Theory Seminar Series

08/30/2024 - Dana Moshkovitz, University of Texas Austin: Coding Theory in Almost-Linear Time and Sub-Linear Space
 09/06/2024 - Jeremy Fineman, Georgetown University: Beating Bellman-Ford: Faster Single-Source Shortest Paths with Negative Real Weights
09/13/2024 - Maryam Aliakbarpour, Rice University: Hypothesis selection with computational constraints
09/20/2024 - Barna Saha, UC San Diego: Faster All Pairs Shortest Paths
09/27/2024 - Noah Golowich, MIT: Computationally Efficient Reinforcement Learning with Linear Bellman Completeness  
NOTE LOCATION: 12:15pm, GDC 6.302
10/04/2024 - Venkatesan Guruswami, UC Berkeley: The Parameterized Inapproximability Hypothesis
10/11/2024 - Kuikui Liu, MIT: Strong spatial mixing for colorings on trees and its algorithmic applications
10/18/2024 - Nick Hunter-Jones, University of Texas at Austin:  Random unitaries in low depths
10/25/2024 - Sabee Grewal, University of Texas at Austin: Improved Stabilizer Estimation via Bell Difference Sampling & Siddhartha Jain, University of Texas at Austin: On Pigeonhole Principles and Ramsey in TFNP
11/01/2024 - Cristopher Moore, Santa Fe Institute: Tensor networks and phase transitions in machine learning 
NOTE LOCATION: 12:15pm, GDC 6.302
11/08/2024 - Jesse Goodman, University of Texas at Austin: Improved condensers for Chor-Goldreich sources
11/15/2024 - Vasilis Kontonis, University of Texas at Austin: Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
11/22/2024 - Yael Tauman Kalai, MIT: Classical commitments to quantum states
11/29/2024 -
12/06/2024 - Roei Tell
12/13/2024 - Ian Mertz

08/30/2024
Dana Moshkovitz, University of Texas Austin
Coding Theory in Almost-Linear Time and Sub-Linear Space

Typical time-efficient encoding and decoding algorithms for error correcting codes use linear space. We construct asymptotically good codes that can be deterministically encoded in almost linear time and sub-linear space, as well as asymptotically good codes that can be deterministically decoded in this complexity. The encodable codes are based on condenser graphs. The decodable codes are based on locally correctable codes and a new efficient derandomization method. We believe that the new derandomization method is of independent interest.
 

The talk is based on joint works with Joshua Cook.

Jeremy Fineman, Georgetown University 
Beating Bellman-Ford: Faster Single-Source Shortest Paths with Negative Real Weights 
This talk presents a new randomized algorithm for the problem of single-source shortest path on directed graphs with real (both positive and negative) edge weights. Given an input graph with n vertices and m edges, the algorithm completes in $\tilde{O}(mn^{8/9})$ time with high probability. Whereas there has been significant progress for the case of integer-weighted graphs, this result constitutes the first asymptotic improvement over the 

classic O(mn)-time algorithm for the case of real weights.

Maryam Aliakbarpour, Rice University
Hypothesis selection with computational constraints
With the ever-growing volume of data, understanding the computational aspects of statistical inference is increasingly critical. A key question arises: Can we develop algorithms that are both fast and memory-efficient to tackle these challenges? In this talk, we focus on the computational aspects of Hypothesis Selection, a fundamental problem in learning theory and statistics. The task is to select a distribution from a finite set of candidate distributions that best matches the underlying distribution of the given dataset. This talk will delve into the hypothesis selection problem under constraints of memory and time. We will explore how to achieve a nearly optimal tradeoff between memory usage and sample complexity, as well as methods to attain optimal accuracy using algorithms with near-optimal time complexity. 
 

This talk is based on joint work with Mark Bun and Adam Smith. 

Barna Saha, UC San Diego
Faster All Pairs Shortest Paths
We consider the age-old all pairs shortest path problem. For graphs with n vertices, the all-pairs shortest paths conjecture states that there is no algorithm that is truly subcubic. We show how approximations (both multiplicative and additive) allow us to go way below the cubic bound beating the previous results.

Computationally Efficient Reinforcement Learning with Linear Bellman Completeness
One of the most natural approaches to reinforcement learning (RL) with function approximation is value iteration, which inductively generates approximations to the optimal value function by solving a sequence of regression problems. To ensure the success of value iteration, it is typically assumed that Bellman completeness holds, which ensures that these regression problems are well-specified. I will discuss new results on the problem of learning an optimal policy under Bellman completeness in the online and offline models of RL with linear function approximation.

Venkatesan Guruswami, UC Berkeley 
The Parameterized Inapproximability Hypothesis 
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable instance of a constraint satisfaction problem (CSP) parameterized by the number of variables, from one where every assignment fails to satisfy 1% of the constraints. PIH plays the role of the PCP theorem in parameterized complexity, with many downstream inapproximability consequences. 

Sabee Grewal, University of Texas at Austin 
Improved Stabilizer Estimation via Bell Difference Sampling
Stabilizer states, which are the outputs of Clifford circuits, play a central role in quantum information. Aaronson and Gottesman (2008) and Montanaro (2017) showed that n-qubit stabilizer states can be learned in poly(n) time. In this talk, I'll discuss joint work with Vishnu Iyer, William Kretschmer, and Daniel Liang, where we establish new learnability and non-pseudorandomness results for outputs of Clifford+T circuits and generalizations thereof.

Siddhartha Jain, University of Texas at Austin 
On Pigeonhole Principles and Ramsey in TFNP
A celebrated theorem of Frank Ramsey says that in any undirected, simple graph on 2^n vertices, there must exist a clique or independent set of size n/2. RAMSEY is the search problem of finding such a clique or independent set given a succinctly represented graph as input. Similarly, PIGEON is the search problem corresponding to the Pigeonhole Principle.

Jesse Goodman, University of Texas at Austin
Improved condensers for Chor-Goldreich sources

Yael Tauman Kalai, MIT
Classical commitments to quantum states

01/19/2024 - Samson Zhou, Texas A&M University: Streaming Euclidean k-median and k-means with o(log n) Space
01/26/2024 - Thomas Rothvoss, University of Washington: The Subspace Flatness Conjecture and Faster Integer Programming
02/02/2024 - Brent Waters, University of Texas: Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation 
02/09/2024 - Gregory Kehne, University of Texas: Online Covering: Secretaries, Prophets, and Samples
02/16/2024 - NO MEETING THIS WEEK
02/23/2024 - Parikshit Gopalan, Apple: Omniprediction and multigroup fairness 
03/01/2024 - Ainesh Bakshi, MIT:  Learning quantum Hamiltonians at any temperature in polynomial time 
03/08/2024 - Josh Alman, Columbia University: Faster Walsh-Hadamard Transform from Matrix Non-Rigidity 
03/15/2024   SPRING BREAK
03/22/2024 - Ce Jin, MIT: 0-1 Knapsack in Nearly Quadratic Time
                        ROOM CHANGE: meeting in Wel 3.320 
03/29/2024 -  Ryan Williams, MIT:  Beating Brute Force for Compression Problems
04/05/2024 - Moses Charikar, Stanford: Breaking the Metric Voting Distortion Barrier 
04/12/2024 - Amit Sahai, UCLA: The Mathematics of Hiding Secrets in Software 
                        MEETING TIME IS 2pm
04/19/2024 - Euiwoong Lee, University of Michigan: Recent Progresses on Correlation Clustering 
04/26/2024 - Yufei Zhao, MIT:  Equiangular lines and eigenvalue multiplicity 
05/03/2024 - Mohsen Ghaffari, MIT: Parallel Derandomization for Chernoff-like Concentrations​
                         ROOM CHANGE: meeting in POB 2.402

01/19/2024
Samson Zhou, Texas A&M University
Streaming Euclidean k-median and k-means with o(log n) Space

We consider the classic Euclidean k-median and k-means objective on insertion-only streams, where the goal is to maintain a (1+epsilon)-approximation to the k-median or k-means, while using as little memory as possible. Over the last 20 years, clustering in data streams has received a tremendous amount of attention and has been the test-bed for a large variety of new techniques, including coresets, the merge-and-reduce framework, bicriteria approximation, sensitivity sampling, and so on. Despite this intense effort to obtain smaller sketches for these problems, all known techniques require storing at least Omega(log(nDelta)) words of memory, where n is the size of the input and Delta is the aspect ratio. A natural question is if one can beat this logarithmic dependence on n and Delta. In this paper, we break this barrier by giving the first algorithm that achieves a (1+epsilon)-approximation to the more general (k,z)-clustering problem, using only ~O(dk/varepsilon^2)*(2^{z log z})*min(1/epsilon^z, k)*poly(log log(n Delta)) words of memory.

