Henry Yuen
  • Member for 11 years, 5 months
  • Last seen more than 1 year ago
What papers should everyone read?
153 votes

The 1936 paper that arguably started computer science itself: Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society s2-...

View answer
Representing OR with polynomials
26 votes

Let $p$ be a polynomial such that for all $x\in \{0,1\}^n$, $p(x) = \sf{OR}(x)$. Consider the symmetrization of the polynomial $p$: $$q(k) = \frac{1}{\binom{n}{k}} \sum_{x: |x| = k} p(x).$$ Note that,...

View answer
Derandomizing Valiant-Vazirani?
22 votes

Just for reference, I stumbled across this really interesting paper today, which gives evidence that a deterministic reduction is unlikely: Dell, H., Kabanets, V., Watanabe, O., & van ...

View answer
Physical realization of nonlinear operators for quantum computers.
Accepted answer
18 votes

Short answer: if you believe quantum mechanics is an accurate description of nature, then since QM is a linear theory, it isn't possible to physically realize nonlinear operations. As far as we know, ...

View answer
Generating "infinite" randomness from a constant number of sources
15 votes

This is a great question, Suresh! Our randomness expansion result does not imply any complexity theoretic result. Here's one way to understand the result: we believe that quantum mechanics governs ...

View answer
A converse to Fano's inequality ?
Accepted answer
12 votes

Consider the following reconstruction procedure $P(y)$: given $y$, output $x$ such that $\Pr[X = x \mid Y = y]$ is maximized. The probability that this procedure succeeds is $\max_x \Pr[x \mid Y = y]$....

View answer
Surprising Results in Complexity (Not on the Complexity Blog List)
12 votes

I would say the recent work of Jain, Upadhyay and Watrous showing that QIP = IP = PSPACE is quite surprising. My opinion is that it isn't so much that QIP = IP is interesting but rather the fact that ...

View answer
$\mathcal{MA}$ in terms of $\mathcal{PCP}$
11 votes

Under a hardness assumption, namely, that the complexity class $E = DTIME(2^{O(n)})$ requires circuits of exponential size, suffices to derandomize $MA$, so that $MA = NP$. In fact, the ...

View answer
Does the MIP* = RE proof work for limited provers?
Accepted answer
9 votes

I believe our result shows that if the prover is capable of solving NTIME[poly(T)] problems, and has the ability to manipulate polylog(T) qubits, then they can convince the verifier of YES instances ...

View answer
Asymmetry in Property Testing Definition
7 votes

This is because there isn't really a gap between $\epsilon$-close to having a property $P$ and being $\epsilon$-far to having property $P$. As a crude example, suppose we're testing the property of ...

View answer
High probability events without low probability coordinates
6 votes

How does $\epsilon$ compare to $n$? If $\epsilon$ can be $O(1/\sqrt{n})$, then I think we can accomplish what you want. Let $B = \mbox{Supp}(X) - E$. Note that $B$ is given $\epsilon$ probability mass ...

View answer
Notation for a Conditional Hamiltonian Evolution Operator
Accepted answer
6 votes

I remember struggling with this very same question! Ultimately I concluded that the $C$ is just a notational device (it doesn't represent any mathematical operation), just to indicate that, for a ...

View answer
Non adaptive PCP
3 votes

The assumption is that the number of queries is at most logarithmic in the input size ($n$), so $2^q$ is still polynomial in $n$.

View answer
Why does the Complexity Class PostBQP makes proving PP greater than or equal to QMA easier?
0 votes

I assume by "greater or equal to" you mean "contains". Well, one facile answer to this question is that PostBQP is inherently a quantum complexity class, whereas PP is defined in terms of classical ...

View answer