user avatar
user avatar
user avatar
Or Meir
  • Member for 10 years, 4 months
  • Last seen this week
70 votes
Accepted

Why does Fourier analysis of Boolean functions "work"?

19 votes
Accepted

$d$-regular bipartite expander graph

18 votes

The utility of Renyi entropies?

17 votes

AM/MA and NP in analogy to P and BPP

16 votes

Landscape of interactive proof systems

15 votes
Accepted

What's known about basing one-way function on the $P \neq NP$ assumption?

12 votes

$BPL$ with polylog random bits is in $L$

12 votes

Book on Probability

11 votes

Uniform way of quantifying "branching" in nondeterministic, probabilistic, and quantum computation?

10 votes
Accepted

Why is $\{0,1\}^n$ referred to as the Boolean hypercube?

10 votes
Accepted

What is the reason for using a "Lines-Oracle" in the PCP Theorem?

10 votes

Variants of direct product theorems

9 votes
Accepted

Where can I find examples of error correcting codes of the following types?

8 votes
Accepted

Distinguishing a biased coin with a small set of tests

8 votes

Why is the circuit class AC0 unavoidable?

8 votes
Accepted

The entropy of a noisy distribution

8 votes

Hierarchy theorems for circuit depth

8 votes

What is the fastest known simulation of BPP using Las Vegas algorithms?

8 votes

Why does Dinur's proof of the PCP theorem fail to work for unique games?

7 votes
Accepted

Best known asymptotic PCP sizes / 3-SAT

6 votes

Major unsolved problems in theoretical computer science?

5 votes

Algorithms with finite expected running time and infinite variance

5 votes

How do top researchers keep track new results in datastructures

5 votes

Second eigenvalue and the last eigenvalue

5 votes

Is a software implementation of a PCP encoder available?

5 votes

Why can't codes be defined over infinite fields?

5 votes
Accepted

Is $P^{SAT} \subseteq NP$?

5 votes

PCP research proposal

4 votes
Accepted

Are there Similar Distance Binary Error Correcting Codes?

4 votes
Accepted

Testing low degree bivariate polynomials