Joint work with Vincent Cohen-Addad and David P. Woodruff.

01/26/2024
Thomas Rothvoss, University of Washington
The Subspace Flatness Conjecture and Faster Integer Programming

In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity  $\mu_{KL}(\Lambda,K)$ which denotes the best volume-based lower bound on the \emph{covering  radius} $\mu(\Lambda,K)$ of a convex body $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved  that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,K)$ and the Subspace  Flatness Conjecture by Dadush (2012) claims a $O(\log n)$ factor  suffices, which would match the lower bound from the work of Kannan and Lov\'asz. We settle this conjecture up to a constant in the exponent by proving 
that  $\mu(\Lambda,K) \leq O(\log^{3}(n)) \cdot \mu_{KL} (\Lambda,K)$.  Our proof is based on the Reverse Minkowski Theorem due to Regev and 
Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a $(\log  n)^{O(n)}$-time randomized algorithm to
solve integer programs in $n$ variables. Another implication of our main result is a near-optimal \emph{flatness  constant} of $O(n \log^{3}(n))$.

This is joint work with Victor Reis.

02/02/2024​
Brent Waters, University of Texas
Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation

A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement x is true with a proof of size o(|x| + |w|) where w is the associated NP witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for NP in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for NP from falsifiable} assumptions. All previous SNARGs for in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters).

This is joint work with David Wu.

02/09/2024 
Gregory Kehne, University of Texas 
Online Covering: Secretaries, Prophets, and Samples

What makes set cover harder to solve online than off? By way of an answer, we give a polynomial-time algorithm for online covering integer programs (IPs) with a competitive ratio of O(\log mn) when the constraints are revealed in random order, essentially matching the best possible offline bound of \Omega(\log n) and circumventing the \Omega(\log m \log n) lower bound known in adversarial order. We then leverage this O(\log mn) competitive algorithm for the prophet version of online integer covering, where constraints are sampled from a sequence of known distributions. We present sample guarantees in the prophet setting, as well as in the setting where random samples from an adversarial instance are revealed at the outset.

This talk is based on joint work with Anupam Gupta and Roie Levin.

02/23/2024 
Parikshit Gopalan, Apple 
Omniprediction and multigroup fairness

Consider a scenario where we are learning a predictor, whose predictions will be evaluated by their expected loss. What if we do not know the precise loss at the time of learning, beyond some generic properties (like convexity)? What if the same predictor will be used in several applications in the future, each with their own loss function? Can we still learn predictors that have strong guarantees? 
This motivates the notion of omnipredictors: predictors with strong loss minimization guarantees across a broad family of loss functions, relative to a benchmark hypothesis class. Omniprediction turns out to be intimately connected to multigroup fairness notions such as multicalibration, and also to other topics like boosting, swap regret minimization, and the approximate rank of matrices. This talk will present recent work in this area, emphasizing these connections. 

03/01/2024 
Ainesh Bakshi, MIT 
Learning quantum Hamiltonians at any temperature in polynomial time

A quantum system of n interacting particles at thermal equilibrium can be described using a polynomial number of parameters, which correspond to the strengths of the forces between particles. A natural open question has been whether these parameters can be estimated efficiently by running experiments on the system. We resolve this question by giving the first polynomial-time algorithm for this task. This improves over prior work, which uses polynomially many samples from the system, but requires exponential time. In this talk, I will introduce the problem and describe some of the key ideas behind our algorithm. No background in quantum information is required.

Based on joint work with Allen Liu, Ankur Moitra and Ewin Tang.

03/08/2024 
Josh Alman, Columbia University 
Faster Walsh-Hadamard Transform from Matrix Non-Rigidity

The Walsh-Hadamard transform is a simple recursively-defined linear transformation with many applications throughout algorithm design and complexity theory. The folklore "fast Walsh-Hadamard transform" algorithm computes it using only N log N arithmetic operations, which is believed to be optimal up to constant factors. In this talk, I'll give two improved constructions:

- A new algorithm which uses (23/24) N log N + O(N) arithmetic operations. This is, to my knowledge, the first improvement of the leading constant. (Based on joint work with Kevin Rao.)

- A new depth-2 linear circuit of size O(N^1.45), improving on size O(N^1.5) which one gets from the fast Walsh-Hadamard transform approach. (Based on joint work with Ashwin Padaki and Yunfeng Guan.)

A key idea behind both constructions is to take advantage of the matrix non-rigidty of the Walsh-Hadamard transform. A matrix is called "rigid" if it's impossible to change a "small" number of its entries to make it have "low" rank. L. Valiant showed that if a matrix is rigid, then this implies lower bounds for computing its linear transformation. However, a recent line of work has shown that many matrices of interest, including the Walsh-Hadamard transform, are actually not rigid. Although a formal converse to Valiant's result is not known, we'll make use of non-rigidity in our new constructions.

03/22/2024 
Ce Jin, MIT
0-1 Knapsack in Nearly Quadratic Time

We study pseudo-polynomial time algorithms for the fundamental 0-1 Knapsack problem. Recent research interest has focused on its fine-grained complexity with respect to the number of items n and the maximum item weight w_max. Under (min,+)-convolution hypothesis, 0-1 Knapsack does not have O((n+w_max)^{2-δ}) time algorithms (Cygan-Mucha-Węgrzycki-Włodarczyk 2017 and Künnemann-Paturi-Schneider 2017). On the upper bound side, currently the fastest algorithm runs in O~(n + w_max^{12/5}) time (Chen, Lian, Mao, and Zhang 2023), improving the earlier O(n + w_max^3)-time algorithm by Polak, Rohwedder, and Węgrzycki (2021).

We close this gap between the upper bound and the conditional lower bound (up to subpolynomial factors): The 0-1 Knapsack problem has a deterministic algorithm in O(n + w_max^2 * log^4 w_max) time.

03/29/2024 
Ryan Williams, MIT 
Beating Brute Force for Compression Problems

A compression problem is defined with respect to an efficient encoding function f: given a string x, the goal is to find the shortest y such that f(y)=x. The obvious brute-force algorithm for solving a compression problem on n-bit strings runs in time about 2^s, where s is the length of the shortest description y.

We show that every compression problem has a Boolean circuit family which finds short descriptions more efficiently than brute force. In particular, our circuits have size roughly 2^{4s/5}. Our construction builds on Fiat-Naor’s data structure for function inversion [SICOMP 1999]: we show how to carefully modify their data structure so that it can be nontrivially implemented using Boolean circuits, and we show how to utilize hashing so that the circuit size is only exponential in the description length.

One corollary is that the Minimum Circuit Size Problem for generic fan-in two circuits of size s(n) on truth tables of size 2^n can be solved by circuits of size 2^{4/5 w + o(w)}poly(2^n), where w=s(n)log_2(s(n)+n). This improves over the brute-force approach of trying all possible size-s(n) circuits for all s(n) >= n.

This talk is based on joint work with Shuichi Hirahara and Rahul Ilango, which will be merged with concurrent and independent work of Noam Mazor and Rafael Pass.

04/05/2024 
Moses Charikar, Stanford 
Breaking the Metric Voting Distortion Barrier

We consider the following well-studied problem of metric distortion in social choice. Suppose we have an election with voters and candidates who lie in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, each voter gives us a ranked list of the candidates in order of distance. Can we design a voting rule that, regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion)? 
A long line of work culminated in finding deterministic voting rules with metric distortion 3, which is the best possible for deterministic rules and many other classes of voting rules. However, without any restrictions, there is still a significant gap in our understanding. Even though the best lower bound is substantially lower at 2.112, finding a randomized rule that guarantees distortion $3 - \epsilon$ for some constant $\epsilon$ has been a major challenge in computational social choice. 
In this work, we give a rule that guarantees distortion less than 2.753 by carefully randomizing between Maximal Lotteries, a natural game-theoretical voting rule dating back to the 60's, and new voting rules that we introduce. 
Based on joint work with Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu.
 

04/12/2024 
Amit Sahai 
The Mathematics of Hiding Secrets in Software

At least since the initial public proposal of public-key cryptography based on computational hardness conjectures (Diffie and Hellman, 1976), cryptographers have contemplated the possibility of a “one-way compiler” that translates computer programs into “incomprehensible” but equivalent forms. And yet, the search for such a “one-way compiler” remained elusive for decades.
In this talk, we look back at our community’s attempts to formalize the notion of such a compiler, culminating in our 2001 work with Barak, Goldreich, Impagliazzo, Rudich, Vadhan, and Yang, which proposed the notion of indistinguishability obfuscation (iO). Roughly speaking, iO requires that the compiled versions of any two equivalent programs (with the same size and running time) be indistinguishable to any efficient adversary. The notion of punctured programming, introduced in our work with Waters in 2013, spawned an area of research dedicated to exploring the remarkable power of iO.
We’ll then discuss the intense effort that recently culminated in our 2021 work with Jain and Lin, finally showing how to construct iO in such a way that, for the first time, we can prove the security of our iO scheme based on well-studied computational hardness conjectures in cryptography.

04/19/2024
Euiwoong Lee, University of Michigan
Recent Progresses on Correlation Clustering

Correlation Clustering is one of the most well-studied graph clustering problems. The input is a complete graph where each edge is labeled either "+" or "-", and the goal is to partition the vertex set into (an arbitrary number of) clusters to minimize (the number of + edges between different clusters) + (the number of - edges within the same cluster). Until recently, the best polynomial-time approximation ratio was 2.06, nearly matching the integrality gap of 2 for the standard LP relaxation.

Since 2022, we have bypassed this barrier and progressively improved the approximation ratio, with the current ratio being 1.44. Based on a new relaxation inspired by the Sherali-Adams hierarchy, the algorithm introduces and combines several tools considered in different contexts, including "local to global correlation rounding" and "combinatorial preclusering". In this talk, I will describe the current algorithm as well as how it has been inspired by various viewpoints.

Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl.

04/26/2024 
Yufei Zhao, MIT 
Equiangular lines and eigenvalue multiplicity

I will discuss our solution to a longstanding discrete geometry problem where we determined the maximum number of lines in high dimension pairwise separated by a fixed angle. A key step is a new result in spectral graph theory showing that a connected bounded degree graph has sublinear second eigenvalue multiplicity.

These results prompted further investigations into spherical codes and spectral graph theory. I will highlight some ongoing work and open problems.

05/03/2024
Mohsen Ghaffari
Parallel Derandomization for Chernoff-like Concentrations

Randomized algorithms frequently use concentration results such as Chernoff and Hoeffding bounds. A longstanding challenge in parallel computing is to devise an efficient method to derandomize parallel algorithms that rely on such concentrations. Classic works of Motwani, Naor, and Naor [FOCS'89] and Berger and Rompel [FOCS'89] provide an elegant parallel derandomization method for these, via a binary search in a k-wise independent space, but with one major disadvantage: it blows up the computational work by a (large) polynomial. That is, the resulting deterministic parallel algorithm is far from work-efficiency and needs polynomial processors even to match the speed of single-processor computation. This talk overviews a duo of recent papers that provide the first nearly work-efficient parallel derandomization method for Chernoff-like concentrations.
Based on joint work with Christoph Grunau and Vaclav Rozhon, which can be accessed via https://arxiv.org/abs/2311.13764 and https://arxiv.org/abs/2311.13771.
 

08/15/2023 - Xin Li, Johns Hopkins University: Two Source Extractors for Asymptotically Optimal Entropy, and Improved Ramsey Graphs ***Location: GDC 4.304 Time: 11:00am-12:00pm*** 
08/25/2023 - Geoffrey Mon, UT Austin: Relaxed Local Correctability from Local Testing
09/01/2023 - Kevin Tian, UT Austin: Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory
09/08/2023 - Raghu Meka, UCLA: Resolving Matrix Spencer Conjecture Up to poly-logarithmic Rank
09/15/2023 - Scott Aaronson, UT Austin/Open AI: Watermarking of Large Language Models
09/22/2023 - Peter Manohar, Carnegie Mellon University: Lower Bounds for Locally Decodable Codes from Semirandom CSP Refutation
09/29/2023 -
10/06/2023 - Ali Vakilian, TTIC: Algorithms for Socially Fair Clustering: Min-Max Fairness to Cascaded Norms
10/13/2023 - Keegan Ryan, UCSD: Fast Practical Lattice Reduction through Iterated Compression
10/20/2023 - Aaron Potechin, University of Chicago: Separating MAX 2-AND, MAX DI-CUT and MAX CUT
10/27/2023 - Lijie Chen, UC Berkeley: Polynomial -Time Pseudodeterministic Construction of Primes
11/03/2023 - Jesse Goodman, UT Austin: Exponentially Improved Extractors for Adversarial Sources
11/10/2023 - Greg Bodwin , University of Michigan: Recent Progress on Fault Tolerant Spanners
11/17/2023 - Thatchaphol Saranurak, University of Michigan: Using Isolating Mincuts for Fast Graph Algorithms: A Tutorial
11/24/2023 - THANKSGIVING HOLIDAY
12/01/2023 - Sivakanth Gopi, Microsoft Research:  Higher Order MDS Codes and List Decoding
12/08/2023 - Jinyoung Park, Courant Institute of Mathematical Sciences NYU: Thresholds  

08/15/2023
Xin Li, Johns Hopkins University
Two Source Extractors for Asymptotically Optimal Entropy, and Improved Ramsey Graphs

Randomness extractors are functions that extract almost uniform random bits from weak random sources with severe biases. One of the most important and well studied types of extractors is the so-called two source extractor, where the input consists of two independent weak sources. Assuming each source has n bits, one can show the existence of two source extractors for entropy k =log n+O(1). Such an extractor also gives a (bipartite) Ramsey graph with N=2^n vertices (on each side), such that there is no (bipartite) clique or independent set of size K=O(log N). Explicit constructions of two source extractors and Ramsey graphs are long standing open problems, dating back to the year of 1947 when Erd˝os invented the probabilistic method.

However, despite considerable effort and several recent breakthroughs, previously the best explicit two source extractor only works for entropy k=o(log n log log n). Correspondingly, the best explicit construction of Ramsey graphs only guarantees the non-existence of a clique or independent set of size K=(log N)^{o(log log log N)}.

In this talk, I will describe a new construction of explicit two source extractors for asymptotically optimal entropy of k=O(log n), which gives explicit Ramsey graphs on N vertices with on clique or independent set of size K=log^c N for some absolute constant c>1.

08/25/2023
Geoffrey Mon, UT Austin
Relaxed Local Correctability from Local Testing

A relaxed locally correctable code is equipped with an algorithm that, when given query access to a (potentially corrupted) codeword and an index i, either returns the ith bit of the nearest codeword or detects corruption. We build the first asymptotically good relaxed locally correctable codes with polylogarithmic query complexity, which finally closes the superpolynomial gap between query lower and upper bounds.

Our construction makes use of locally testable codes, which have algorithms that probabilistically detect the presence of corruption with few queries. By combining high-rate locally testable codes of various sizes, we can produce a code with local testers at every scale: we can gradually "zoom in" to any desired codeword index i, and a local tester at each step certifies that the next, smaller restriction of the input has low error. If no local tester detects corruption throughout this process, then the ith bit of the input is likely not corrupt and can be safely returned.

Based on joint work with Vinayak M. Kumar.

09/01/2023
Kevin Tian, UT Austin
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory

Discrepancy theory provides powerful tools for producing higher-quality objects which “beat the union bound” in fundamental settings throughout combinatorics and computer science. However, this quality has often come at the price of more expensive algorithms. We introduce a new framework for bridging this gap, by allowing for the efficient implementation of discrepancy-theoretic primitives. Our framework repeatedly solves regularized optimization problems to low accuracy to approximate the partial coloring method of [Rothvoss ’17], and simplifies and generalizes recent work of [Jain-Sah-Sawhney ’23] on fast algorithms for Spencer’s theorem. In particular, our framework only requires that the discrepancy body of interest has exponentially large Gaussian measure and is expressible as a sub level set of a symmetric, convex function. We combine this framework with new tools for proving Gaussian measure lower bounds to give improved algorithms for a variety of sparsification and coloring problems.

Joint work with Arun Jambulapati and Victor Reis.

09/08/2023
Raghu Meka, UCLA 
Resolving Matrix Spencer Conjecture Up to poly-logarithmic Rank

The matrix Spencer conjecture is the following: given n symmetric matrices A1,..., An each of spectral norm at most 1, can we find signs for each of them such that their signed sum has spectral-norm at most O(sqrt{n}). If true, this would substantially generalize Spencer's 'Six standard deviations suffice' (a classical result in discrepancy theory). Spencer's result corresponds to the matrices Ai being diagonal.

