Fall 2023
Fall 2023 Theory Seminars will meet on Fridays from 11:00 am  12:00 pm in POB 2.402. This schedule will be updated throughout the semester.
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:00am12:00pm***
08/25/2023  Geoffrey Mon, UT Austin: Relaxed Local Correctability from Local Testing
09/01/2023  Kevin Tian, UT Austin: LinearSized Sparsifiers via NearLinear Time Discrepancy Theory
09/08/2023  Raghu Meka, UCLA: Resolving Matrix Spencer Conjecture Up to polylogarithmic 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: MinMax 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
10/27/2023  Lijie Chen, UC Berkeley
11/03/2023  Jesse Goodman, UT Austin
11/10/2023  Greg Bodwin , University of Michigan: Recent Progress on Fault Tolerant Spanners
11/17/2023  Thatchaphol Saranurak, University of Michigan
11/24/2023  THANKSGIVING HOLIDAY
12/01/2023  Sivakanth Gopi, Microsoft Research
12/08/2023  Jinyoung Park, Courant Institute of Mathematical Sciences NYU
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 socalled 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 nonexistence 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 highrate 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
LinearSized Sparsifiers via NearLinear Time Discrepancy Theory
Discrepancy theory provides powerful tools for producing higherquality 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 discrepancytheoretic 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 [JainSahSawhney ’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 polylogarithmic 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 spectralnorm 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 polylogarithmic 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 lowerror 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 GPTenabled 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 qlocally decodable code (qLDC) if one can recover any chosen bit b_i of the kbit message b with good confidence by randomly querying the nbit encoding x on at most q coordinates. Existing constructions of 2LDCs 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 3query case, a nearcubic 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: MinMax Fairness to Cascaded Norms
In the centerbased clustering methods (e.g., kmeans), the assignment cost of a point represents the quality of the clustering for the point. This has motivated a notion of minmax 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 prespecified 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 kclustering 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.
11/10/2023
Greg Bodwin, University of Michigan
Recent Progress on Fault Tolerant Spanners
Given a large input graph, a kspanner 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.
Spring 2023
Spring 2023 Theory Seminars will meet on Fridays from 2:00  3:00 pm in GDC 4.304. This schedule will be updated throughout the semester.
01/13/2023  Scott Aaronson, UT: Discrete Bulk Reconstruction
01/20/2023  Robert Andrews, University of Illinois UrbanaChampaign: On Matrix Multiplication and Polynomial Identity Testing
01/27/2023  William Kretschmer, UT: Quantum Cryptography in Algorithmica
02/03/2023  David Zuckerman, UT: Almost ChorGoldreich 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: SelfAdjusting Data Structures **GDC 2.216 Lecture Hall**
03/10/2023  Daniel Liang, UT: LowStabilizerComplexity 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:00am12:00pm***
03/27/2023  Jelani Nelson, UC Berkeley: New local differentially private protocols for frequency and mean estimation ***POB 2.302 (Avaya Auditotrium) 1:002:00pm***
03/29/2023  Marijn Heule, Carnegie Mellon: Computeraided Mathematics: Successes, Advances, and Trust ***2:303: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:004: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 3progressions
01/13/2023
Scott Aaronson, UT
Discrete Bulk Reconstruction
According to the socalled "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 informationtheoretic 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 mincut problem: rather than being given a graph and asked to find a mincut, here we're given the values of mincuts 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 UrbanaChampaign
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 singlecopy 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 blackbox setting, quantum cryptography based on pseudorandom states is possible even if oneway 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 oneway functions are not necessary for computationallysecure 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 ChorGoldreich Sources and Adversarial Random Walks
A ChorGoldreich (CG) source is a sequence of random variables where each has minentropy, 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 ShannonCG sources that were not known to hold even for standard CG sources, and even for the weaker model of SanthaVazirani sources.
Specifically, we construct a deterministic condenser that on input a ShannonCG source, outputs a distribution that is close to having constant entropy gap, namely its minentropy 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 "oneshot" 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 entropydeficient, 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) kdeletion 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 nk. Let D(n, k) be the size of the largest kdeletion 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 socalled "zerorate 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 Haarrandom states to polytime 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. Haarrandom states, as well as tdesigns for t≥2, exhibit nearmaximal 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 oneway 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
SelfAdjusting 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 selfadjusting search trees and selfadjusting 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 coinvented 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
LowStabilizerComplexity 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 nqubit 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 1delta 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 leakageresilient cryptography. In turn, I will use this to show the nearly optimal hardness of the longstudied 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 coinventor of modern fully homomorphic encryption systems and many other latticebased 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 ondevice 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 socalled 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
Computeraided Mathematics: Successes, Advances, and Trust
Progress in satisfiability (SAT) solving has made it possible to determine the correctness of complex systems and answer longstanding open questions in mathematics. The SATsolving 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 SATsolving techniques to the HadwigerNelson 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 awardwinning SAT solvers and his preprocessing and proofproducing techniques are used in many stateoftheart solvers. Marijn won multiple best paper awards at international conferences, including at SAT, CADE, IJCAR, TACAS, HVC, and IJCAIJAIR. 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 highdimensional 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 memoryintensive algorithms. Do some problems inherently require superlinear (or quadratic memory) to be solved efficiently? In this talk, we will survey the layoftheland 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) superlinear 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 interiorpoint 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 nearlyoptimal running time, and it also improves the stateoftheart 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 Boxtype 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 decisionmaker 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 wellmotivated benchmark; the online optimal. Here, the main goal is to find polynomialtime algorithms that guarantee nearoptimal expected reward. As a warmup, we present a quasipolynomial time approximation scheme (QPTAS) through careful discretization and nontrivial 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 3progressions
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 3term 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.
Fall 2022
Fall 2022 Theory Seminars will meet on Fridays from 1:45  2:45 pm in GDC 4.302. This schedule will be updated throughout the semester.
09/02/2022  David Wu, UT: Batch Arguments for NP and More from Standard Bilinear Group Assumptions
09/09/2022  Joe Neeman, UT: Bubble Clusters in Geometry and Computer Science
09/16/2022  Chinmay Nirkhe, IBM Quantum: NLTS Hamiltonians from Good Quantum Codes
09/23/2022  Sam Hopkins, MIT: Matrix Discrepancy from Quantum Communication **BEGINS AT 1:45 PM**
10/14/2022  Danupon Nanogkai, Max Planck Institute for Informatics: NegativeWeight SingleSource Shortest Paths in Near Linear Time
10/21/2022  Pravesh Kothari, CMU: The Kikuchi Matrix Method
10/28/2022  Nicole Wein, DIMACS: Closing the Gap Between Directed Hopsets and Shortcut Sets
11/04/2022  Shuichi Hirahara, National Institute of Informatics, Tokyo, Japan: NP Hardness of Learning Programs and Partial MCSP
11/11/2022  Nikhil Bansal, University of Michigan: The Power of Two Choices for Balls into Bins: Beyond Greedy Strategies
11/18/2022  Huacheng Yu, Princeton: Strong XOR Lemma for Communication with Bounded Rounds
12/02/2022 
12/09/2022 
09/02/2022
David Wu, UT
Batch Arguments for NP and More from Standard Bilinear Group Assumptions
Noninteractive batch arguments for NP provide a way to amortize the cost of NP verification across multiple instances. They enable a computationallybounded 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 kLin assumption). Our approach avoids heavy tools like correlationintractable hash functions or probabilisticallycheckable 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 noninteractive 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.
09/09/2022
Joe Neeman, UT
Bubble Clusters in Geometry and Computer Science
On the plane, a circle is the smallestperimeter shape with a given area. In three (and higher) dimensions, it's a sphere. Now what if you want to enclose two (or more) given areas using a minimal perimeter? You can do better than two circles, because if you smoosh two circles together then you can reuse part of the perimeter for both shapes. For two sets, the problem (known as the "double bubble conjecture") was solved about 20 years ago.
I'll talk about some recent progress in this area (joint work with E. Milman), some open problems, and the relevance of all this to computer science.
09/16/2022
Chinmay Nirkhe, IBM Quantum
NLTS Hamiltonians from Good Quantum Codes
The quantum PCP conjecture is one of the central open questions in quantum complexity theory. It asserts that calculating even a rough approximation to the ground energy of a local Hamiltonian is intractable even for quantum devices. The widely believed separation between the complexity classes NP and QMA necessitates that polynomial length classical proofs do not exist for calculating the ground energy. This further implies that lowenergy states of local Hamiltonians cannot be described by constant depth quantum circuits.
The ``No lowenergy trivial states (NLTS)'' conjecture by Freedman and Hastings posited the existence of such Hamiltonians. This talk will describe a line of research culminating in a proof of the NLTS conjecture by Anshu, Breuckmann, and Nirkhe. The construction is based on quantum error correction and in the talk, I will elaborate on how error correction, local Hamiltonians, and lowdepth quantum circuits are related.
09/23/2022 **BEGINS AT 1:45 PM**
Sam Hopkins, MIT
Matrix Discrepancy from Quantum Communication
Discrepancy is the mathematical study of balance; it has broad applications across TCS. For example, given vectors v_1,...,v_n \in R^m, one may ask how well they may be split into two groups S and barS to minimize  \sum_{i \in S} v_i  \sum_{i \in barS} v_i , where ... is some norm. Spencer's famous result, "6 standard deviations suffice", gives essentially a full characterization in the setting that the v_i's are bounded in infinity norm and ... is itself the infinity norm. A natural question, the "Matrix Spencer Conjecture", asks for a noncommutative version of this picture: can matrices be balanced as well as vectors can? This question has eluded much progress despite substantial attention in the last 10 years.
In this talk I will describe a new communicationbased perspective on discrepancy theory, showing that discrepancy upper bounds (i.e., theorems saying that a certain amount of balance is always possible) are actually equivalent to communication lower bounds (i.e. theorems saying that certain communication problems lack efficient protocols). This perspective opens a line of attack on the Matrix Spencer conjecture, via a lowerbounds problem in quantum communication which is of independent interest. In the talk (time permitting), I will show a new proof of Spencer's theorem via communication lower bounds, and I will describe how that proof can be generalized to prove a special case of the Matrix Spencer Conjecture, where the matrices to be balanced have polynomiallysmall rank.
Based on joint work with Prasad Raghavendra and Abhishek Shetty.
10/14/2022
Danupon Nanogkai, Max Planck Institute for Informatics
NegativeWeight SingleSource Shortest Paths in NearLinear Time
Watch a video of this seminar
We present a randomized algorithm that computes singlesource shortest paths (SSSP) in O(m log^8(n) log W) time when edge weights are integral and can be negative and are >=W. This essentially resolves the classic negativeweight SSSP problem. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. (Based on a FOCS 2022 paper with Aaron Bernstein and Christian WulffNilsen.)
10/21/2022
Pravesh Kothari, CMU
The Kikuchi Matrix Method
Watch a video of this seminar
In this talk, I will present a new method that reduces understanding an appropriate notion of girth in hypergraphs to unraveling the spectrum of a "Kikuchi" matrix associated with the hypergraph.
I will discuss three applications of this technique:
 Finding a refutation algorithm for smoothed instances of constraint satisfaction problems (obtained by randomly perturbing the literal patterns in a worstcase instance with a small probability) that matches the best runningtime vs constraintdensity tradeoffs for the significantly special and easier case of random CSPs,
 Confirming Feige's 2008 Conjecture that postulated an extremal girth vs density tradeoff (a.k.a. Moore bounds) for kuniform hypergraphs that generalizes the AlonHooryLinial Moore bound for graphs,
 Proving a cubic lower bound on the block length of 3 query locally decodable codes improving on the prior best quadratic lower bound from the early 2000s.
