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:
Date  Speaker  Talk Title 
January 25  Social  
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 constantdepth 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 allpairs maxflow

March 15  Shuchi Chawla (UW–Madison)  Pandora’s Box with Correlations: Learning and Approximation 
March 22  Andrea Lincoln (UC Berkeley)  New Techniques for Proving FineGrained AverageCase Hardness 
March 29  Nicole Wein (MIT)  Approximating the Diameter of a Graph 
April 5  Luowen Qian  Tight Quantum TimeSpace Tradeoffs for Function Inversion 
April 12  Omri BenEliezer (Harvard)  Adversarially Robust Streaming Algorithms 
April 21  Nick Spooner (BU)  PostQuantum Succinct Arguments 
April 26  Jonathan Huggins (CDS BU)  Statistical Inference with Stochastic Gradient Algorithms 
Abstracts
Speaker: John Kallaugher
Title: Separations and Equivalences between Turnstile Streaming and Linear Sketching
Abstract:
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 smallspace 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
Abstract:
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 realworld 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 constantdepth circuits and applications to MCSP
Abstract:
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 fanin circuits that given a function f, constructs a function g, so that the depth d+1 (averagecase) complexity of g is controlled by the depth d (averagecase) 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 gapversions of AC0MCSP. 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 AC0MCSP that we propose), or stronger than known AC0 circuit lower bounds.
Speaker: Krzysztof Onak
Title: Dynamic Algorithms for Tracking Patterns in Sparse Graphs
Abstract:
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 allpairs maxflow
Abstract:
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
Abstract:
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 realworld settings. In this work, we provide the first approximation algorithms for Pandora’s Boxtype 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 FineGrained AverageCase Hardness
Abstract:
In this talk I will cover a new technique for worstcase to averagecase reductions. There are two primary concepts introduced in this talk: “factored” problems and a framework for worstcase to averagecase finegrained (WCtoACFG) self reductions.
We will define new versions of OV, kSUM and zerokclique that are both worstcase and averagecase finegrained hard assuming the core hypotheses of finegrained complexity. We then use these as a basis for finegrained hardness and averagecase 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, kLCS and versions of MaxFlow. 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 [BoixAdsera et al. 2019] that was used to give a WCtoACFG reduction for counting kcliques. 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 finegrained averagecase 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
Abstract:
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 allpairs 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 tradeoff algorithms and hardness for diameter.
Speaker: Luowen Qian
Title: Tight Quantum TimeSpace Tradeoffs for Function Inversion
Abstract:
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 wellknown 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 CorriganGibbs and Kogan (2019). Prior knowledge on quantum computation is not assumed but will be helpful.
This is based on joint work with KaiMin Chung, Siyao Guo, and Qipeng Liu, which appeared in FOCS 2020.
Speaker: Omri BenEliezer
Title: Adversarially Robust Streaming Algorithms
Abstract:
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 wellsuited 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: PostQuantum Succinct Arguments
Abstract:
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 postquantum 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
Abstract:
Stochastic gradient algorithms are widely used for largescale learning and inference problems. However, their use in practice is typically guided by heuristics and trialanderror rather than rigorous, generalizable theory. We take a step toward better understanding the effect of tuning parameter choices by characterizing the largesample 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 finitesample 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 Miseslimit 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 largesample 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.