In this talk, I will describe a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank, i.e., each matrix Ai has rank at most n/(log n)^3. Previously, the result was known only for rank sqrt(n). Our result also has implications for quantum random access codes in the low-error regime: in particular, it implies a (1*log n - 3*(log log n)) lower bound for quantum random access codes with an advantage of 1/sqrt(n).

Based on joint work with Nikhil Bansal and Haotian Jiang.

09/15/2023
Scott Aaronson, UT Austin / Open AI
Watermarking of Large Language Models

I'll survey the research that's been done over the last year, by me and others, into the problem of how to insert statistical watermarks into the outputs of Large Language Models, in order (for example) to help detect GPT-enabled academic cheating, propaganda campaigns, and fraud.  I'll explain how, by using pseudorandom functions, one can typically insert a watermark without degrading the quality of the LLM's output at all.  I'll highlight the theoretical computer science aspects of the problem, as well as the challenge of coming up with a watermarking scheme that resists rephrasing attacks, or even of formalizing what one means by that.  I'll also discuss some of the social and political issues around the deployment of LLM watermarking.

09/22/2023
Peter Manohar, Carnegie Mellon University
Lower Bounds for Locally Decodable Codes from Semirandom CSP Refutation

A code C is a q-locally decodable code (q-LDC) if one can recover any chosen bit b_i of the k-bit message b with good confidence by randomly querying the n-bit encoding x on at most q coordinates. Existing constructions of 2-LDCs achieve blocklength n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions have n = subexp(k), while the best known lower bounds, that have stood for nearly two decades, only show a quadratic lower bound of n >= \Omega(k^2) on the blocklength.

In this talk, we will showcase a new approach to prove lower bounds for LDCs using recent advances in refuting semirandom instances of constraint satisfaction problems. These new tools yield, in the 3-query case, a near-cubic lower bound of n >= \tilde{\Omega}(k^3), improving on the prior best lower bound of n >= \tilde{\Omega(k^2)} of Kerendis and de Wolf from 2004 by a polynomial factor in k.

10/06/2023
Ali Vakilian, TTIC
Algorithms for Socially Fair Clustering: Min-Max Fairness to Cascaded Norms

In the center-based clustering methods (e.g., k-means), the assignment cost of a point represents the quality of the clustering for the point. This has motivated a notion of min-max fairness for the clustering problem, also known as socially fair clustering: Select k centers that minimize the maximum average clustering cost incurred by any of the L pre-specified groups of points in the input. This problem can be used to select a set of vaccination or polling sites to ensure different communities in the population are served fairly.

In this talk, I present our O(log L/ log log L)-approximation for the problem, which exponentially improves over the previously known O(L)-approximation and is optimal up to a constant factor. Then, I introduce a generalization of the problem called (p, q)-fair clustering, i.e., clustering with cascaded norms. This is a “relaxed” way of enforcing the fairness requirement, and its objective interpolates between the objective of classic k-clustering and that of socially fair clustering.

10/13/2023
Keegan Ryan, USCD
Fast Practical Lattice Reduction through Iterated Compression

We introduce a new lattice basis reduction algorithm with approximation guarantees analogous to the LLL algorithm and practical performance that far exceeds the current state of the art. We achieve these results by iteratively applying precision management techniques within a recursive algorithm structure and show the stability of this approach. We analyze the asymptotic behavior of our algorithm for arbitrary basis matrices, and we show that the heuristic running time is small and comparable to the cost of performing size reduction, matrix multiplication, and QR factorization on similarly sized matrices. The heuristic running time of our algorithm depends on the log of the condition number of the input basis, which is bounded by the bit length of basis entries in common applications. Our algorithm is fully practical, and we have published our implementation. We experimentally validate our heuristic, give extensive benchmarks against numerous classes of cryptographic lattices, and show that our algorithm significantly outperforms existing implementations.

10/20/23
Aaron Potechin, University of Chicago
Separating MAX 2-AND, MAX DI-CUT and MAX CUT

In 2008, Raghavendra's paper "Optimal algorithms and inapproximability results for every CSP?" showed that assuming the Unique Games Conjecture (or at least that unique games is hard), for any CSP on a finite set of predicates, the optimal worst-case polynomial time approximation algorithm is to use a standard semidefinite program and then apply a rounding algorithm. However, since the set of potential rounding functions is extremely large, Raghavendra's result does not tell us what the approximation ratio is for a given CSP. In fact, there are still several basic questions which are still open. For example, the question of whether there is a 7/8 approximation ratio for MAX SAT (where the clauses can have any length) is still open.

In this talk, I will review Raghavendra's result and why additional work is needed to analyze particular CSPs. I will then describe why MAX 2-AND, MAX DI-CUT and MAX CUT all have different approximation ratios and how we can prove this.

This is joint work with Joshua Brakensiek, Neng Huang, and Uri Zwick

10/27/23
Lijie Chen, UC Berkeley
Polynomial -Time Pseudodeterministic Construction of Primes

A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. 

We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of n, B(1^n) outputs a canonical n-bit prime p_n with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q. This improves upon a subexponential-time construction of Oliveira and Santhanam. 

Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell, using a variant of the Shaltiel-Umans generator. This talk is based on joint work with Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam.

11/03/2023
Jesse Goodman, UT Austin
Exponentially Improved Extractors for Adversarial Sources

Randomness is a powerful resource in computer science, with applications in cryptography, distributed computing, algorithm design, and more. Unfortunately, almost all of these applications require access to perfectly uniform bits, while the bits available in nature rarely look so pure. This motivates the study of randomness extractors, which are devices that can convert weak sources of randomness into perfectly uniform bits.

The *independent source model* is the oldest and most well-studied setting in which to study randomness extraction. In this model, the goal is to extract uniform bits from a sequence of N independent random variables X1, …, XN, each with min-entropy at least k. However, in real life, natural sources of randomness may sometimes produce samples with no entropy at all. This motivates the study of *adversarial sources*, which are identical to independent sources, except that only K of them are guaranteed to be “good” (i.e., contain any min-entropy, k).

Adversarial sources were first introduced by Chattopadhyay, Goodman, Goyal and Li (STOC ‘20), who showed how to extract from just K ≥ N^{0.5} good sources of polylogarithmic entropy. In a follow-up work, Chattopadhyay and Goodman (FOCS ‘21) improved the number of required good sources to K ≥ N^{0.01}. In this talk, I will describe a new construction that works for *exponentially less* good sources K ≥ polylog(N). In fact, for any constant N (e.g., N = 10^82), our extractor requires just K = 4 of the sources to be good. To construct our extractors, we exploit old and new tools from communication complexity, extractor theory, and extremal combinatorics.

Based on joint work with Eshan Chattopadhyay.

11/10/2023
Greg Bodwin, University of Michigan
Recent Progress on Fault Tolerant Spanners

Given a large input graph, a k-spanner is a much smaller subgraph that preserves shortest path distances up to an approximation factor of k. When this distance approximation is robust to a bounded set of failing nodes or edges, the spanner is called fault tolerant.  Fault tolerant spanners and their relatives have applications in networking and distributed computing.

There has been a recent flurry of progress in our understanding of fault tolerant spanners, including faster construction algorithms and better tradeoffs between spanner size, error, and level of fault tolerance. We will survey this progress, spanning a sequence of 8 papers over the last 5 years. We will explain the new perspectives on the problem that have enabled progress, what has been solved, and what remains open.

11/17/2023
Thatchaphol Saranurak, University of Michigan
Using Isolating Mincuts for Fast Graph Algorithms: A Tutorial

The Isolating Mincuts algorithm is a new technique recently introduced by [Li and Panigrahi] and [Abboud Krauthgamer Trabelsi]. In the last three years, they found more than ten applications in fast graph algorithms.
I will give a gentle tutorial on this technique.

12/01/2023
Sivakanth Gopi, Microsoft Research
Higher Order MDS Codes and List Decoding

In this talk, we introduce 'higher order MDS codes', a fundamental generalization of MDS codes. An order-m MDS code, denoted by MDS(m), has the property that any m subspaces formed from columns of its generator matrix intersect as minimally as possible. Ordinary MDS codes correspond to m=2. We will then show that higher order MDS codes are equivalent to various seemingly unrelated concepts in coding theory: (1) optimally list-decodable codes (2) maximally recoverable tensor codes and (3) MDS codes with support constrained generator matrices (such as in GM-MDS theorem). This along with the GM-MDS theorem for Reed-Solomon codes implies that random Reed-Solomon codes over large enough alphabet are optimally list decodable.

