up vote 7 down vote favorite
5

To promote this site, it would be useful to have a collection of our highlights. Hence this question:

What are the best technical questions that have been asked and answered on cstheory.stackexchange.com?

Rules: One thread per answer. Briefly explain why you think it is a highlight. This is CW, please edit the answers to improve them, and vote up/down freely to rank the answers.

share

4 Answers

up vote 3 down vote

A Boolean function that is not constant on affine subspaces of large enough dimension

A very technical question, with a specific answer. Possibly the exact kind of question that we'd like to see more of.

share
up vote 2 down vote

Does Nisan's pseudo-random generator relativize?

Noam Nisan answering a question about his own pseudorandom generator :)

share
indeed ! that's a good example. Not sure if the OP realized it though. – Suresh Venkat♦ Oct 17 '10 at 3:16
up vote 1 down vote

Quick encoding of balanced vectors

Reasons:

  • Cute coding theory-ish problem: works great as a puzzle
  • Two nice and complete answers.
share
up vote 0 down vote

Approximate counting problem capturing BQP

Reasons:

  • Very natural and elegant question
  • Clean and direct answer
  • A recent answer (i.e not something in the canon that a google search would have immediately found)
share
I'm not really sure if the OP's question was answered. Firstly, the paper doesn't mention any black-box problems. If we get a black-box problem out under some natural interpretation, I don't see how the problem captures BQP. It seems harder than BQP, but I don't see how it is in BQP. I guess only the OP can tell us if it answers his question or not. – Robin Kothari Sep 25 '10 at 0:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged