Fall 2021

Fall 2021 Theory Seminars will meet on Fridays from 1:30 -2:30pm via a zoom invite. This schedule will be updated throughout the semester.

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, MIT
10/08/2021 - Eric Vigoda, UCSB
10/15/2021 - Srikanth Srinivasan, IIT Bombay
10/22/2021 - 
10/29/2021 - Amnon Ta-Shma, Tel-Aviv University
11/05/2021 - 
11/12/2021 - 
11/19/2021 - 
12/03/2021 - 

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.

Spring 2021

01/22/2021 - Richard Peng, Georgia Institute of Technology: Solving Sparse Linear Systems Faster than Matrix Multiplication
02/05/2021 - Rahul Ilango, Massachusetts Institute of Technology: Towards Hardness for the Minimum Circuit Size Problem
02/12/2021 - Mark Bun, Boston University: An Equivalence between Private Classification and Online Prediction
03/05/2021 - Rocco Servedio, Columbia University: Some Recent Results on Trace Reconstruction
03/12/2021 - Daniel Kane, University of California San Diego: Point Location and Active Learning
03/26/2021 - Muthu Venkitasubramaniam, University of Rochester: Average-case Complexity Through the Lens of Interactive Puzzles
04/02/2021 -  Andy Drucker, University of Chicago: An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature
04/09/2021 - Mark Braverman, Princeton: Optimal Tiling of the Euclidean Space Using Symmetric Bodies
04/16/2021 - Matthew Fahrbach, Google: Edge-Weighted Online Bipartite Matching
04/23/2021 - Gil Cohen, Tel Aviv University: Tree Codes and Interactive Coding Schemes
04/30/2021 - Eric Price, UT: Instance-Optimal Compressed Sensing via Conditional Resampling
05/07/2021 - Rahul Santhanam, Oxford: An Unconditional Polynomial-Time Pseudorandom Generator and its Consequences

01/22/2021
Richard Peng, Georgia Institute of Technology
Solving Sparse Linear Systems Faster than Matrix Multiplication

Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general setting, the bit complexity of solving an n-by-n linear system Ax=b is n^\omega, where \omega<2.372864 is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly(n) condition number.

We present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any \omega>2. This speedup holds for any input matrix A with o(n^{\omega -1}/\log(\kappa(A))) non-zeros, where \kappa(A) is the condition number of A. For poly(n)-conditioned matrices with O(n) nonzeros, and the current value of \omega, the bit complexity of our algorithm to solve to within any 1/poly(n) error is O(n^{2.331645}).

Our algorithm can be viewed as an efficient randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly-Giesbrecht-Giorgi-Storjohann-Villard ISSAC `06 `07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.

Joint work with Santosh Vempala, manuscript at https://arxiv.org/abs/2007.10254.

02/05/2021
Rahul Ilango, Massachusetts Institute of Technology
Towards Hardness for the Minimum Circuit Size Problem

While understanding the computational complexity of the Minimum Circuit Size Problem (MCSP) is strongly motivated by connections to areas such as learning theory, cryptography, and average-case complexity, we still know relatively little about the problem. In particular, it is a longstanding open problem to base the intractability of MCSP on standard worst-case assumptions.

In this talk, I will survey a series of recent works that prove hardness results for natural variants of MCSP. This includes NP-hardness for an oracle-version, a multi-output version, and a constant-depth formula version. I'll discuss the last result in the most detail, and I'll highlight an application that uses similar techniques to establish the existence of functions with a 2^{\Omega_d(n)} additive gap between their depth-d and depth-(d+1) formula complexity.

02/12/2021
Mark Bun, Boston University
An Equivalence between Private Classification and Online Prediction

Differential privacy enables rich statistical analyses on data while provably protecting individual-level privacy. The last 15 years of research has shown that, at least in principle, a number of fundamental statistical tasks are compatible with differential privacy. However, privacy-preserving analyses often require additional complexity over their non-private counterparts, for instance, in terms of the number of data samples one needs to collect in order to get accurate results. In fact, some infinite concept classes that are "easy" to learn in standard computational learning theory become impossible to learn under differential privacy using any finite number of samples.

Alon, Livni, Malliaris, and Moran recently showed that finite Littlestone dimension is a necessary condition for a concept class to be privately learnable, and conjectured that it is sufficient as well. Here, Littlestone dimension characterizes learnability in the mistake-bound model of online learning. We prove their conjecture, establishing a qualitative equivalence between private learnability and online learnability. Our result goes by way of a new connection between privacy and algorithmic stability for learning.

Joint work with Roi Livni and Shay Moran.

03/05/2021
Rocco Servedio, Columbia University
Some Recent Results on Trace Reconstruction

I will give a broad overview of the "trace reconstruction problem", which is the problem of reconstructing a string from deletion-plagued copies of it.  The general problem is largely open with an exponential gap between known upper and lower bounds; the main focus of the talk will be on some recent results in settings where efficient trace reconstruction is known to be possible.

03/12/2021
Daniel Kane, University of California San Diego
Point Location and Active Learning

In the point location one is given a hyperplane arrangement and an unknown point. By making linear queries about that point one wants to determine which cell of the hyperplane arrangement it lies in. This problem has an unexpected connection to the problem in machine learning of actively learning a halfspace. We discuss these problems and their relationship and provide a new and nearly optimal algorithm for solving them.

03/26/2021
Muthu Venkitasubramaniam, University of Rochester
Average-case Complexity Through the Lens of Interactive Puzzles

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in $\NP$ imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that the answer to (at least) one of these questions is yes.
 
Both one-way functions and problems in TFNP can be interpreted as promise-true distributional NP search problems---namely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence of a hard-on-average distributional NP search problem implies a hard-on-average promise-true distributional NP search problem. In other words, ”It is no easier to find witnesses (a.k.a. proofs) for efficiently-sampled statements (theorems) that are guaranteed to be true.”

This result follows from a more general study of interactive puzzles---a generalization of average-case hardness in NP—and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols.

Joint work with Rafael Pass.

04/02/2021
Andy Drucker, University of Chicago
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly. Estimating the value of such games (i.e., winning probability under optimal play by the strategic player) is an important goal in the study of decision-making under uncertainty.  The problem's PSPACE-completeness does not rule out non-trivial algorithms, a goal fulfilled in certain cases by Littman, Majercik, and Pitassi [LMP '01].

We study the case in which the players strictly alternate with binary moves, for which [LMP '01] does not give a general speedup. We give a randomized algorithm to approximate the value of such games (and to produce near-optimal play) . Our algorithm achieves exponential savings over brute-force, making 2^{(1-delta)n} queries to the input game's lookup table for some absolute constant delta > 0, and certifies a lower bound on the game value with exponentially-small expected additive error. (On the downside, delta is tiny and the algorithm uses exponential space.)

Our algorithm is recursive, and bootstraps a "base-case" algorithm for fixed-size inputs. The base-case algorithm and the form of recursive composition used are interesting and, we feel, likely to find uses beyond the present work.

04/09/2021
Mark Braverman, Princeton
Optimal Tiling of the Euclidean Space Using Symmetric Bodies

What is the least surface area of a symmetric body B whose Z^n translations tile R^n? Since any such body must have volume 1, the isoperimetric inequality implies that its surface area must be at least \Omega(\sqrt{n}). Remarkably, Kindler et al. showed that for general bodies B this is tight, i.e. that there is a tiling body of R^n whose surface area is O(\sqrt{n}). In contrast, the surface area of the "trivial" tiling by cubes [0,1]^n is 2n.

In theoretical computer science, the tiling problem is intimately to the study of parallel repetition theorems (which are an important component in PCPs), and more specifically in the question of whether a ``strong version'' of the parallel repetition theorem holds. Raz showed, using the odd cycle game, that strong parallel repetition fails in general, and subsequently these ideas were used to construct non-trivial tilings of R^n.

Motivated by the study of a symmetric parallel repetition, we consider the symmetric variant of the tiling problem in R^n. We show that any symmetric body that tiles $\mathbb{R}^n$ must have surface area at least \Omega(n/\sqrt{\log n}), and that this bound is tight, i.e.\ that there is a symmetric tiling body of R^n with surface area O(n/\sqrt{\log n}). We also give matching bounds for the value of the symmetric parallel repetition of Raz's odd cycle game.

Based on joint work with Dor Minzer (MIT).

04/16/2021
Matthew Fahrbach, Google
Edge-Weighted Online Bipartite Matching

Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) introduced an elegant algorithm for the unweighted bipartite matching that achieves an optimal competitive ratio of 1-1/e. Aggarwal et al. (SODA 2011) later generalized their algorithm and analysis to the vertex-weighted case. Little is known, however, about the most general edge-weighted problem aside from the trivial 1/2-competitive greedy algorithm. In this paper, we present the first online algorithm that breaks the long-standing 1/2 barrier and achieves a competitive ratio of at least 0.5086. In light of the hardness result of Kapralov, Post, and Vondrák (SODA 2013) that restricts beating a 1/2 competitive ratio for the more general problem of monotone submodular welfare maximization, our result can be seen as strong evidence that edge-weighted bipartite matching is strictly easier than submodular welfare maximization in the online setting.

The main ingredient in our online matching algorithm is a novel subroutine called online correlated selection (OCS), which takes a sequence of pairs of vertices as input and selects one vertex from each pair. Instead of using a fresh random bit to choose a vertex from each pair, the OCS negatively correlates decisions across different pairs and provides a quantitative measure on the level of correlation. We believe our OCS technique is of independent interest and will find further applications in other online optimization problems.

04/23/2021
Gil Cohen, Tel Aviv University
Tree Codes and Interactive Coding Schemes

Interactive coding is the study of conversing over imperfect communication channels. In this talk I will survey key results in this 30 year old field, focusing on the related combinatorial problem of constructing tree codes.

04/30/2021
Eric Price, UT
Instance-Optimal Compressed Sensing via Conditional Resampling

Given a distribution P of images, how many random linear measurements are required for approximate recovery? Classical compressed sensing gives an upper bound for approximately sparse P, but actual distributions may have more or different structure than sparsity.  We instead give an instance-optimal bound: when P is (approximately) known, then conditional resampling, where we output a sample of P(x | y), is within constant factors of the best possible recovery algorithm.

When applied to state-of-the-art deep generative models, we find that conditional resampling produces less washed-out, more realistic results than prior methods.  It also has nice fairness properties, including "proportional representation": the representation of any group in the output matches the input distribution.

05/07/2021
Rahul Santhanam, Oxford
An Unconditional Polynomial-Time Pseudorandom Generator and its Consequences​

The existence of pseudo-random generators (PRGs) secure against general polynomial-time adversaries is one of the central questions in cryptography and pseudorandomness. For each $\epsilon > 0$, we give an unconditional construction of a PRG G from n^{\epsilon} bits to n bits  that is infinitely often secure against probabilistic linear-time adversaries, such that G is computable in probabilistic polynomial time with one bit of advice. As a consequence, we show that there are infinitely many n for which there is a prime p_n of length n with a succinct representation of size n^{\epsilon} from which p_n can be feasibly recovered.

Our broader motivation is the study of pseudodeterministic algorithms, pioneered by Gat and Goldwasser. A pseudodeterministic algorithm for a search problem is one that outputs a fixed answer to the search problem with high probability. We show a close correspondence between pseudodeterministic algorithms for randomized search problems and long-standing open problems about the structure of probabilistic time, such as the existence of complete problems and of tight hierarchies.

Joint work with Zhenjian Lu and Igor Oliveira.

Fall 2020

08/28/2020 - Michal Moshkovitz, UC San Diego: Unexpected Effects of Online K-means Clustering
09/04/2020 - Greg Plaxton, UT Austin: On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences
09/11/2020 - Ben Lee Volk , UT Austin: A Lower bound on Determinantal Complexity
09/25/2020 - Alexander Sherstov, UCLA: An Optimal Separation of Randomized and Quantum Query Complexity
10/02/2020 - Eshan Chattopadhyay, Cornell: Pseudorandom Generators from Fourier Tail Bounds
10/09/2020 - Sumegha Garg, Harvard: The Coin Problem with Applications to Data Streams
*All meetings after 10/16/2020 will begin at 2:00 PM.*
10/16/2020 - Shalev Ben-David, University of Waterloo: Forecasting Algorithms, Minimax Theorems, and Randomized Lower Bounds 
10/23/2020 - Anup Rao, University of Washington: Anti-concentration and the Gap-Hamming problem
10/30/2020 - Seth Pettie, University of Michigan: Planar Distance Oracles
11/13/2020 - Rafael Pass, Cornell University: On One-Way Functions and Kolmogorov Complexity
11/20/2020 - Xi Chen, Columbia University: An Improved Analysis of the Quadtree for High Dimensional EMD
12/04/2020 - Andrea Lincoln, UC Berkeley: New Techniques for Proving Fine-Grained Average-Case Hardness
12/11/2020 - Zhao Song, Princeton & Institute for Advanced Study: Optimization: From Linear Programming to Deep Learning

