For Fall 2018, the Theory Seminar will meet on Fridays from 2:00-3:00pm in GDC 4.302 unless otherwise noted. This schedule is being updated throughout the semester.

08/10/2018 - Sruthi Sekar, Indian Institute of Sciences: "Privacy Amplification from Non-malleable Codes"
08/31/2018 - Scott Aaronson, University of Texas at Austin: "A Connection Between Gentle Measurement of Quantum States and Differential Privacy"
09/14/2018 - Guy Moshkovitz, Institute of Advanced Study: "A Tight Bound for Hypergraph Regularity"
09/21/2018 - Dean Doron, University of Texas at Austin: "Near-Optimal Erasure List-Decodable Codes"
09/28/2018 - Dana Moshkovitz, University of Texas at Austin: "Small Set Expansion In The Johnson Graph"
10/12/2018 - Ronitt Rubinfeld, MIT and Tel Aviv University: "Local Algorithms for Sparse Connected Subgraphs"
10/26/2018 - Avishay Tal, Stanford University: "Oracle Separation of BQP and the Polynomial Hierarchy"
11/09/2018 - Dana Randall, Georgia Institute of Technology: “Phase Transitions and Emergent Phenomena in Algorithms and Applications”
11/16/2018 - Mark Bun, Princeton University: "Towards Instance-Optimal Private Query Release"
11/30/2018 - Alexander Sherstov, UCLA: “The Hardest Halfspace”
12/07/2018 - Henry Yuen, University of Toronto: "Quantum Proof Systems for Iterated Exponential Time, and Beyond"
12/11/2018 - Leonard Schulman, Caltech: "Analysis of a Classical Matrix Preconditioning Algorithm" **Note: 11am Talk

Sruthi Sekar, Indian Institute of Sciences
Privacy Amplification from Non-malleable Codes

The field of Information-theoretic Cryptography has seen a flurry of exciting research activity in recent times, specifically on two very interesting problems: "Non-malleable Codes" and "Privacy Amplification". Non-malleable codes allow for encoding a message in such a manner that any "legal'' tampering will either leave the message in the underlying tampered codeword unchanged or unrelated to the original message. In the setting of Privacy Amplification, we have two users that share a weak secret "w" guaranteed to have some entropy. The goal is to use this secret to agree on a fully hidden, uniformly distributed, key "K", while communicating on a public channel fully controlled by an adversary. 

In this talk, I will give an introduction to both these primitives and show an interesting connection between them. Specifically, I will show how we get a general transformation that takes any "augmented" non-malleable code and builds a privacy amplification protocol (specifically with "optimal parameters"). 

This is joint work with: Eshan Chattopadhyay, Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu.

Scott Aaronson, University of Texas at Austin
A Connection Between Gentle Measurement of Quantum States and Differential Privacy

I'll explain a surprising new connection between, on the one hand, gentle measurement (where one wants to measure n unentangled quantum states, in a way that damages the states only by a little), and on the other hand, differential privacy (a field of classical CS where one wants to query a database about n users, in a way that reveals only a little about any individual user).  The connection is bidirectional, though with loss of parameters in going from DP to gentle measurement (the nontrivial direction).  By exploiting this connection, together with recent results from classical DP, we're able to give a new protocol for so-called "shadow tomography" of quantum states, which improves over the parameters of my previous protocol for that task, and which has the additional advantage of being "online" (that is, the measurements are processed and responded to one at a time).

Joint work with Guy Rothblum (Weizmann Institute); paper still in preparation.  

Guy Moshkovitz, Institute of Advanced Study
A Tight Bound for Hypergraph Regularity

The hypergraph regularity lemma — the extension of Szemeredi's graph regularity lemma to the setting of k-graphs — is one of the most celebrated combinatorial results obtained in the past decade. By now there are various (very different) proofs of this lemma, obtained by Gowers, Rodl et al. and Tao. Unfortunately, what all these proofs have in common is that they yield partitions whose order is given by the k-th Ackermann function.

We prove that such Ackermann-type bounds are unavoidable for every k>=2, thus confirming a prediction of Tao. Prior to our work, the only result of this kind was Gowers' famous lower bound for graph regularity.  

Dean Doron, University of Texas at Austin
Near-Optimal Erasure List-Decodable Codes

For every small ε, we explicitly construct binary erasure list-decodable codes that can be list-decoded from 1-ε fraction of erasures, with near-optimal list-size poly(log(1/ε)) and near-optimal rate O(ε^(1+γ)) where γ>0 is any constant. This is the first construction to break the ε^2 rate barrier, solving a long-standing open problem raised by Guruswami and Indyk, and it does so with a remarkably small list size (we remark that Guruswami showed such a result is impossible using linear codes, and indeed our code is not linear).

Equivalently, in terms of dispersers, we construct ε-error one-bit strong dispersers with near-optimal seed-length and near-optimal entropy-loss.
The main ingredient in the construction is a new (and nearly optimal) unbalanced two-source extractor. The extractor extracts one bit with constant error from two independent sources, where one source has length n and tiny min-entropy O(loglog n) and the other source has length O(log n) and arbitrarily small constant min-entropy rate.

Dana Moshkovitz, University of Texas at Austin
Small Set Expansion In The Johnson Graph

For natural numbers t<l<k, the nodes of the Johnson graph are sets of size l in a universe of size k. Two sets are connected if their intersection is of size t. The Johnson graph arises often in combinatorics and theoretical computer science: it represents a "slice" of the noisy hypercube, and it is the graph that underlies direct product tests as well as a candidate hard unique game.

