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"

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.