Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$).
We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ... more >>>

We show that a very simple pseudorandom generator fools intersections of $k$ linear threshold functions (LTFs) and arbitrary functions of $k$ LTFs over $n$-dimensional Gaussian space.

The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of ... more >>>

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... more >>>