This closes a long line of work on list-decodability of Reed-Solomon codes starting with the celebrated result of Guruswami and Sudan (1998) who showed that they are list-decodable up to the Johnson bound. Later works showed that "random" Reed-Solomon codes are list-decodable beyond the Johnson bound. We show that they in fact are optimally list-decodable! Quantitatively, we show that a random Reed-Solomon code of rate R over a large enough field is list decodable from radius 1-R-(1-R)/(L+1) with list size at most L, which proves a conjecture of Shangguan and Tamo (2020).

Subsequent work by Guo, Zhang (2023) and Alrabiah, Guruswami and Li (2023) showed that random RS codes over linear-sized fields achieve list-decoding capacity (which is weaker than optimal list-decoding). Building on this, we show that random AG codes over constant-sized fields achieve list-decoding capacity. For this, we prove a generalized GM-MDS theorem for algebraic codes.

Based on joint work with Joshua Brakensiek, Manik Dhar, Visu Makam and Zihan Zhang.

12/8/2023
 Jinyoung Park, Courant Institute of Mathematical Sciences NYU
Thresholds

For a finite set X, a family F of subsets of X is said to be increasing if any set A that contains B in F is also in F. The p-biased product measure of F increases as p increases from 0 to 1, and often exhibits a drastic change around a specific value, which is called a "threshold." Thresholds of increasing families have been of great historical interest and a central focus of the study of random discrete structures (e.g. random graphs and hypergraphs), with estimation of thresholds for specific properties the subject of some of the most challenging work in the area. In 2006, Jeff Kahn and Gil Kalai conjectured that a natural (and often easy to calculate) lower bound q(F) (which we refer to as the “expectation-threshold”) for the threshold is in fact never far from its actual value. A positive answer to this conjecture enables one to narrow down the location of thresholds for any increasing properties in a tiny window. In particular, this easily implies several previously very difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery). I will present recent progress on this topic. Based on joint work with Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Huy Tuan Pham.

01/13/2023 - Scott Aaronson, UT: Discrete Bulk Reconstruction
01/20/2023 - Robert Andrews, University of Illinois Urbana-Champaign: On Matrix Multiplication and Polynomial Identity Testing
01/27/2023 - William Kretschmer, UT: Quantum Cryptography in Algorithmica
02/03/2023 - David Zuckerman, UT: Almost Chor-Goldreich Sources and Adversarial Random Walks
02/10/2023 - Xiaoyu He, Princeton University: Deletion Code Bounds via Pseudorandomness
02/17/2023 - Jack Zhou, Stanford University: Quantum Pseudoentanglement
02/24/2023 - GRADFEST
03/03/2023 - Robert Tarjan, Princeton University - James S. McDonnell Distinguished University Professor: Self-Adjusting Data Structures **GDC 2.216 Lecture Hall**
03/10/2023 - Daniel Liang, UT: Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
03/17/2023 - SPRING BREAK
03/24/2023 - Vinod Vaikuntanathan, MIT: Continuous Learning with Errors and Applications: Gaussian Mixtures and Undetectable Backdoors ***11:00am-12:00pm***
03/27/2023 - Jelani Nelson, UC Berkeley: New local differentially private protocols for frequency and mean estimation ***POB 2.302 (Avaya Auditotrium) 1:00-2:00pm***
03/29/2023 - Marijn Heule, Carnegie Mellon: Computer-aided Mathematics: Successes, Advances, and Trust ***2:30-3:30pm***
03/31/2023 - Gregory Valiant, Stanford University: Optimization with Limited Memory?
04/07/2023 - Ruizhe Zhang, UT Austin: Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
04/14/2023 - Schuchi Chawla, UT Austin: Pandora's Box with Correlations: Learning and Approximation ***3:00-4:00pm***
04/21/2023 - ***CANCELLED***
04/28/2023 - FINALS
05/03/2023 - Yifeng Teng, Google Research: Prophet Secretary Against the Online Optimal
05/05/2023 - Raghu Meka, UCLA: Strong bounds for 3-progressions

01/13/2023
Scott Aaronson, UT
Discrete Bulk Reconstruction

According to the so-called "AdS/CFT correspondence" from quantum gravity, the geometries of certain spacetimes are fully determined by quantum states that live on their boundaries -- indeed, by the entropies of portions of those boundary states. This work investigates to what extent the geometries can be reconstructed from the entropies in polynomial time. Bouland, Fefferman, and Vazirani (2019) argued that the AdS/CFT map can be exponentially complex if one wants to reconstruct regions such as the interiors of black holes. Our main result provides a sort of converse: we show that, in the special case of a single 1D boundary, if the input data consists of a list of entropies of contiguous boundary regions, and if the entropies satisfy a single inequality called Strong Subadditivity, then we can construct a graph model for the bulk in linear time. Moreover, the bulk graph is planar, it has O(N^2) vertices (the information-theoretic minimum), and it's ``universal,'' with only the edge weights depending on the specific entropies in question. From a combinatorial perspective, our problem boils down to an ``inverse'' of the famous min-cut problem: rather than being given a graph and asked to find a min-cut, here we're given the values of min-cuts separating various sets of vertices, and we need to find a weighted undirected graph consistent with those values. We also make initial progress on the case of multiple 1D boundaries -- where the boundaries could be connected wormholes -- including an upper bound of O(N^4) vertices whenever a planar bulk graph exists, thus putting the problem into NP.

The talk is meant to be accessible to a CS theory audience, and assumes no particular knowledge of quantum gravity or even quantum mechanics.
Joint work with Jason Pollack (UT Austin)
https://arxiv.org/abs/2210.15601 
 

01/20/2023
Robert Andrews, University of Illinois Urbana-Champaign
On Matrix Multiplication and Polynomial Identity Testing

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that ω, the matrix multiplication exponent, equals 2. If true, this conjecture would yield fast algorithms for a wide array of problems in linear algebra and beyond. If instead ω > 2, can the hardness of matrix multiplication be leveraged to design algorithms for other problems? In this talk, I will describe how lower bounds on ω can be used to make progress on derandomizing polynomial identity testing. 

01/27/2023
William Kretschmer, UT
Quantum Cryptography in Algorithmica

In this talk, I will discuss the construction of a classical oracle relative to which P = NP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds, this is a construction of pseudorandom states in "Algorithmica," and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom quantum states, (2) holds for a random oracle, and thus plausibly holds for existing hash functions like SHA3, and (3) is independent of the P vs. NP question in the black box setting. This offers further evidence that one-way functions are not necessary for computationally-secure quantum cryptography. Our proof builds on recent work of Aaronson, Ingram, and Kretschmer (2022). Based on joint work with Luowen Qian, Makrand Sinha, and Avishay Tal.

02/03/2023
David Zuckerman, UT
Almost Chor-Goldreich Sources and Adversarial Random Walks

A Chor-Goldreich (CG) source is a sequence of random variables where each has min-entropy, even conditioned on the previous ones.  We extend this notion in several ways, most notably allowing each random variable to have Shannon entropy conditioned on previous ones.  We achieve pseudorandomness results for Shannon-CG sources that were not known to hold even for standard CG sources, and even for the weaker model of Santha-Vazirani sources.

Specifically, we construct a deterministic condenser that on input a Shannon-CG source, outputs a distribution that is close to having constant entropy gap, namely its min-entropy is only an additive constant less than its length.  Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a "one-shot" simulation is needed.  Moreover, our construction works in an online manner, since it is based on random walks on expanders.

Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders) accumulate entropy.

Joint work with Dean Doron, Dana Moshkovitz, and Justin Oh.

02/10/2023
Xiaoyu He, Princeton University
Deletion Code Bounds via Pseudorandomness

Deletion channels, introduced by Levenshtein in the 60's, are noisy channels that delete characters from the input. A (binary) k-deletion code of length n is a set C of binary strings of length n capable of correcting k such errors, i.e. satisfying the property that no pair of elements of C shares a common subsequence of length at least n-k. Let D(n, k) be the size of the largest k-deletion code of length n. Two central problems are to determine (a) the order of D(n, k) for constant k, and (b) the supremum of all 0<p<1 such that D(n, pn) grows exponentially in n (the so-called "zero-rate threshold"). In this talk, we establish the first nontrivial lower bound for problem (a) when k > 1, improving the greedy lower bound for D(n,k) by a logarithmic factor. We also prove the first nontrivial upper bound for problem (b), showing that D(n,pn) = 2^o(n) for p > 1/2 - 10^{-60}. The proofs use a variety of techniques from extremal and probabilistic combinatorics, especially pseudorandomness and a regularity lemma.

