A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, April 14 — Andrea Lincoln, UC Berkeley

The next TCS+ talk will take place this coming Wednesday, April 14th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Andrea Lincoln from UC Berkeley will speak about “New Techniques for Proving Fine-Grained Average-Case Hardness” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The recorded talk will also be posted on our website afterwards, so people who did not sign up will still be able to watch the talk)

As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: 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 average-case 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.

TCS+ talk: Wednesday, March 31 — Jasper Lee, Brown University

The next TCS+ talk will take place this coming Wednesday, March 31th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Jasper Lee from Brown University will speak about “Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The recorded talk will also be posted on our website afterwards, so people who did not sign up will still be able to watch the talk)

As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We revisit and settle a fundamental problem in statistics: given access to independent samples from a 1D random variable (with finite but unknown mean and variance), what is the best way to estimate the mean in the high probability regime, in terms of error convergence with respect to sample size? The conventional wisdom is to use the empirical mean as our estimate. However, it is known that the empirical mean can in fact have exponentially sub-optimal convergence for certain heavy-tailed distributions. On the other hand, the median-of-means estimator (invented and reinvented in various literature) does have sub-Gaussian convergence for all finite-variance distributions, albeit only in the big-O sense with a sub-optimal multiplicative constant. The natural remaining question then, is whether it is possible to bridge the gap, and have an estimator that has optimal convergence with the right constant for all finite-variance distributions.

In this talk, we answer the question affirmatively by giving an estimator that converges with the optimal constant inside the big-O, up to a 1+o(1) multiplicative factor. The estimator is also easy to compute. The convergence analysis involves deriving tail bounds using linear and convex-concave programming dualities, which may be of independent interest.

Based on joint work with Paul Valiant.

TCS+ talk: Wednesday, March 17 — Avishay Tal, UC Berkeley

The next TCS+ talk will take place this coming Wednesday, March 17th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Avishay Tal from UC Berkeley will speak about “Junta Distance Approximation with Sub-Exponential Queries” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The recorded talk will also be posted on our website afterwards, so people who did not sign up will still be able to watch the talk.) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Joint Work with Vishnu Iyer and Michael Whitmeyer.

A Boolean function $f\colon \{0,1\}^n \to \{0,1\}$ is called a $k$-junta if it depends only on $k$ out of the $n$ input bits. Junta testing is the task of distinguishing between $k$-juntas and functions that are far from $k$-juntas. A long line of work settled the query complexity of testing $k$-juntas, which is $O(k log(k))$ [Blais, STOC 2009; Saglam, FOCS 2018]. Suppose, however, that $f$ is not a perfect $k$-junta but rather correlated with a $k$-junta. How well can we estimate this correlation? This question was asked by De, Mossel, and Neeman [FOCS 2019], who gave an algorithm for the task making $\sim\exp(k)$ queries. We present an improved algorithm that makes $\sim\exp(\sqrt{k})$ many queries. Along the way, we also give an algorithm, making $\mathrm{poly}(k)$ queries, that provides “implicit oracle access” to the underlying $k$-junta. Our techniques are Fourier analytical and introduce the notion of “normalized influences” that might be of independent interest.

TCS+ talk: Wednesday, March 3 — Steve Hanneke, TTIC

The next TCS+ talk will take place this coming Wednesday, March 3th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Steve Hanneke from TTIC will speak about “A Theory of Universal Learning” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The recorded talk will also be posted on our website afterwards, so people who did not sign up will still be able to watch the talk.) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: How quickly can a given class of concepts be learned from examples? It is common to measure the performance of a supervised machine learning algorithm by plotting its “learning curve”, that is, the decay of the error rate as a function of the number of training examples. However, the classical theoretical framework for understanding learnability, the PAC model of Vapnik-Chervonenkis and Valiant, does not explain the behavior of learning curves: the distribution-free PAC model of learning can only bound the upper envelope of the learning curves over all possible data distributions. This does not match the practice of machine learning, where the data source is typically fixed in any given scenario, while the learner may choose the number of training examples on the basis of factors such as computational resources and desired accuracy.

In this work, we study an alternative learning model that better captures such practical aspects of machine learning, but still gives rise to a complete theory of the learnable in the spirit of the PAC model. More precisely, we consider the problem of universal learning, which aims to understand the performance of learning algorithms on every data distribution, but without requiring uniformity over the distribution. The main result of this work is a remarkable trichotomy: there are only three possible rates of universal learning. More precisely, we show that the learning curves of any given concept class decay either at an exponential, linear, or arbitrarily slow rates. Moreover, each of these cases is completely characterized by appropriate combinatorial parameters, and we exhibit optimal learning algorithms that achieve the best possible rate in each case.