08/28/2020
Michal Moshkovitz, UC San Diego
Unexpected Effects of Online K-means Clustering

Offline k-means clustering was studied extensively and algorithms with a constant approximation are available. However, online clustering is still uncharted. New factors come into play: the ordering of the dataset and whether the number of points, n, is known in advance or not. Their exact effects are unknown. In this paper we focus on the online setting where the decisions are irreversible: after a point arrives the algorithm needs to decide whether to take the point as a center or not, and this decision is final. How many centers are needed and sufficient to achieve constant approximation in this setting? We show upper and lower bounds for all the different cases. These bounds are exactly the same up to a constant, thus achieving optimal bounds. For example, for k-means cost with constant k>1 and random order, Θ(logn) centers are enough to achieve a constant approximation, while the mere apriori knowledge of n reduces the number of centers to a constant. These bounds hold for any distance function that obeys a triangle-type inequality.

09/04/2020
Greg Plaxton, UT Austin
On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences

In the most basic version of the stable marriage problem, we are given an equal number of men and women, each of whom has complete, strict preferences over the agents of the opposite sex, and we seek a perfect matching (i.e., a partition of the agents into disjoint man-woman pairs) that is "stable" in the sense that no man and woman prefer each other to their matches.  In a famous result, Gale and Shapley presented an algorithm that computes a stable matching for any given stable marriage instance.

Knuth asked whether stable matchings are guaranteed to exist when there are three types of agents, say men, women, and dogs. In this setting, we seek to partition the agents into a stable collection of man-woman-dog families. Several variants of Knuth's question -- associated with different restrictions on the agent preferences -- have been addressed in the literature. In this talk, we study the special case where the men care only about the women, the women care only about the dogs, and the dogs care only about the men.  Our main theorem disproves some published conjectures.

Joint work with Chi-Kit Lam.

09/11/2020
Ben Lee Volk, UT Austin
A lower bound on determinantal complexity

This talk is about algebraic complexity, which is a field that studies the complexity of computing algebraic problems using basic arithmetic operations. In the first part of the talk I will give a brief introduction to this area. The nature of questions arising in the study of polynomials as complexity theoretic objects suggests that techniques from algebraic geometry could be useful. As an example, I will then describe a recent result establishing a lower bound on the well studied notion of determinantal complexity, which is closely related to circuit lower bounds. The determinantal complexity of a polynomial f is the minimal integer m such that there exists an mxm matrix M of linear functions such that f(x)=Det(M(x)).
We give an explicit n-variate polynomial of degree n whose determinantal complexity is at least 1.5n-3. This is the strongest lower bound known as a function of the number of variables.
(Based on a joint work with Mrinal Kumar)

09/25/2020
Alexander Sherstov, UCLA
An Optimal Separation of Randomized and Quantum Query Complexity

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with $\ell,$ becoming trivial already at $\ell=\sqrt{d}.$

As an application, we obtain, for any positive integer $k,$ a partial function on $n$ bits that has bounded-error quantum query complexity at most ceiling(k/2) and randomized query complexity $\tilde{\Omega}(n^{1-1/k}).$ This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015). Prior to our work, the best known separation was polynomially weaker: $O(1)$ versus $n^{2/3-\epsilon}$ for any $\epsilon>0$ (Tal, FOCS 2020).

No familiarity with quantum computing will be assumed. Joint work with Andrey Storozhenko (UCLA) and Pei Wu (UCLA): https://arxiv.org/abs/2008.10223.

