Algorithms and Theory Seminar
Weekly Algorithms and Theory seminars are held online on Mondays from 11 am to 12 pm for the Spring 2021 semester. Below is a list of seminar dates with information on the speakers:
|February 1||John Kallaugher (UT Austin)||Separations and Equivalences between Turnstile Streaming and Linear Sketching|
|February 8||Andrew McGregor (UMass)||Recent Results on Cycle Counting in the Data Stream Model|
|February 16||Ken Hoover (UCSD)||Lifting for constant-depth circuits and applications to MCSP|
|February 22||Krzysztof Onak (CDS BU)||Dynamic Algorithms for Tracking Patterns in Sparse Graphs|
|March 1||Kira Goldner (Columbia)||Mechanism Design for Social Good|
|March 8||Ohad Trabelsi (Weizmann)||
New algorithms and lower bounds for all-pairs max-flow
|March 15||Shuchi Chawla (UW–Madison)||Pandora’s Box with Correlations: Learning and Approximation|
|March 22||Andrea Lincoln (UC Berkeley)||New Techniques for Proving Fine-Grained Average-Case Hardness|
|March 29||Nicole Wein (MIT)||Approximating the Diameter of a Graph|
|April 5||Luowen Qian||Tight Quantum Time-Space Tradeoffs for Function Inversion|
|April 12||Omri Ben-Eliezer (Harvard)||Adversarially Robust Streaming Algorithms|
|April 21||Nick Spooner (BU)||Post-Quantum Succinct Arguments|
|April 26||Jonathan Huggins (CDS BU)||Statistical Inference with Stochastic Gradient Algorithms|
Speaker: John Kallaugher
Title: Separations and Equivalences between Turnstile Streaming and Linear Sketching
It was shown in [Li, Nguyên, Woodruff `14] that, if a turnstile algorithm works for arbitrarily long streams with arbitrarily large coordinates at intermediate stages of the stream, then the turnstile algorithm is equivalent to a linear sketch. We show separations of the opposite form: if either the stream length or the maximum value of the stream are substantially restricted, there exist problems where linear sketching is exponentially harder than turnstile streaming.
A further limitation of the [Li, Nguyên, Woodruff `14] equivalence is that the turnstile sketching algorithm is neither explicit nor uniform, but requires an exponentially long advice string. We show how to remove this limitation for deterministic streaming algorithms: we give an explicit small-space algorithm that takes the streaming algorithm and computes an equivalent module.
Speaker: Andrew McGregor
Title: Recent Results on Cycle Counting in the Data Stream Model
Estimating the number of cycles in a graph is one of the most widely studied graph problems in the data stream model. From the theoretical perspective, it is a convenient problem to explore the efficacy of various sampling techniques and to understand the limits of stream computation. From an applied perspective, the frequency of cycles and other subgraphs captures interesting structural properties of massive real-world graphs. Three relevant variants of the data stream model include: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order, the random order model in which the edges are randomly permuted, and the adjacency list order model in which all edges incident to the same vertex appear consecutively. In this talk, we survey recent work in all these models.
Speaker: Ken Hoover
Title: Lifting for constant-depth circuits and applications to MCSP
Lifting arguments show that the complexity of a function in one model is essentially that of a related function (often the composition of the original function with a small function called a gadget) in a more powerful model. Lifting has been used to prove strong lower bounds in communication complexity, proof complexity, circuit complexity and many other areas.
We present a lifting construction for constant depth unbounded fan-in circuits that given a function f, constructs a function g, so that the depth d+1 (average-case) complexity of g is controlled by the depth d (average-case) complexity of f. The function g is defined as f composed with a parity function. As an application, we show that being able to approximate the depth d (for any large constant d>3) circuit complexity of given (truth tables of) Boolean functions yields an algorithm for approximating the depth 3 circuit complexity of functions. These results are stated as reductions between gap-versions of AC0-MCSP. Our lifting results rely on a novel blockwise switching lemma that may be of independent interest.
We also show some barriers on improving the efficiency of our reductions: such improvements would either yield surprisingly efficient algorithms for MCSP (violating a new Weak Exponential Time Hypothesis for AC0-MCSP that we propose), or stronger than known AC0 circuit lower bounds.
Speaker: Krzysztof Onak
Title: Dynamic Algorithms for Tracking Patterns in Sparse Graphs
Counting graph patterns has various practical applications, including detecting fraud and anomalies in financial transactions and social networks. While the vast majority of previous work focuses on the static case and computing the global number of occurrences of a given pattern, I will show that using simple techniques, it is possible to efficiently track the number of copies of a pattern in which each vertex appears. I will demonstrate our techniques for simple graph patterns such as triangles, and cliques and cycles of size 4. As long as the graph has low arboricity, the update time of our algorithms is significantly sublinear in the number of vertices.
Joint work with Karthikeyan Shanmugam and Shay Solomon.
Speaker: Ohad Trabelsi
Title: New algorithms and lower bounds for all-pairs max-flow
When can maximum flow be solved for all pairs of nodes faster than naively solving it separately for each pair?
We will overview new algorithms – including a very recent result!, and also lower bounds (under some popular assumptions).
Speaker: Shuchi Chawla
Title: Pandora’s Box with Correlations: Learning and Approximation
The Pandora’s Box problem and its extensions capture optimization problems with stochastic input where the algorithm can obtain instantiations of input random variables at some cost. To our knowledge, all previous work on this class of problems assumes that different random variables in the input are distributed independently. As such it does not capture many real-world settings. In this work, we provide the first approximation algorithms for Pandora’s Box-type problems with correlations. We assume that the algorithm has access to samples drawn from the joint distribution on input.
Algorithms for these problems must determine an order in which to probe random variables, as well as when to stop and return the best solution found so far. In general, an optimal algorithm may make both decisions adaptively based on instantiations observed previously. Such fully adaptive (FA) strategies cannot be efficiently approximated to within any sublinear factor with sample access. We therefore focus on the simpler objective of approximating partially adaptive (PA) strategies that probe random variables in a fixed predetermined order but decide when to stop based on the instantiations observed. We consider a number of different feasibility constraints and provide simple PA strategies that are approximately optimal with respect to the best PA strategy for each case. All of our algorithms have polynomial sample complexity. We further show that our results are tight within constant factors: better factors cannot be achieved even using the full power of FA strategies.
This is joint work with Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang.
Speaker: Andrea Lincoln
Title: 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.
Speaker: Nicole Wein
Title: Approximating the Diameter of a Graph
I will talk about algorithms and conditional lower bounds for approximating the diameter of a graph (the largest distance between two vertices). The best known algorithm for exactly computing the diameter of a graph is the naive algorithm of computing all-pairs shortest paths (APSP) and taking the largest distance. Furthermore, no significantly better algorithm exists under the Strong Exponential Time Hypothesis. Running APSP can be prohibitively slow for very large graphs, so we seek much faster algorithms that produce an approximation of the diameter. I will discuss the landscape of time vs. accuracy trade-off algorithms and hardness for diameter.
Speaker: Luowen Qian
Title: Tight Quantum Time-Space Tradeoffs for Function Inversion
In function inversion, we are given oracle query access to a function f: [N] → [N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. It is natural to ask whether we can combine two well-known algorithms from the last century for this problem: one being the classical Hellman’s algorithm achieving tradeoff ST = N (for permutations), and the other being Grover’s search which uses quantum time ︀ T = √︀N but no advice.
We show that ST+ T² = ̃Ω(N) is required for any quantum algorithm to invert random functions, which is best possible without implying new (classical) circuit lower bounds as shown by Corrigan-Gibbs and Kogan (2019). Prior knowledge on quantum computation is not assumed but will be helpful.
This is based on joint work with Kai-Min Chung, Siyao Guo, and Qipeng Liu, which appeared in FOCS 2020.
Speaker: Omri Ben-Eliezer
Title: Adversarially Robust Streaming Algorithms
Streaming algorithms are traditionally categorized into two classes: deterministic algorithms and randomized ones. These two types of algorithms exhibit a tradeoff between robustness and efficiency; on one hand, deterministic algorithms always return a correct output, but for many important streaming problems, they are provably inefficient. On the other hand, efficient randomized algorithms are known for a very wide range of problems, but their correctness typically relies on the assumption that the stream is fixed in advance, which is commonly unrealistic in practice.
In this talk, I will focus on a middle ground that combines both robustness and efficiency: adversarially robust algorithms, whose output is correct with high probability even when the stream updates are adaptively chosen as a function of previous outputs. This regime has received surprisingly little attention until recently, and many intriguing problems are still open. I will mention some of the recent results, discussing algorithms that are well-suited for the adversarially robust regime (random sampling), algorithms that are not robust (linear sketching), and efficient techniques to turn algorithms that work in the standard static setting into robust streaming algorithms.
The results demonstrate strong connections between streaming and other areas such as online learning, differential privacy, cryptography, adaptive data analysis and statistics.
Based on joint works with Noga Alon, Yuval Dagan, Rajesh Jayaram, Shay Moran, Moni Naor, David Woodruff, and Eylon Yogev.
Speaker: Nick Spooner
Title: Post-Quantum Succinct Arguments
A succinct argument is a proof system for NP where the total communication is much smaller than the NP witness. Almost 30 years ago, Kilian showed how to build succinct arguments with security against classical adversaries, under standard cryptographic assumptions. In this work, we show that the same construction achieves security against quantum adversaries, under a standard post-quantum assumption. We achieve this by designing a quantum rewinding procedure which achieves “optimal” extraction error.
Speaker: Jonathan Huggins
Title: Statistical Inference with Stochastic Gradient Algorithms
Stochastic gradient algorithms are widely used for large-scale learning and inference problems. However, their use in practice is typically guided by heuristics and trial-and-error rather than rigorous, generalizable theory. We take a step toward better understanding the effect of tuning parameter choices by characterizing the large-sample behavior of iterates of a very general class of preconditioned stochastic gradient algorithms with fixed step size, including stochastic gradient descent with and without additional Gaussian noise, momentum, and/or acceleration. We show that near a local optimum, the iterates converge weakly to paths of an Ornstein–Uhlenbeck process, and provide sufficient conditions for the stationary distributions of the finite-sample processes to converge weakly to that of the limiting process. In particular, with appropriate choices of tuning parameters, the limiting stationary covariance can match either the Bernstein–von Mises-limit of the posterior, adjustments to the posterior for model misspecification, or the asymptotic distribution of the maximum likelihood estimate – and that with a naive tuning, the limit corresponds to none of these. Moreover, we argue that, in the large-sample regime, an essentially independent sample from the stationary distribution can be obtained after a fixed number of passes over the dataset. Our results show that properly tuned stochastic gradient algorithms offer a practical approach to obtaining inferences that are computationally efficient and statistically robust.