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

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: Negative-Weight Single-Source 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

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.

09/09/2022
Joe Neeman, UT
Bubble Clusters in Geometry and Computer Science

On the plane, a circle is the smallest-perimeter 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 low-energy states of local Hamiltonians cannot be described by constant depth quantum circuits. 

The ``No low-energy 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 low-depth 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 non-commutative 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 communication-based 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 lower-bounds 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 polynomially-small rank.

Based on joint work with Prasad Raghavendra and Abhishek Shetty.

10/14/2022
Danupon Nanogkai, Max Planck Institute for Informatics
Negative-Weight Single-Source Shortest Paths in Near-Linear Time
Watch a video of this seminar

We present a randomized algorithm that computes single-source 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 negative-weight 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 Wulff-Nilsen.)

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:

1. Finding a refutation algorithm for smoothed instances of constraint satisfaction problems (obtained by randomly perturbing the literal patterns in a worst-case instance with a small probability) that matches the best running-time vs constraint-density trade-offs for the significantly special and easier case of random CSPs, 
2. Confirming Feige's 2008 Conjecture that postulated an extremal girth vs density trade-off (a.k.a. Moore bounds) for k-uniform hypergraphs that generalizes the Alon-Hoory-Linial Moore bound for graphs, 
3. 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, st-reachability in such a setting, it is useful to find a shortcut set as a preprocessing step, and then run an st-reachability 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 NP-completeness, Leonid Levin proved NP-hardness of the partial function version of the Minimum DNF Size Problem in 1973, but delayed his publication because he hoped to extend it to NP-hardness of the Minimum Circuit Size Problem (MCSP). In this talk, we prove NP-hardness of the partial function version of MCSP. Our proofs are inspired by NP-hardness of learning programs, the question posed by Ker-I 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 two-choice 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 power-of-two-choices 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 sub-optimal 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 end-points. 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 bounded-round two-player randomized communication. For a function f:X×Y→{0,1}, the n-fold 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 r-round communication protocols that computes f with probability 2/3 uses at least C bits of communication, then any r-round protocol that computes f^⊕n with probability 1/2+exp(-O(n)) must use n(r^{-O (r)}C-1) 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 2-bit communication protocols, our new XOR lemma implies the previous result.
 

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.