Henry Yuen
• Member for 11 years, 5 months
• Last seen more than 1 year ago
• Cambridge, MA

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-...

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,...

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 ...

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, ...

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 ...

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]$....

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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$.