Based on joint works with Omar Alrabiyah (Berkeley), Tim Hsieh (CMU), Peter Manohar (CMU), Sidhanth Mohanty (Berkeley), and Venkat Guruswami (Berkeley).
10/28/2022
Nicole Wein, DIMACS
Closing the Gap Between Directed Hopsets and Shortcut Sets
Watch a video of this seminar
A shortcut set is a (small) set of edges that when added to a directed graph G produces a graph with the same transitive closure as G while reducing the diameter as much as possible. A hopset is defined similarly but for approximate distances instead of reachability. One motivation for such structures is that in many settings (e.g. distributed, parallel, dynamic, streaming), computation is faster when the diameter of the graph is small. Thus, to compute, for instance, streachability in such a setting, it is useful to find a shortcut set as a preprocessing step, and then run an streachability algorithm on the resulting graph.
This talk is about existential bounds for shortcut sets and hopsets: given a budget of ~O(n) added edges, what is the smallest diameter achievable? A folklore algorithm says that diameter O(n^{1/2}) is possible for any graph. A recent breakthrough of Kogan and Parter improves this to O(n^{1/3}) for shortcut sets and O(n^{2/5}) for hopsets. In recent work, we ask whether hopsets (approximate distances) are truly harder than shortcut sets (reachability). We close the gap between hopsets and shortcut sets by providing an O(n^{1/3})diameter construction for hopsets.
Based on joint work with Aaron Bernstein.
11/04/2022
Shuichi Hirahara, National Institute of Informatics, Tokyo, Japan
NP Hardness of Learning Programs and Partial MCSP
Watch a video of this seminar
In his seminal paper on the theory of NPcompleteness, Leonid Levin proved NPhardness of the partial function version of the Minimum DNF Size Problem in 1973, but delayed his publication because he hoped to extend it to NPhardness of the Minimum Circuit Size Problem (MCSP). In this talk, we prove NPhardness of the partial function version of MCSP. Our proofs are inspired by NPhardness of learning programs, the question posed by KerI Ko in 1990.
11/11/2022
Nikhil Bansal, University of Michigan
The Power of Two Choices for Balls into Bins: Beyond Greedy Strategies
In the classical twochoice process for assigning balls into bins, each ball chooses two bins uniformly at random and is placed greedily in the least loaded of the two bins. This poweroftwochoices paradigm has been highly influential and leads to substantially better load balancing than a random assignment of balls into bins.
Somewhat surprisingly, the greedy strategy turns out to be quite suboptimal for some natural generalizations. One such setting is the graphical process where the bins correspond to the vertices of a graph G, and at any time a random edge is picked and a ball must be assigned to one of its endpoints. Another setting is where the balls can also be deleted arbitrarily by an oblivious adversary. In this talk we will see why the greedy strategy can perform poorly, and I will describe other strategies for these settings that are close to optimal.
Based on joint works with Ohad Feldheim and William Kuszmaul.
11/18/2022
Huacheng Yu, Princeton
Strong XOR Lemma for Communication with Bounded Rounds
In this talk, we show a strong XOR lemma for boundedround twoplayer randomized communication. For a function f:X×Y→{0,1}, the nfold XOR function f^⊕n:X^n×Y^n→{0,1} maps n input pairs (x_1,...,x_n), (y_1,...,y_n) to the XOR of the n output bits f(x_1,y_1)⊕...⊕f(x_n, y_n). We prove that if every rround communication protocols that computes f with probability 2/3 uses at least C bits of communication, then any rround protocol that computes f^⊕n with probability 1/2+exp(O(n)) must use n(r^{O (r)}C1) bits. When r is a constant and C is sufficiently large, this is Omega(nC) bits. It matches the communication cost and the success probability of the trivial protocol that computes the n bits f(x_i,y_i) independently and outputs their XOR, up to a constant factor in n.
A similar XOR lemma has been proved for f whose communication lower bound can be obtained via bounding the discrepancy [Shaltiel03]. By the equivalence between the discrepancy and the correlation with 2bit communication protocols, our new XOR lemma implies the previous result.
Spring 2022
02/18/2022  Oliver Korten, Columbia: The Hardest Explicit Construction
03/11/2022  Matthew Ferland, USC: Winning the War by (Strategically) Losing Battles: Settling the Complexity of GrundyValues in Undirected Geography
03/25/2022  Lisa Sauermann, MIT: Listdecoding for ReedSolomon codes
04/01/2022  Kevin Tian, Stanford University: SemiRandom Sparse Recovery in NearlyLinear Time
04/08/2022  Debmalya Panigrahi, Duke University: Recent Results in Minimum Cut Algorithms
04/15/2022  William Hoza, Simons Institute: Fooling ConstantDepth Threshold Circuits
04/22/2022  Sushant Sachdeva, University of Toronto: Almost Linear Time Algorithms for MaxFlow and More
04/29/2022  John Kallaugher, Sandia National Laboratories: A Quantum Advantage for a Natural Streaming Problem **HYBRID EVENT in GDC 4.304  Event will begin at 2:00PM.**
05/06/2022  Dean Doron, BenGurion University: Approximating Large Powers of Stochastic Matrices in Small Space
[Anchor] 02/18/2022
Oliver Korten, Columbia
The Hardest Explicit Construction
We investigate the complexity of explicit construction problems, where the goal is to produce a particular object of size n possessing some pseudorandom property in time polynomial in n. We give overwhelming evidence that APEPP, defined originally by Kleinberg et al., is the natural complexity class associated with explicit constructions of objects whose existence follows from the probabilistic method, by placing a variety of such construction problems in this class. We then demonstrate that a result of Jeřábek on provability in Bounded Arithmetic, when reinterpreted as a reduction between search problems, shows that constructing a truth table of high circuit complexity is complete for APEPP under PNP reductions. This illustrates that Shannon's classical proof of the existence of hard boolean functions is in fact a universal probabilistic existence argument: derandomizing his proof implies a generic derandomization of the probabilistic method. As a corollary, we prove that EXPNP contains a language of circuit complexity 2^n^Ω(1) if and only if it contains a language of circuit complexity 2^n/2n. Finally, for several of the problems shown to lie in APEPP, we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.
[Anchor] 03/11/2022
Matthew Ferland, USC
Winning the War by (Strategically) Losing Battles: Settling the Complexity of GrundyValues in Undirected Geography
We settle two longstanding complexitytheoretical questionsopen since 1981 and 1993in combinatorial game theory (CGT).
We prove that the Grundy value (a.k.a. nimvalue, or nimber) of Undirected Geography is PSPACEcomplete to compute. This exhibits a stark contrast with a result from 1993 that Undirected Geography is polynomialtime solvable. By distilling to a simple reduction, our proof further establishes a dichotomy theorem, providing a "phase transition to intractability" in Grundyvalue computation, sharply characterized by a maximum degree of four: The Grundy value of Undirected Geography over any degreethree graph is polynomialtime computable, but over degreefour graphseven when planar and bipartiteis PSPACEhard. Additionally, we show, for the first time, how to construct Undirected Geography instances with Grundy value ∗n and size polynomial in n.
We strengthen a result from 1981 showing that sums of tractable partisan games are PSPACEcomplete in two fundamental ways. First, since Undirected Geography is an impartial ruleset, we extend the hardness of sums to impartial games, a strict subset of partisan. Second, the 1981 construction is not built from a natural ruleset, instead using a long sum of tailored shortdepth game positions. We use the sum of two Undirected Geography positions to create our hard instances. Our result also has computational implications to SpragueGrundy Theory (1930s) which shows that the Grundy value of the disjunctive sum of any two impartial games can be computedin polynomial timefrom their Grundy values. In contrast, we prove that assuming PSPACE ≠ P, there is no general polynomialtime method to summarize two polynomialtime solvable impartial games to efficiently solve their disjunctive sum.
[Anchor] 03/25/2022
Lisa Sauermann, MIT
Listdecoding for ReedSolomon codes
ReedSolomon codes are an important and intensively studied class of errorcorrecting codes. After giving some background, this talk will discuss the socalled listdecoding problem for ReedSolomon codes. More specifically, we prove that for any fixed listdecoding parameters, there exist ReedSolomon codes with a certain rate, which is optimal up to a constant factor. This in particular answers a question of Guo, Li, Shangguan, Tamo, and Wootters about listdecodability of ReedSolomon codes with radius close to 1. Joint work with Asaf Ferber and Matthew Kwan.
[Anchor] 04/01/2022
Kevin Tian, Stanford University
SemiRandom Sparse Recovery in NearlyLinear Time
Sparse recovery is one of the most fundamental and wellstudied inverse problems. Standard statistical formulations of the problem are provably solved by general convex programming techniques and more practical, fast (nearlylinear time) iterative methods. However, these latter "fast algorithms" have previously been observed to be brittle in various realworld settings.
We investigate the brittleness of fast sparse recovery algorithms to generative model changes through the lens of studying their robustness to a "helpful" semirandom adversary, a framework which tests whether an algorithm overfits to input assumptions. We consider the following basic model: let A be an nxd measurement matrix which contains an unknown mxd subset of rows G which are bounded and satisfy the restricted isometry property (RIP), but is otherwise arbitrary. Letting x* in R^d be ssparse, and given either exact measurements b = Ax* or noisy measurements b = Ax* + xi, we design algorithms recovering x* informationtheoretically optimally in nearlylinear time. We extend our algorithm to hold for weaker generative models relaxing our planted RIP row subset assumption to a natural weighted variant, and show that our method's guarantees naturally interpolate the quality of the measurement matrix to, in some parameter regimes, run in sublinear time.
Our approach differs from that of prior fast iterative methods with provable guarantees under semirandom generative models (Cheng and Ge '18, Li et al. '20), which typically separate the problem of learning the planted instance from the estimation problem, i.e. they attempt to first learn the planted "good" instance (in our case, the matrix G). However, natural conditions on a submatrix which make sparse recovery tractable, such as RIP, are NPhard to verify and hence first learning a sufficient row reweighting appears challenging. We eschew this approach and design a new iterative method, tailored to the geometry of sparse recovery, which is provably robust to our semirandom model. Our hope is that our approach opens the door to new robust, efficient algorithms for other natural statistical inverse problems.
Based on joint work with Jonathan Kelner, Jerry Li, Allen Liu, and Aaron Sidford
[Anchor] 04/08/2022
Debmalya Panigrahi, Duke University
Recent Results in Minimum Cut Algorithms
Minimum cut problems are among the most basic questions in algorithm design. In the last few years, there has been a resurgence in new results in this domain, resulting in the first improvements in many decades for problems such as global mincut, vertex mincut, allpairs mincut, etc. In this talk, I will explore some of these results, focusing on the broad themes and techniques that have driven this progress.
This talk will be based on papers that have appeared in FOCS '20, STOC '21, and FOCS '21.
[Anchor] 04/15/2022
William Hoza, Simons Institute
Fooling ConstantDepth Threshold Circuits
We present the first nontrivial pseudorandom generator (PRG) for linear threshold (LTF) circuits of arbitrary constant depth and superlinear size. This PRG fools circuits with depth d and n^{1 + delta} wires, where delta = exp(O(d)), using seed length O(n^{1  delta}) and with error exp(n^{delta}). This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for LTF circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuitanalysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds.
A key ingredient in our construction is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a nonnatural "hybrid computational model" that combines decision trees and LTFs. As part of our proof we also construct an "extremely lowerror" PRG for the class of functions computable by an arbitrary function of s linear threshold functions that can handle even the extreme setting of parameters s = n/polylog(n) and epsilon = exp(n/polylog(n)).
Joint work with Pooya Hatami, Avishay Tal, and Roei Tell.
[Anchor] 04/22/2022
Sushant Sachdeva, University of Toronto
Almost Linear Time Algorithms for MaxFlow and More
***There will be an additional 15minute optional portion of the talk immediately afterwards in order to fully convey the main ideas of the work.***
We give the first almostlinear time algorithm for computing exact maximum flows and minimumcost flows on directed graphs. By wellknown reductions, this implies almostlinear time algorithms for several problems including bipartite matching, optimal transport, and undirected vertex connectivity.
Our algorithm is designed using a new Interior Point Method (IPM) that builds the flow as a sequence of almostlinear number of approximate undirected minimumratio cycles, each of which is computed and processed very efficiently using a new dynamic data structure.
Our framework extends to give an almostlinear time algorithm for computing flows that minimize general edgeseparable convex functions to high accuracy. This gives the first almostlinear time algorithm for several problems including entropyregularized optimal transport, matrix scaling, pnorm flows, and Isotonic regression.
Joint work with Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, and Maximilian Probst Gutenberg.
[Anchor] 04/29/2022
John Kallaugher, Sandia National Laboratories
A Quantum Advantage for a Natural Streaming Problem
**HYBRID EVENT in GDC 4.304  Event will begin at 2:00PM.**
Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of spacebounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input.
We give a onepass quantum streaming algorithm for one of the best studied problems in classical graph streaming  the triangle counting problem. Almosttight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.
[Anchor] 05/06/2022
Dean Doron, BenGurion University
Approximating Large Powers of Stochastic Matrices in Small Space
We give a deterministic spaceefficient algorithm for approximating powers of stochastic matrices. On input a w×w stochastic matrix A, our algorithm approximates An in space O(log n + √log n · log w) to within high accuracy. This improves upon the seminal work by Saks and Zhou, that requires O(log3/2n + √log n·log w) space, in the regime n ≫ w.
Fall 2021
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, NonBlackBox, and InstanceWise
10/08/2021  Eric Vigoda, UCSB: Computational Phase Transition for Approximate Counting
10/15/2021  Srikanth Srinivasan, Aarhus University: Superpolynomial Lower Bounds Against LowDepth Algebraic Circuits
10/22/2021  Amnon TaShma, TelAviv University: Expander Random Walks: A FourierAnalytic Approach
11/05/2021  Joe Neeman, UT Austin: Robust Testing of LowDimensional 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 wellknown classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a KarushKuhnTucker (KKT) point of a continuously differentiable function over the domain [0,1]2 is PPAD ∩ PLScomplete. 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/2epsilon 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 LLLlike 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 FisherShannon (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 baseq variants of Flajolet and Martin's PCSA sketch have Fishnumber H0/I0≈1.98016 and that every baseq variant of (Hyper)LogLog has Fishnumber 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, entropycompressed 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 Fishnumber 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, NonBlackBox, and InstanceWise
Textbook hardnesstorandomness converts circuit lower bounds into PRGs. But is this blackbox approach really necessary for derandomization? In this talk I'll show how to revamp the classical hardnesstorandomness framework, converting new types of *uniform lower bounds* into *nonblackbox derandomization*. This yields conclusions such as promiseBPP = promiseP without PRGs, and reveals a close connection between worstcase 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 LowDepth 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 nonzero 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 polynomialsized "SigmaPiSigma" (sums of products of sums) representations. We can also show similar results for SigmaPiSigmaPi, SigmaPiSigmaPiSigma and so on for all "constantdepth" expressions.
Based on joint work with Nutan Limaye (ITU Copenhagen + IIT Bombay) and Sébastien Tavenas (USMB + Univ. Grenoble, CNRS).
10/22/2021
Amnon TaShma, TelAviv University
Expander Random Walks: A FourierAnalytic 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 FourierAnalytic 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 LowDimensional Functions *Hybrid Event: To be hosted virtually and in person in GDC 4.304*
A natural problem in highdimensional 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 kjunta if it is completely determined by some kdimensional subspace of the input space. A recent work of the authors showed that linear kjuntas are testable. Thus there exists an algorithm to distinguish between: 1. f:Rn→{−1,1} which is a linear kjunta with surface area s, 2. f is ϵfar from any linear kjunta 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 noisetolerant property testing, in this paper we prove a noisetolerant (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 kjunta with surface area s. 2. f has correlation at most c−ϵ with any linear kjunta 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 kjuntas 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 khalfspaces (for constant k) over the Gaussian space. Our query complexity is independent of the ambient dimension n. Previously, no nontrivial 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 2approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in nearlinear time.
A series of papers on finegrained 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 medge graphs requires mn^{1+1/(k−1)−o(1)} time. In particular, the simple linear time 2approximation algorithm is optimal.
In this talk I will give an overview of the known algorithms and finegrained lower bounds for diameter, including the SETHbased optimality of the 2approximation 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 errorcorrecting 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 3query 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 PaskinCherniavsky (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 2query linear Insdel LDCs do not exist, and give an exponential lower bound for the length of all qquery 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 privatekey 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 privatekey 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 propertytester. 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 "c3LTCs", namely LTCs with *c*onstant rate, *c*onstant distance, and *c*onstant locality.
In this work we construct such codes based on a new twodimensional complex which we call a leftright Cayley complex. This is essentially a graph which, in addition to vertices and edges, also has squares. Our codes can be viewed as a twodimensional version of (the onedimensional) expander codes, where the codewords are functions on the squares rather than on the edges.