10/02/2020
Eshan Chattopadhyay, Cornell
Pseudorandom Generators from Fourier Tail Bounds

A central goal in complexity theory is to construct unconditional pseudorandom generators (PRGs) for various computational models. In this talk, I will survey a recent line of work that develops a new method for constructing PRGs via exploiting Fourier tail bounds of Boolean function classes. This gives a unified way of constructing PRGs for many well-studied classes of functions including small-depth circuits (AC0), small-width branching programs, low-sensitivity functions, and low-degree polynomials over F_2.  I will highlight open problems around this new framework that will imply application of this method in constructing PRGs for classes of functions (such as AC0 with PARITY gates) that have been beyond reach for decades.

Based on joint works with Jason Gaitonde, Pooya Hatami, Kaave Hosseini, Chin Ho Lee, Shachar Lovett, Abhishek Shetty, Avishay Tal, and David Zuckerman.

10/09/2020
Sumegha Garg,  Harvard
The Coin Problem with Applications to Data Streams

Consider the problem of computing the majority of a stream of n i.i.d. uniformly random bits. This problem, known as the coin problem, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant advantage (over the uniform distribution) must use Ω(log n) bits of space. Previously, it was known that computing the majority on every input with a constant probability takes Ω(log n) space. We extend our lower bound to proving tight lower bounds for solving multiple, randomly interleaved copies of the coin problem, as well as for solving the OR of multiple copies of a variant of the coin problem. Our proofs involve new measures of information complexity that are well-suited for data streams.

We use these lower bounds to obtain a number of new results for data streams. In each case there is an underlying d-dimensional vector x with additive updates to its coordinates given in a stream of length m. The input streams arising from our coin lower bound have nice distributional properties, and consequently for many problems for which we only had lower bounds in general turnstile streams, we now obtain the same lower bounds in more natural models, such as the bounded deletion model, in which ||x||_2 never drops by a constant fraction of what it was earlier, or in the random order model, in which the updates are ordered randomly. 

Based on joint work with Mark Braverman and David P. Woodruff.

10/16/2020 *TIME CHANGE: Meeting will begin at 2:00 PM.*
Shalev Ben-David, University of Waterloo
Forecasting Algorithms, Minimax Theorems, and Randomized Lower Bounds

I will present a new approach to randomized lower bounds, particularly in the setting where we wish to give a fine-grained analysis of randomized algorithms that achieve small bias. The approach is as follows: instead of considering ordinary randomized algorithms which give an output in {0,1} and may err, we switch models to look at "forecasting" randomized algorithms which output a confidence in [0,1] for whether they think the answer is 1. When scored by a proper scoring rule, the performance of the best forecasting algorithm is closely related to the bias of the best (ordinary) randomized algorithm, but is more amenable to analysis.

As an application, I'll present a new minimax theorem for randomized algorithms, which can be viewed as a strengthening of Yao's minimax theorem. Yao's minimax theorem guarantees the existence of a hard distribution for a function f such that solving f against this distribution (to a desired error level) is as hard as solving f in the worst case (to that same error level). However, the hard distribution provided by Yao's theorem depends on the chosen error level. Our minimax theorem removes this dependence, giving a distribution which certifies the hardness of f against all bias levels at once. In recent work, we used this minimax theorem to give a tight composition theorem for randomized query complexity.

Based on joint work with Eric Blais.

10/23/2020  *TIME CHANGE: Meeting will begin at 2:00 PM.*
Anup Rao, University of Washington
Anti-concentration and the Gap-Hamming problem
 

We prove new lower bounds on the well known Gap-Hamming problem in communication complexity. Our main technical result is an anti-concentration bound for the inner product of two independent random vectors. We show that if A, B are arbitrary  subsets of the cube {±1}^n with |A| · |B| ≥ 2^(1.01n), and X ∈ A and Y ∈ B are sampled independently and uniformly, then the inner product <X,Y> must be anti-concentrated: it takes on any fixed value with probability at most O(1/sqrt(n)). In fact, the following stronger claim holds: for any integer k, |Pr[<X,Y>=k] - Pr[<X,Y> = k+4]| is at most O(1/n). Remarkably, this last claim is false if 4 is replaced with an integer that is not divisible by 4. I will explain why this happens in my talk.