We prove that any small set of vertices in the Johnson graph either has near perfect edge expansion or is not pseudorandom. Here "not pseudorandom" means that the set becomes denser when conditioning on containing a small set of elements. In other words, we show that slices of the noisy hypercube -- while not necessarily small set expanders like the noisy hypercube -- can only have small non-expanding sets of a certain simple structure.

The result was motivated, in part, by works of Dinur, Khot, Kindler, Minzer and Safra, which hypothesized and made partial progress on a similar result for the Grassmann graph, and showed that it would imply the proof of the 2 to 2 Conjecture in PCP. In turn, our result served as a crucial step towards the full result for the Grassmann graphs completed subsequently by Khot, Minzer and Safra.

This is joint work with Subhash Khot, Dor Minzer and Muli Safra.

Ronitt Rubinfeld, MIT and Tel Aviv University
Local Algorithms for Sparse Connected Subgraphs

Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety.   However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of  "local computation algorithms" which for a given input, supports queries by a user to values of  specified bits of a legal output.  The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. In this talk, we survey a series of results on local computation algorithms for finding sparse  connected subgraphs and sparse spanners. 

Avishay Tal, Stanford University
Oracle Separation of BQP and the Polynomial Hierarchy

We present an oracle, A, relative to which BQP^A is not contained in PH^A.

Following the approach of Aaronson [STOC, 2010], our oracle separation is obtained by finding a distribution D over Boolean strings of length N such that:
(1) There exists a quantum algorithm that runs in time polylog(N) and distinguishes between D and the uniform distribution over Boolean strings of length N.
(2) No AC0 circuit of quasi-polynomial size can distinguish between D and the uniform distribution with advantage better than polylog(N)/sqrt(N).

Based on joint work with Ran Raz.

Dana Randall, Georgia Institute of Technology
Phase Transitions and Emergent Phenomena in Algorithms and Applications

Markov chain Monte Carlo methods have become ubiquitous across science and engineering as a means of sampling from large configuration spaces. A striking discovery has been the realization that many natural Markov chains undergo a phase transition where they change from being efficient to inefficient as some parameter of the system is modified. In this talk we will explore this phenomenon, and show how insights from computing reveal interesting results in other fields, including colloids, models of segregation, and asynchronous models of programmable matter.

Mark Bun, Princeton University
Towards Instance-Optimal Private Query Release

Research in differential privacy aims to understand when and how we can perform statistical analyses on sensitive data while protecting individual privacy. In this talk, I will describe new geometric algorithms for privately releasing approximate answers to statistical queries. Our algorithms are efficient and achieve optimal sample complexity for any given query workload (up to constant factors, in certain parameter regimes) with respect to the class of all algorithms satisfying concentrated differential privacy. The framework we introduce is quite flexible, and also yields optimal query release algorithms in the local model of privacy.

This is joint work with Jarosław Błasiok, Aleksandar Nikolov, and Thomas Steinke.

Alexander Sherstov, UCLA
The Hardest Halfspace

We study the infinity-norm approximation of halfspaces h:{0,1}^n->{0,1} by polynomials and rational functions. We determine the minimum error to which approximants of any given degree can approximate the worst-case halfspace, and construct this "hardest" halfspace explicitly. As an application, we construct a communication problem with the largest possible gap between sign-rank and discrepancy (or equivalently,
communication complexity with unbounded versus weakly bounded error), improving quadratically on previous constructions.

The proof features elements of approximation theory, random walks, and number theory. Our starting point is the construction, due to Ajtai et al. (1990), of a set of O(log m) integers that appear random modulo m in the sense of the discrete Fourier transform on Z/mZ.

Henry Yuen, University of Toronto
Quantum Proof Systems for Iterated Exponential Time, and Beyond

An outstanding open question in quantum information theory concerns the computational complexity of nonlocal games. in a nonlocal game, a classical verifier interacts with multiple players that cannot communicate, but are allowed to share entanglement. In a recent breakthrough result, Slofstra showed that the following problem is undecidable: given a nonlocal game, is there a quantum strategy for the players to win with probability 1?
In this work, we show that even the approximation problem for nonlocal games is extremely difficult. We prove that approximating the maximum winning probability to within additive error 1/f(n) is as hard as any problem solvable in time 2^O(f (n)), even using nondeterministic resources. Here, n is the size of the game, and f(n) is an arbitrary (time-constructible) function, such as an iterated exponential function. By contrast, the maximum winning probability for games with classical players can be exactly computed in nondeterministic exp(n) time. The high complexity of nonlocal games arises from the ability to encode arbitrarily complex computations into entangled states. 
I will discuss some consequences of our result: (1) we give an alternate proof of Slofstra's undecidability result; (2) we present polynomial-size quantum proof systems for nondeterministic 2^O(f (n)) time with completeness-soundness gap 1/f(n) for arbitrary f(n), and (3) we show that seemingly minor quantitative improvements to our result would yield negative answers to long-standing questions in quantum information theory and pure mathematics.
I won't assume any prior knowledge of quantum information theory. This is joint work with Joe Fitzsimons, Zhengfeng Ji, and Thomas Vidick.

Leonard Schulman, Caltech
Analysis of a Classical Matrix Preconditioning Algorithm

There are several prominent computational problems for which simple iterative methods are widely preferred in practice despite an absence of runtime or performance analysis (or "worse", actual evidence that more sophisticated methods have superior performance according to the usual criteria). These situations raise interesting challenges for the analysis of algorithms.

We are concerned in this work with one such simple method: a classical iterative algorithm for balancing matrices via scaling
transformations. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard
preconditioner for eigenvalue computations in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence.

We prove the first such bound: a natural L_\infty -norm variant of the algorithm converges, on n by n matrices, in O(n^3 log(n)) elementary scaling transformations. This is tight up to the log n factor. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed.

Joint work with Alistair Sinclair (Berkeley)