Based on joint works with Noga Alon, Gabriela Bourla, Ben Graham, Venkatesan Guruswami, Noah Kravitz, and Ray Li.

02/17/2023
Jack Zhou, Stanford University
Quantum Pseudoentanglement

Quantum pseudorandom states are efficiently constructable states which nevertheless masquerade as Haar-random states to poly-time observers. First defined by Ji, Liu and Song, such states have found a number of applications ranging from cryptography to the AdS/CFT correspondence. A fundamental question is exactly how much entanglement is required to create such states. Haar-random states, as well as t-designs for t≥2, exhibit near-maximal entanglement. Here we provide the first construction of pseudorandom states with only polylogarithmic entanglement entropy across an equipartition of the qubits, which is the minimum possible. Our construction can be based on any one-way function secure against quantum attack. We additionally show that the entanglement in our construction is fully "tunable", in the sense that one can have pseudorandom states with entanglement Θ(f(n)) for any desired function ω(logn)≤f(n)≤O(n). 

More fundamentally, our work calls into question to what extent entanglement is a "feelable" quantity of quantum systems. Inspired by recent work of Gheorghiu and Hoban, we define a new notion which we call "pseudoentanglement", which are ensembles of efficiently constructable quantum states which hide their entanglement entropy. We show such states exist in the strongest form possible while simultaneously being pseudorandom states. We also describe diverse applications of our result from entanglement distillation to property testing to quantum gravity.

03/03/2023
Robert Tarjan, Princeton University - James S. McDonnell Distinguished University Professor
Self-Adjusting Data Structures

Data structures are everywhere in computer software.  Classical data structures are specially designed to make each individual operation fast.  A more flexible approach is to design the structure so that it adapts to its use.  This idea has produced data structures that perform well in practice and have surprisingly good performance guarantees.  In this talk I’ll review some recent work on such data structures, specifically self-adjusting search trees and self-adjusting heaps.

Robert Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.  He has held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, HP, Microsoft, and Intertrust Technologies.  He has invented or co-invented many of the most efficient known data structures and graph algorithms.  He was awarded the first Nevanlinna Prize from the International Mathematical Union in 1982 for “for outstanding contributions to mathematical aspects of information science,” the Turing Award in 1986 with John Hopcroft for “fundamental achievements in the design and analysis of algorithms and data structures,” and the Paris Kanellakis Award in Theory and Practice in 1999 with Daniel Sleator for the invention of splay trees.  He is a member of the U.S. National Academy of Sciences, the U. S. National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society.

03/10/2023
Daniel Liang, UT
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Pseudorandom quantum states are a set of quantum states that are indistinguishable from a uniformly random (i.e. Haar random) quantum state. While they have been shown to be extremely useful for cryptographic purposes, a natural question is "what resources might be needed to construct them?" We attempt to answer the question relative to the Clifford + T gate set, a commonly used universal quantum gate. As the name implies, the T gate is the most expensive operation in this set and the number of T gates needed to create a state is often the most important measure. Our results are as follows: Given blackbox access to an n-qubit quantum state that is promised to be either (1) a state prepared with Clifford gates and at most t uses of the T gate or (2) a Haar random state, we give an algorithm that distinguishes between the two cases with probability at least 1-delta using at most O(exp(t) log(1/delta)) samples and O(n exp(t) log(1/delta)) time. As such, the number of T gates necessary for the construction of pseudorandom quantum states is strictly greater than O(log n). Our proofs expand on recent results by Gross, Nezami, and Walter (2021). Based on joint work with Sabee Grewal, Vishnu Iyer, and William Kretschmer.

03/24/2023
Vinod Vaikuntanathan, MIT
Continuous Learning with Errors and Applications: Gaussian Mixtures and Undetectable Backdoors

I will describe two results at the interface of statistics, machine learning and cryptography both of which build on the recently formulated continuous learning with errors (CLWE) problem.

First, I will show that CLWE is as hard as the widely studied (discrete) learning with errors (LWE) problem using techniques from leakage-resilient cryptography. In turn, I will use this to show the nearly optimal hardness of the long-studied Gaussian mixture learning problem.

Secondly, I will show an application of CLWE to machine learning. In the increasingly common setting where the training of models is outsourced, I will describe a method whereby a malicious trainer can use cryptography to insert an *undetectable* backdoor in a classifier. Using a secret key, the trainer can then slightly alter inputs to create large deviations in the model output. Without the secret key, the existence of the backdoor is hidden.

The talk is based on joint works with Shafi Goldwasser, Michael P. Kim and Or Zamir; and with Aparna Gupte and Neekon Vafa.

Vinod Vaikuntanathan is a professor of computer science at MIT, interested in cryptography and its applications across computer science. Vinod is the co-inventor of modern fully homomorphic encryption systems and many other lattice-based cryptographic primitives. He is a recipient of the Gödel Prize (2022), MIT Harold E. Edgerton Faculty Award (2018), DARPA Young Faculty Award (2018), the Sloan Faculty Fellowship (2013) and the Microsoft Faculty Fellowship (2014).

03/27/2023
Jelani Nelson, UC Berkeley
New local differentially private protocols for frequency and mean estimation

Consider the following examples of distributed applications: a texting app wants to train ML models for autocomplete based on text history residing on-device across millions of devices, or the developers of some other app want to understand common app settings by their users. In both cases, and many others, a third party wants to understand something in the aggregate about a large distributed database but under the constraint that each individual record requires some guarantee of privacy. Protocols satisfying so-called local differential privacy have become the gold standard for guaranteeing privacy in such situations, and in this talk I will discuss new such protocols for two of the most common problems that require solutions in this framework: frequency estimation, and mean estimation.

Based on joint works with subsets of Hilal Asi, Vitaly Feldman, Huy Le Nguyen, and Kunal Talwar.

Jelani Nelson is a Professor of Electrical Engineering and Computer Sciences at UC Berkeley, interested in randomized algorithms, sketching and streaming algorithms, dimensionality reduction, and differential privacy. He is a recipient of the Presidential Early Career Award for Scientist and Engineers (PECASE), and a Sloan Research Fellowship. He is also Founder and President of AddisCoder, Inc., a nonprofit that provides algorithms training to high school students in Ethiopia and Jamaica.

03/29/2023
Marijn Heule, Carnegie Mellon University 
Computer-aided Mathematics: Successes, Advances, and Trust

Progress in satisfiability (SAT) solving has made it possible to determine the correctness of complex systems and answer long-standing open questions in mathematics. The SAT-solving approach is completely automatic and can produce clever though potentially gigantic proofs. We can have confidence in the correctness of the answers because highly trustworthy systems can validate the underlying proofs regardless of their size.

We demonstrate the effectiveness of the SAT approach by presenting some successes, including the solution of the Boolean Pythagorean Triples problem, computing the fifth Schur number, and resolving the remaining case of Keller’s conjecture. Moreover, we constructed and validated proofs for each of these results. The second part of the talk focuses on notorious math challenges for which automated reasoning may well be suitable. In particular, we discuss advances in applying SAT-solving techniques to the Hadwiger-Nelson problem
(chromatic number of the plane), optimal schemes for matrix multiplication, and the Collatz conjecture.

Marijn Heule is an Associate Professor at Carnegie Mellon University and received his PhD at Delft University of Technology (2008). His contributions to automated reasoning have enabled him and others to solve hard problems in formal verification and mathematics. He has developed award-winning SAT solvers and his preprocessing and proof-producing techniques are used in many state-of-the-art solvers. Marijn won multiple best paper awards at international conferences, including at SAT, CADE, IJCAR, TACAS, HVC, and IJCAI-JAIR. He is one of the editors of the Handbook of Satisfiability. This 900+ page handbook has become the reference for SAT research.

03/31/2023
Gregory Valiant, Stanford University
Optimization with Limited Memory?

In many high-dimensional optimization settings, there are significant gaps between the amount of data or number of iterations required by algorithms whose memory usage scales linearly with the dimension versus more complex and memory-intensive algorithms.  Do some problems inherently require super-linear (or quadratic memory) to be solved efficiently? In this talk, we will survey the lay-of-the-land of fundamental tradeoffs between the amount of available memory, and the amount of data or queries to the function being optimized.  This will include a discussion of our recent work showing that for optimizing a convex function, given the ability to query the function value/gradient at points, a (significantly) super-linear amount of memory is required to achieve the optimal rate of convergence obtained by algorithms using more than quadratic memory.  Throughout, the emphasis will be on the many open problems in this area.

