# 5th TOCA-SV Day

## Friday, Nov 9, 2018, 11:00 am -- 5:30 pm

### Huang Mackenzie Center Room 300

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