This is joint work with Amir Yehudayoff.

10/30/2020
Seth Pettie, University of Washington
Planar Distance Oracles

We consider the problem of preprocessing a weighted planar graph in order to answer exact distance and shortest path queries. As in the recent algorithms of Cohen-Addad et al. (2017), Gawrychowski et al. (2018), and Charalampopoulos et al. (2019), our algorithm is based on solving the point-location problem in weighted planar Voronoi diagrams.

We give a new, efficient method to solve point location using persistent data structures, which leads to a new time-space tradeoff for the problem. At the extremes of this tradeoff, the data structure:

* occupies $n^{1+o(1)}$ space and answers distance queries in $\log^{2+o(1)} n$ time, or

* occupies $n\log^{2+o(1)} n$ space and answers distance queries in$n^{o(1)}$ time.

Joint work with Yaowei Long, to appear in SODA 2021. arXiv:2007.08585.

11/13/2020
Rafael Pass, Cornell University
On One-Way Functions and Kolmogorov Complexity

We prove the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n)>2n, the following are equivalent:

  • Cryptographic one-way functions exists; 
  • The t-time bounded Kolmogorov Complexity problem is mildly hard-on-average.

In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptograpy. 

Joint work with Yanyi Liu: https://eccc.weizmann.ac.il/report/2020/052/.

11/20/2020
Xi Chen, Columbia University
An Improved Analysis of the Quadtree for High Dimensional EMD

The Earth Mover's Distance (EMD) between two multi-sets A,B in R^d of size s is the min-cost of bipartite matchings between points in A and B, where the cost is measured by distance between points. We study a class of divide-and-conquer algorithms based on a quadtree data structure. Our analysis improves on the O(min{log s, log d} log s)-approximation of Andoni et al. (2008) and Backurs et al. (2020), showing that matchings from quadtrees can be used to achieve an O(log s)-approximation of EMD. As further applications, we give new linear sketches (and streaming algorithms) for the approximation of EMD. The main conceptual contribution is an analytical framework for studying quadtrees which goes beyond the worst-case distortion of randomized tree embeddings.

Joint work with Rajesh Jayaram, Amit Levi and Erik Waingarten.

12/04/2020
Andrea Lincoln, UC Berkeley
New Techniques for Proving Fine-Grained Average-Case Hardness

In this talk I will cover a new technique for worst-case to average-case reductions. There are two primary concepts introduced in this talk: "factored" problems and a framework for worst-case to average-case fine-grained (WCtoACFG) self reductions.
We will define new versions of OV, kSUM and zero-k-clique that are both worst-case and averagecase fine-grained hard assuming the core hypotheses of fine-grained complexity. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. Our hard factored problems are also simple enough that we can reduce them to many other problems, e.g. to edit distance, k-LCS and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution.

To show hardness for these factored problems we formalize the framework of [Boix-Adsera et al. 2019]  that was used to give a WCtoACFG reduction for counting k-cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self reduction.

In total these factored problems and the framework together give tight fine-grained average-case hardness for various problems including the counting variant of regular expression matching. Based on joint work with Mina Dalirrooyfard and Virginia Vassilevska Williams. 

12/11/2020
Zhao Song, Princeton & Institute for Advanced Study
Optimization: From Linear Programming to Deep Learning

Many real-life problems can be solved by optimization methods including both linear programming and deep learning. The running time of optimization algorithms usually consists of two components, the number of iterations and the cost per iteration. Over the past several decades, researchers have been putting tremendous efforts on reducing the number of iterations. Recently, we found new angles and proposed novel techniques to speed up the cost per iteration instead. In this talk, we first show how to use those ideas to speed up linear programming to n^omega + n^{2+1/18} time. Further, we show our ideas can be applied to the field of deep learning theory, and can be used to train neural networks more efficiently in practice.

This talk is based on joint works with Jan van den Brand, Shunhua Jiang, Binghui Peng, Omri Weinstein, Hengjie Zhang.

https://arxiv.org/abs/2004.07470
https://arxiv.org/abs/2006.11648
https://openreview.net/forum?id=wWK7yXkULyh