Joint work with Olivier Bousquet, Shay Moran, Ramon van Handel, and Amir Yehudayoff.

TCS+ talk: Wednesday, February 17 — William Hoza, UT Austin

Welcome back for a new season of TCS+! Our talks are back to a fortnightly schedule, with an exciting slate of speakers ahead of us.

The first TCS+ talk will take place in two weeks, Wednesday, February 17th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). William Hoza from UT Austin will speak about “Fooling Constant-Depth Threshold Circuits” (abstract below). You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The talk will be recorded and posted on our website and YouTube channel afterwards, so people who did not sign up will still be able to watch the talk.) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We present the first non-trivial pseudorandom generator (PRG) for linear threshold (LTF) circuits of arbitrary constant depth and super-linear 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 circuit-analysis 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 non-natural “hybrid computational model” that combines decision trees and LTFs. As part of our proof we also construct an “extremely low-error” 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/\mathrm{polylog}(n)$ and $\epsilon = \exp(-n/\mathrm{polylog}(n))$.

Joint work with Pooya Hatami, Avishay Tal, and Roei Tell.

TCS+ talk: Wednesday, December 2 — Yang Liu, Stanford University

We hope you are all doing well and, in the case of our US audience, are slowly emerging from a comfortable Thanksgiving food-induced stupor! Our last TCS+ talk of the semester will take place this coming Wednesday, December 2nd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Yang Liu from Stanford University will speak about “Faster Algorithms for Unit Maximum Flow” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: The maximum flow problem is one of the most well-studied problems in combinatorial optimization, encompassing a broad range of cut, matching, and scheduling problems. Here we present a recent line of work obtaining provably faster algorithms for solving the maximum flow problem using interior point methods. In particular, we show how to solve the maximum flow problem in $m$-edge unit capacity graphs in time almost $m^{4/3}$, improving over the breakthrough $m^{10/7}$ time algorithm of Mądry.

This is based on joint work with Aaron Sidford (arxiv.org/abs/1910.14276, arxiv.org/abs/2003.08929).

TCS+ talk: Wednesday, November 25 — The Coin Problem with Applications to Data Streams

The next TCS+ talk will take place this coming Wednesday, November 25th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Sumegha Garg from Harvard University will speak about “The Coin Problem with Applications to Data Streams” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: 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 $\Omega(\log n)$ bits of space. Previously, it was known that computing the majority on every input with a constant probability takes $\Omega(\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.

TCS+ talk: Wednesday, November 11 — Shuai Shao, UW-Madison

The next TCS+ talk will take place this coming Wednesday, November 11th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Shuai Shao from UW-Madison will speak about “A Dichotomy for Real Boolean Holant Problems” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: In this talk, we present a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions as in previous results. It is proved that for every set $F$ of real-valued constraint functions, $\text{Holant}(F)$ is either $P$-time computable or $\#P$-hard. The classification has an explicit criterion. This is a culmination of much research on a decade-long classification program for Holant problems, and it uses previous results and techniques from many researchers. However, as it turned out, the journey to the present theorem has been arduous. Some particularly intriguing concrete functions f6, f8 and their associated families with extraordinary closure properties related to Bell states in quantum information theory play an important role in this proof.

Based on joint work with Jin-Yi Cai.

TCS+ talk: Wednesday, November 4 — Shalev Ben-David, University of Waterloo

The next TCS+ talk will take place this coming Wednesday, November 4th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Shalev Ben-David from University of Waterloo will speak about “Forecasting Algorithms, Minimax Theorems, and Randomized Lower Bounds” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

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

TCS+ talk: Wednesday, October 28 — Omar Montasser, TTIC

The next TCS+ talk will take place this coming Wednesday, October 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Omar Montasser from TTIC will speak about “Adversarially Robust Learnability: Characterization and Reductions” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We study the question of learning an adversarially robust predictor from uncorrupted samples. We show that any VC class $H$ is robustly PAC learnable, but we also show that such learning must sometimes be improper (i.e. use predictors from outside the class), as some VC classes are not robustly properly learnable. In particular, the popular robust empirical risk minimization approach (also known as adversarial training), which is proper, cannot robustly learn all VC classes. After establishing learnability, we turn to ask whether having a tractable non-robust learning algorithm is sufficient for tractable robust learnability and give a reduction algorithm for robustly learning any hypothesis class $H$ using a non-robust PAC learner for $H$, with nearly-optimal oracle complexity.
This is based on joint work with Steve Hanneke and Nati Srebro, available at https://arxiv.org/abs/1902.04217.