Next

__
TR18-101
| 20th May 2018
__

Akash Kumar, C. Seshadhri, Andrew Stolman#### Finding forbidden minors in sublinear time: a $O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs

__
TR18-100
| 18th May 2018
__

Eshan Chattopadhyay, Anindya De, Rocco Servedio#### Simple and efficient pseudorandom generators from Gaussian processes

__
TR18-099
| 19th May 2018
__

Scott Aaronson#### PDQP/qpoly = ALL

Next

Akash Kumar, C. Seshadhri, Andrew Stolman

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

Eshan Chattopadhyay, Anindya De, Rocco Servedio

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

Scott Aaronson

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

Next