5th TOCA-SV Day

Schedule

1045-1100: Welcome

1100-1145: Avishay Tal (Simons Institute & Stanford University) , Oracle Separation of BQP and the Polynomial Hierarchy

1145-1230: Badih Ghazi (Google), Resource-Efficient Common Randomness and Secret Key Generation

1230-1400: Lunch (provided)

1400-1515: Motwani Colloquium: Shafi Goldwasser (Simons Institute), Pseudo Deterministic Algorithms and Proofs

1515-1540: Happy hour!

1515-1730: Student talks

1540-1605: Dima Kogan, The Function-Inversion Problem: Barriers and Opportunities

1605-1630: Clement Cannone, Testing and Learning Distributions Under Local Information Constraints

1630-1640: Happy hour refill!

1640-1705: Weihao Kong, Estimating Learnability

1705-1730: Oliver Hinder, Convex Until Proven Guilty: Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Abstracts

Avishay Tal, Oracle Separation of BQP and the Polynomial Hierarchy

In their seminal paper, Bennett, Bernstein, Brassard and Vazirani [SICOMP, 1997] showed that relative to an oracle, quantum algorithms are unable to solve NP-complete problems in sub-exponential time (i.e., that Grover's search is optimal in this setting).

In this work, we show a strong converse to their result. Namely, we show that, relative to an oracle, there exist computational tasks that can be solved efficiently by a quantum algorithm, but require exponential time for any algorithm in the polynomial hierarchy (a hierarchy of complexity classes that captures P, NP, coNP, and their generalizations).

The tasks that exhibit this "quantum advantage" arise from a pseudo-randomness approach initiated by Aaronson [STOC, 2010]. Our core technical result is constructing a distribution over Boolean strings that "look random" to constant-depth circuits of quasi-polynomial size, but can be distinguished from the uniform distribution by very efficient quantum algorithms.

Joint work with Ran Raz

Badih Ghazi, Resource-Efficient Common Randomness and Secret Key Generation

The task of manipulating randomness has been a subject of intense investigation in computational complexity with dispersers, extractors, pseudorandom generators, condensers, mergers being just a few of the objects of interest. All these tasks consider a single processor massaging random samples from an unknown source.

In this talk, I will discuss a less studied setting where randomness is distributed among different players who would like to convert it to other forms in an efficient manner and with little communication. For instance players may be given access to a source of biased correlated bits and their goal may be to get a common random string out of this source. Even the setting where the source is known leads to some interesting questions that have been explored since the 70s with striking constructions and some surprisingly hard questions. After giving some background, I will describe recent work which explores the task of extracting common randomness from correlated sources with bounds on either the sample complexity or on the number of rounds of interaction.

Based on joint works with T.S. Jayram, Mitali Bafna, Noah Golowich and Madhu Sudan

Shafi Goldwasser, Pseudo Deterministic Algorithms and Proofs

Probabilistic algorithms for both decision and search problems can offer significant complexity improvements over deterministic algorithms. One major difference, however, is that they may output different solutions for different choices of randomness. This makes correctness amplification impossible for search algorithms and is less than desirable in setting where uniqueness of output is important such as generation of system wide cryptographic parameters or distributed setting where different sources of randomness are used. Pseudo-deterministic algorithms are a class of randomized search algorithms, which output a unique answer with high probability. Intuitively, they are indistinguishable from deterministic algorithms by an polynomial time observer of their input/output behavior. In this talk I will describe what is known about pseudo-deterministic algorithms in the sequential, sub-linear and parallel setting. We will also describe n extension of pseudo-deterministic algorithms to interactive proofs for search problems where the verifier is guaranteed with high probability to output the same output on different executions, regardless of the prover strategies.