9
$\begingroup$

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.

$\endgroup$
0

4 Answers 4

Reset to default
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Does Nisan's pseudo-random generator relativize?

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

$\endgroup$
1
  • $\begingroup$ indeed ! that's a good example. Not sure if the OP realized it though. $\endgroup$
    – Suresh Venkat Mod
    Commented Oct 17, 2010 at 3:16
1
$\begingroup$

Quick encoding of balanced vectors

Reasons:

  • Cute coding theory-ish problem: works great as a puzzle
  • Two nice and complete answers.
$\endgroup$
0
$\begingroup$

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)
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Commented Sep 25, 2010 at 0:47

You must log in to answer this question.

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