04/07/2023
Ruizhe Zhang, UT Austin
Solving SDP Faster: A Robust IPM Framework and Efficient Implementation

Semidefinite programming (SDP) is one of the most important tools in optimization theory. In this talk, I will introduce a new robust interior-point method analysis for SDP. Under this new framework, we can improve the running time of semidefinite programming (SDP) with variable size n×n and m constraints up to ϵ accuracy. For the case m=Ω(n^2), our algorithm can solve SDPs in m^ω time. This suggests solving SDP is nearly as fast as solving a linear system with equal number of variables and constraints. It is the first result that tall dense SDP can be solved in a nearly-optimal running time, and it also improves the state-of-the-art SDP solver [Jiang, Kathuria, Lee, Padmanabhan and Song, FOCS 2020]. In addition to our new IPM analysis, our algorithm also relies on a number of new techniques that might be of further interest, such as, maintaining the inverse of a Kronecker product using lazy updates, and a general amortization scheme for positive semidefinite matrices. Based on joint work with Baihe Huang, Shunhua Jiang, Zhao Song, and Runzhou Tao.

04/14/2023
Schuchi Chawla, UT Austin
Pandora's Box with Correlations: Learning and Approximation

In the Pandora's Box problem, the algorithm is provided with a number of boxes with unknown (stochastic) rewards contained inside them. The algorithm can open any box at some cost, discover the reward inside, and based on these observations can choose one box and keep the reward contained in it. Given the distributions from which the rewards are drawn, the algorithm must determine an order in which to open the boxes as well as when to stop and accept the best reward found so far. In general, an optimal algorithm may make both decisions adaptively based on instantiations observed previously. The Pandora's Box problem and its extensions capture many kinds of optimization problems with stochastic input where the algorithm can obtain instantiations of input random variables at some cost. Previous work on these problems assumes that the random variables are distributed independently. In this work, we consider Pandora's Box-type problems with correlations. Whereas the independent distributions setting is efficiently solvable, the correlated setting is hard and captures as special cases several algorithmic problems that have been studied previously -- e.g. min sum set cover and optimal decision tree. We provide the first approximation algorithms for the correlated setting under various distributional models. This talk is based on two papers with coauthors Evangelia Gergatsouli, Jeremy McMahan, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. The first appeared at FOCS'20 and the second is under preparation.

05/03/2023
Yifeng Teng, Google Research
Prophet Secretary Against the Online Optimal

In the prophet secretary problem, a sequence of random variables with independent known distributions arrive in uniformly random order. Upon seeing a realized value at each step, an online decision-maker has to either select it and stop or irrevocably discard it. The goal is to maximize the expected value of the selected variable. Traditionally, the chosen benchmark is the expected reward of the prophet, who knows all the values in advance and can always select the maximum one.

In this work, we study the prophet secretary problem against a less pessimistic but equally well-motivated benchmark; the online optimal. Here, the main goal is to find polynomial-time algorithms that guarantee near-optimal expected reward. As a warm-up, we present a quasi-polynomial time approximation scheme (QPTAS) through careful discretization and non-trivial bundling processes. Using the toolbox developed for the QPTAS, coupled with a novel frontloading technique that enables us to reduce the number of decisions we need to make, we are able to remove the dependence on the number of items in the exponent of the running time, and obtain the first polynomial time approximation scheme (PTAS) for this problem.

05/05/2023
Raghu Meka, UCLA
Strong bounds for 3-progressions

Suppose you have a set S of integers from \{1,2,\ldots,N\} that contains at least N / C elements. Then for large enough N , must S contain three equally spaced numbers (i.e., a 3-term arithmetic progression)?

In 1953, Roth showed that this is indeed the case when C > \Omega(\log \log N), while Behrend in 1946 showed that C can be at most 2^{O(\sqrt{\log N})}. Since then, the problem has been a cornerstone of the area of additive combinatorics. Following a series of remarkable results, a celebrated paper from 2020 due to Bloom and Sisask improved the lower bound on C to C = (\log N)^{1+c}, for some constant c > 0.

This talk will describe a new work that C >2^{\Omega((\log N)^{0.09})}, thus getting closer to Behrend's construction.

Based on joint work with Zander Kelley.

09/02/2022 - David Wu, UT: Batch Arguments for NP and More from Standard Bilinear Group Assumptions

09/09/2022 - Joe Neeman, UT

09/16/2022 - Chinmay Nirkhe, IBM Quantum

09/23/2022 - 

10/07/2022 - 

10/14/2022 - 

10/21/2022 - 

10/28/2022 - Nicole Wein, DIMACS

11/04/2022 - 

11/11/2022 - 

11/18/2022 - Huacheng Yu, Princeton

12/02/2022 - 

12/09/2022 - 



09/02/2022

David Wu, UT

Batch Arguments for NP and More from Standard Bilinear Group Assumptions



Non-interactive batch arguments for NP provide a way to amortize the cost of NP verification across multiple instances. They enable a computationally-bounded prover to convince a verifier of multiple NP statements with communication that is much smaller than the total witness length and with verification time that is smaller than individually checking each instance.



In this talk, I describe a new and direct approach for constructing batch arguments from standard cryptographic assumptions on groups with bilinear maps (e.g., the subgroup decision or the k-Lin assumption). Our approach avoids heavy tools like correlation-intractable hash functions or probabilistically-checkable proofs common to previous approaches. In turn, we also obtain the first construction of batch arguments for NP from standard bilinear map assumptions.



As corollaries to our main construction, we also obtain a delegation scheme for RAM programs (also known as a succinct non-interactive argument for P) as well as an aggregate signature scheme supporting bounded aggregation from standard bilinear map assumptions in the plain model.



Joint work with Brent Waters.

 

08/27/2021 - Alexandros Hollender, University of Oxford: The Complexity of Gradient Descent: CLS = PPAD ∩ PLS

09/03/2021 - Nathan Klein, University of Washington: A (Slightly) Improved Approximation Algorithm for Metric TSP

09/10/2021 - Vishesh Jain, Stanford University, Stein Fellow: Towards the Sampling Lovász Local Lemma

09/17/2021 - Seth Pettie, University of Michigan: Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon

10/01/2021 - Roei Tell, IAS+DIMACS: Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

10/08/2021 - Eric Vigoda, UCSB: Computational Phase Transition for Approximate Counting

10/15/2021 - Srikanth Srinivasan, Aarhus University: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

10/22/2021 - Amnon Ta-Shma, Tel-Aviv University: Expander Random Walks: A Fourier-Analytic Approach

11/05/2021 -  Joe Neeman, UT Austin: Robust Testing of Low-Dimensional Functions *Hybrid Event: To be hosted virtually and in person in GDC 4.304*

11/12/2021 - Virgina Williams, MIT: Hardness of Approximate Diameter: Now for Undirected Graphs

11/19/2021 -  Minshen Zhu, Purdue University: Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions * Event Begins at 11:00 AM*

12/03/2021 - Shai Evra, Hebrew University of Jerusalem: Locally Testable Codes with Constant Rate, Distance, and Locality



08/27/2021

Alexandros Hollender, University of Oxford

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS



We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain [0,1]2 is PPAD ∩ PLS-complete. This is the first natural problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more "natural" counterpart to PPAD ∩ PLS and contains many interesting problems - is itself equal to PPAD ∩ PLS.



09/03/2021

Nathan Klein, University of Washington

A (Slightly) Improved Approximation Algorithm for Metric TSP



I will describe work in which we obtain a 3/2-epsilon approximation algorithm for metric TSP, for some epsilon>10^{-36}. This slightly improves over the classical 3/2 approximation algorithm due to Christofides [1976] and Serdyukov [1978]. The talk will focus on giving an overview of the key ideas involved, such as properties of Strongly Rayleigh distributions and the structure of near minimum cuts. This is joint work with Anna Karlin and Shayan Oveis Gharan. 



09/10/2021

Vishesh Jain, Stanford University, Stein Fellow

Towards the Sampling Lovász Local Lemma



For a constraint satisfaction problem which satisfies the condition of the Lovász local lemma (LLL), the celebrated algorithm of Moser and Tardos allows one to efficiently find a satisfying assignment. In the past few years, much work has gone into understanding whether one can efficiently sample from (approximately) the uniform distribution on satisfying assignments under LLL-like conditions. I will discuss recent progress on this problem, joint with Huy Tuan Pham (Stanford) and Thuy Duong Vuong (Stanford).



09/17/2021

Seth Pettie, University of Michigan

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon



Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching, dating back to Flajolet and Martin's classic Probabilistic Counting (PCSA) algorithm from 1983. In this paper we study the intrinsic tradeoff between the space complexity of the sketch and its estimation error in the random oracle model. We define a new measure of efficiency for cardinality estimators called the Fisher-Shannon (Fish) number H/I. It captures the tension between the limiting Shannon entropy (H) of the sketch and its normalized Fisher information (I), which characterizes the variance of a statistically efficient, asymptotically unbiased estimator.



Our results are as follows:

• We prove that all base-q variants of Flajolet and Martin's PCSA sketch have Fish-number H0/I0≈1.98016 and that every base-q variant of (Hyper)LogLog has Fish-number worse than H0/I0, but that they tend to H0/I0 in the limit as q→∞. Here H0,I0 are precisely defined constants.

• We describe a sketch called Fishmonger that is based on a smoothed, entropy-compressed variant of PCSA with a different estimator function. It is proved that with high probability, Fishmonger processes a multiset of [U] such that at all times, its space is O(log2logU)+(1+o(1))(H0/I0)b≈1.98b bits and its standard error is 1/sqrt(b).

We give circumstantial evidence that H0/I0 is the optimum Fish-number of mergeable sketches for Cardinality Estimation. We define a class of linearizable sketches and prove that no member of this class can beat H0/I0. The popular mergeable sketches are, in fact, also linearizable.



10/01/2021

Roei Tell, IAS+DIMACS

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

Textbook hardness-to-randomness converts circuit lower bounds into PRGs. But is this black-box approach really necessary for derandomization? In this talk I'll show how to revamp the classical hardness-to-randomness framework, converting new types of *uniform lower bounds* into *non-black-box derandomization*. This yields conclusions such as promiseBPP = promiseP without PRGs, and reveals a close connection between worst-case derandomization and the new types of uniform lower bounds. Another instantiation of this new framework allows to deduce, under plausible hypotheses, that randomness can be eliminated at essentially no observable cost when solving decision problems.

Based on joint work with Lijie Chen.



10/08/2021

Eric Vigoda, UCSB

Computational Phase Transition for Approximate Counting



Spectral independence is a new technique, recently introduced by Anari et al (2020), for establishing rapid mixing results for Markov Chain Monte Carlo (MCMC) algorithms. We show that spectral independence implies optimal convergence rate for a variety of MCMC algorithms. This yields a dramatic computational phase transition for various approximate counting problems such as weighted independent sets.



This talk is based on joint works with Zongchen Chen (MIT) and Kuikui Liu (Washington).



10/15/2021

Srikanth Srinivasan, Aarhus University

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits



Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants. In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P.



What happens if we add another layer of complexity, and consider sums of products of sums (of variables and field constants) expressions? Now, it becomes unclear how to prove that a given polynomial P(x_1,...,x_n) does not have small expressions. In this result, we solve exactly this problem.

More precisely, we prove that certain explicit polynomials have no polynomial-sized "Sigma-Pi-Sigma" (sums of products of sums) representations. We can also show similar results for Sigma-Pi-Sigma-Pi, Sigma-Pi-Sigma-Pi-Sigma and so on for all "constant-depth" expressions.



Based on joint work with Nutan Limaye (ITU Copenhagen + IIT Bombay) and Sébastien Tavenas (USMB + Univ. Grenoble, CNRS).



10/22/2021

Amnon Ta-Shma, Tel-Aviv University

Expander Random Walks: A Fourier-Analytic Approach



We consider the following question: Assume the vertices of an expander graph are labelled by {1,-1}. What test functions can or cannot distinguish t independent samples from those obtained by a random walk?



We prove all symmetric functions are fooled by random walks on expanders with constant spectral gap. We use Fourier analysis noticing that the bias of character $\chi_S$  is determined not only by the cardinality of S, but also by the distances between the elements in S.



The talk is based on two papers:

- Expander Random Walks: A Fourier-Analytic Approach with Gil Cohen and Noam Peri, and,

- Expander Random Walks: The General Case and Limitations with Gil Cohen, Dor Minzer, Shir Peleg and Aaron Potechin.



11/05/2021

Joe Neeman, UT Austin

Robust Testing of Low-Dimensional Functions  *Hybrid Event: To be hosted virtually and in person in GDC 4.304*



A natural problem in high-dimensional inference is to decide if a classifier f:Rn→{−1,1} depends on a small number of linear directions of its input data. Call a function g:Rn→{−1,1}, a linear k-junta if it is completely determined by some k-dimensional subspace of the input space. A recent work of the authors showed that linear k-juntas are testable. Thus there exists an algorithm to distinguish between: 1. f:Rn→{−1,1} which is a linear k-junta with surface area s, 2. f is ϵ-far from any linear k-junta with surface area (1+ϵ)s, where the query complexity of the algorithm is independent of the ambient dimension n.



Following the surge of interest in noise-tolerant property testing, in this paper we prove a noise-tolerant (or robust) version of this result. Namely, we give an algorithm which given any c>0, ϵ>0, distinguishes between 1. f:Rn→{−1,1} has correlation at least c with some linear k-junta with surface area s. 2. f has correlation at most c−ϵ with any linear k-junta with surface area at most s. The query complexity of our tester is kpoly(s/ϵ).



Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class C of linear k-juntas with surface area bounded by s. As a consequence, we obtain a fully noise tolerant tester with query complexity kO(poly(logk/ϵ)) for the class of intersection of k-halfspaces (for constant k) over the Gaussian space. Our query complexity is independent of the ambient dimension n. Previously, no non-trivial noise tolerant testers were known even for a single halfspace.



11/12/2021

Virgina Williams, MIT

Hardness of Approximate Diameter: Now for Undirected Graphs



Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time.



A series of papers on fine-grained complexity have led to strong hardness results for diameter, culminating in our recent tradeoff curve in the upcoming FOCS'21 joint with Ray Li and Mina Dalirrooyfard, showing that under the Strong Exponential Time Hypothesis (SETH), for any integer k≥2 and δ>0, a 2−1/k−δ approximation for diameter in m-edge graphs requires mn^{1+1/(k−1)−o(1)} time. In particular, the simple linear time 2-approximation algorithm is optimal.



In this talk I will give an overview of the known algorithms and fine-grained lower bounds for diameter, including the SETH-based optimality of the 2-approximation algorithm.



11/19/2021

Minshen Zhu, Purdue University

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions * Event Begins at 11:00 AM*



Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have been studied extensively in the past few decades, where a major goal is to understand the amount of redundancy that is necessary and sufficient to decode from large amounts of error, with small query complexity. Despite exciting progress, we still don’t have satisfactory answers in several important parameter regimes. For example, in the case of 3-query LDCs, the gap between existing constructions and lower bounds is superpolynomial in the message length. In this work we study LDCs for insertion and deletion errors, called Insdel LDCs. Their study was initiated by Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015), who gave a reduction from Hamming LDCs to Insdel LDCs with a small blowup in the code parameters. On the other hand, the only known lower bounds for Insdel LDCs come from those for Hamming LDCs, thus there is no separation between them. Here we prove new, strong lower bounds for the existence of Insdel LDCs. In particular, we show that 2-query linear Insdel LDCs do not exist, and give an exponential lower bound for the length of all q-query Insdel LDCs with constant q. For q ≥ 3 our bounds are exponential in the existing lower bounds for Hamming LDCs. Furthermore, our exponential lower bounds continue to hold for adaptive decoders, and even in private-key settings where the encoder and decoder share secret randomness. This exhibits a strict separation between Hamming LDCs and Insdel LDCs. Our strong lower bounds also hold for the related notion of Insdel LCCs (except in the private-key setting), due to an analogue to the Insdel notions of a reduction from Hamming LCCs to LDCs. Our techniques are based on a delicate design and analysis of hard distributions of insertion and deletion errors, which depart significantly from typical techniques used in analyzing Hamming LDCs .



12/03/2021

Shai Evra, Hebrew University of Jerusalem

Locally Testable Codes with Constant Rate, Distance, and Locality

A locally testable code (LTC) is an error correcting code that has a property-tester. The tester reads q bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter q is called the locality of the tester.



LTCs were initially studied as important components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code.

An outstanding open question has been whether there exist "c3-LTCs", namely LTCs with *c*onstant rate, *c*onstant distance, and *c*onstant locality.



In this work we construct such codes based on a new two-dimensional complex which we call a left-right Cayley complex. This is essentially a graph which, in addition to vertices and edges, also has squares. Our codes can be viewed as a two-dimensional version of (the one-dimensional) expander codes, where the codewords are functions on the squares rather than on the edges.