We study the sparsification of objectives $f(x) = \sum_{i=1}^m f_i()$, for vectors $a_1, ..., a_m, x \in R^n$. Informally, we show that if all the functions $f_i$ are nearly symmetric, and grow subquadratically, then $f$ has be sparsified down to $\tilde{O}(n * \epsilon^{-2})$ terms with $(1+\epsilon)$ multiplicative error. Our result generalizes the classical case of $l_p$ norm sparsification, where the functions $f_i(x) = |x|^p$ for $0 < p \le 2$. As an application, we obtain nearly-optimal algorithms to solve $l_p$-norm regression to high accuracy for $1 < p \le 2$.

Non-local games are an important concept in quantum information theory that allow two or more provers to demonstrate, to a classical verifier, the ability to prepare certain kinds of quantum systems. Two important applications include (multi-prover) protocols for (1) the demonstration of quantum advantage and (2) verifiable BQP computation. Key to these protocols is the physical assumption that the "far apart" provers cannot communicate.

In this talk, we will discuss how to emulate the effects of non-local games in an interactive, single-prover protocol, replacing the physical non-locality assumption with a cryptographic hardness assumption. These ideas have led to new interactive protocols for quantum advantage as well as for BQP verification.

This talk is based on joint works with Yael Kalai, Vinod Vaikuntanathan, Lisa Yang, and Fermi Ma.

A graph is said to be a 1-dimensional expander if the second eigenvalue of its adjacency matrix is bounded away from 1, or if it has no sparse vertex cuts. There are several natural ways to generalize the notion of expansion to hypergraphs/simplicial complexes, but one such way is 2-dimensional spectral expansion, in which the local expansion of vertex links/neighborhoods witnesses global expansion. While 1-dimensional expansion is known to be achieved by, e.g., random regular graphs, very few examples of sparse 2-dimensional expanders are known, and at present all are algebraic. It is an open question whether sparse 2-dimensional expanders are natural and abundant.

In this talk, we give some evidence towards abundance: we show that the set of triangles in a random geometric graph on a high-dimensional sphere yields an expanding simplicial complex of arbitrarily small polynomial degree.

Based on joint work with Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang.

In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This beautiful conjecture, if true, has implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Via a simple reduction technique followed by iterative relaxation, we show that the thin tree conjecture is true for laminar families of cuts. This resolves an open question of Olver and Zenklusen from 2013, a work that showed thin trees exist for chains of cuts. As a byproduct, we also obtain the first constant factor approximation algorithm for the laminar-constrained spanning tree problem. Based on joint work with Neil Olver.

I will describe recent progress on providing rigorous convergence guarantees for score-based generative models (SGMs) such as denoising diffusion probabilistic models (DDPMs), which constitute the backbone of large-scale real-world generative models such as DALL⋅E. In the first part of the talk, I will show that such SGMs can efficiently sample from essentially any realistic data distribution, even ones which are highly non-log-concave. In the second part of the talk, I will show how to extend these guarantees to deterministic samplers based on discretizing the so-called probability flow ODE, which ultimately leads to better dependence on the dimension. All of these results assume access to an oracle for score estimation; time permitting, at the end I will briefly touch upon how to provably implement this oracle for interesting classes of distributions like Gaussian mixtures.

We define the notion of zero-knowledge in the streaming setting and construct zero-knowledge SIPs for the two main building blocks in the streaming interactive proofs literature: the sumcheck and polynomial evaluation protocols. To the best of our knowledge all known streaming interactive proofs are based on either of these tools, and indeed, this allows us to obtain zero-knowledge SIPs for central and well-studied streaming problems, such as index, frequency moments, and inner product. Our protocols are efficient both in terms of time and space, as well as communication: the space complexity is polylog(n) and, after a non-interactive setup that uses a random string of near-linear length, the remaining parameters are sub-polynomial.

En route, we develop a toolkit for designing zero knowledge data stream protocols that may be of independent interest, consisting of an algebraic streaming commitment protocol and a temporal commitment protocol. The analysis of our protocols relies on delicate algebraic and information-theoretic arguments and reductions from average-case communication complexity.

Sampler graphs are sparse graphs that "derandomize" Chernoff’s inequality. These graphs are equivalent to randomness extractors and are widely used in other areas of TCS. In this talk we will see that high dimensional expanders (HDXs) give rise to nearly optimal samplers. These are hypergraph analogues of expander graphs. Then we will see some applications such as reverse hypercontractivity inequalities on HDXs and new agreement theorems. This is a joint work with Max Hopkins (UCSD).

We study the basic statistical problem of testing whether normally distributed -dimensional data has been truncated, i.e. altered by only retaining points that lie in some unknown truncation set . As our main algorithmic results,

We give a computationally efficient -sample algorithm that can distinguish the standard normal distribution from conditioned on an unknown and arbitrary convex set .

We give a different computationally efficient -sample algorithm that can distinguish from conditioned on an unknown and arbitrary mixture of symmetric convex sets.

These results stand in sharp contrast with known results for learning or testing convex bodies with respect to the normal distribution or learning convex-truncated normal distributions, where state-of-the-art algorithms require essentially samples. An easy argument shows that no finite number of samples suffices to distinguish from an unknown and arbitrary mixture of general (not necessarily symmetric) convex sets, so no common generalization of results (1) and (2) above is possible.

We also prove lower bounds on the sample complexity of distinguishing algorithms (computationally efficient or otherwise) that match our algorithms up to constant factors.

Joint with Anindya De and Shivam Nadimpalli.

In the multiparty set disjointness problem, we have k players, with private inputs X1,...,Xk \subseteq [n]. The players’ goal is to check whether their sets intersect, or sometimes to compute the full intersection. It is known that in the shared blackboard model of communication, set disjointness requires Omega(n log k + k) bits of communication, and in the coordinator model, it requires Omega(nk) bits. However, these two lower bounds require that the players’ inputs can be highly correlated.

We study the communication complexity of multiparty set disjointness under product distributions, and ask whether the problem becomes significantly easier, as it is known to become in the two party case. Our main result is a nearly-tight bound of tilde-Theta(n^{1-1/k}) bits for both the shared blackboard model and the coordinator model. This shows that in the shared blackboard model, as the number of players grows, having independent inputs helps less and less; but

in the coordinator model, when k is very large, having independent inputs makes the problem much easier. Both our upper and our lower bounds use new ideas, as the original techniques developed for the two-party case do not scale to more than two players.

In this talk, we will introduce a new notion of information complexity for multi-pass streaming problems, and use it to prove multi-pass lower bounds for the coin problem. In the coin problem, one sees a stream of 𝑛 i.i.d. uniform bits and one would like to compute the majority with constant advantage. We show that any constant pass algorithm must use Ω(log 𝑛) bits of memory, significantly extending an earlier Ω(log 𝑛) bit lower bound for single-pass algorithms of [BGW'20]. In the paper, we also use this information complexity notion to prove tight space complexity for the needle problem, which in turn implies tight bounds for the problem of approximating higher frequency moments in a data stream.

Joint work with Mark Braverman, Qian Li, Shuo Wang, David P. Woodruff and Jiapeng Zhang.

In active learning, one seeks to learn the parameters of a model given examples, while minimizing the number of labels read. We give tight bounds up to logarithmic factors on the number of labels that need to be read for active l_p regression for every value of p, as a function of the number of variables and accuracy desired. Previously tight bounds were known only for p = 1 or p =2. We extend these ideas to a large class of loss functions with certain nice conditions, obtaining the first non-trivial bounds for such functions.

Based on joint works, one with Musco, Musco, and Yasuda (FOCS '22) and another with Yasuda (STOC '23).

The Walsh-Hadamard transform is a simple recursively-defined linear transformation with many applications throughout algorithm design and complexity theory. The folklore "fast Walsh-Hadamard transform" algorithm computes it using only N log N arithmetic operations, which is believed to be optimal up to constant factors. In this talk, I'll give two improved constructions:

- A new algorithm which uses $(23/24) N log N + O(N)$ arithmetic operations. This is, to my knowledge, the first improvement of the leading constant. (Based on joint work with Kevin Rao.)

- A new depth-2 linear circuit of size $O(N^{1.45})$, improving on size $O(N^{1.5})$ which one gets from the fast Walsh-Hadamard transform approach. (Based on joint work with Ashwin Padaki and Yunfeng Guan.)

A key idea behind both constructions is to take advantage of the matrix non-rigidty of the Walsh-Hadamard transform. A matrix is called "rigid" if it's impossible to change a "small" number of its entries to make it have "low" rank. L. Valiant showed that if a matrix is rigid, then this implies lower bounds for computing its linear transformation. However, a recent line of work has shown that many matrices of interest, including the Walsh-Hadamard transform, are actually not rigid. Although a formal converse to Valiant's result is not known, we'll make use of non-rigidity in our new constructions.

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges. The problem is notoriously difficult, and despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a O(n)-approximation, while the best current negative results do not rule out constant-factor approximation. All current approximation algorithms for the problem build on the same paradigm, which is also used in practice: compute a set E’of edges (called a planarizing set) such that G \ E’ is planar; compute a planar drawing of G \ E’; then add the drawings of the edges of E to the resulting drawing. Unfortunately, there are examples of graphs G, in which any implementation of this method must incur Ω(OPT2) crossings, where OPT is the value of the optimal solution. This barrier seems to doom the only currently known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than O(n)-approximation.

We propose a new paradigm that allows us to overcome this barrier. Using the new paradigm, we reduce the Crossing Number problem to Crossing Number with Rotation System – a variant of the Crossing Number problem, in which the ordering of the edges incident to every vertex is fixed as part of input. We then show a randomized algorithm for this new problem, that allows us to obtain a subpolynomial approximation for Graph Crossing Number on low-degree graphs.

This talk is based on joint work with Julia Chuzhoy and Sepideh Mahabadi.

Over the last decade or so, combining methods from continuous optimization and analysis with graph theoretic-insights has led to a revolution in algorithms for classic problems on graphs such as maximum flow.

In this talk, I will present some of our key ideas behind our recent work that gives almost-linear time algorithms for solving all convex flow problems on graphs. This implies almost linear time algorithms for max-flow, minimum-cost flow, bipartite matching, optimal transport, matrix scaling, isotonic regression, and several other well-studied problems.

Our algorithm is designed using a new Interior Point Method (IPM) that builds the flow as a sequence of almost-linear number of approximate undirected minimum-ratio cycles, each of which is computed and processed very efficiently using a new dynamic data structure.

Joint work with Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, and Maximilian Probst Gutenberg.

Machine learning provides us with an amazing set of tools to make predictions, but how much should we trust particular predictions? To answer this, we need a way of estimating the confidence we should have in particular predictions of black-box models. Standard tools for doing this give guarantees that are averages over predictions. For instance, in a medical application, such tools might paper over poor performance on one medically relevant demographic group if it is made up for by higher performance on another group. Standard methods also depend on the data distribution being static --- in other words, the future should be like the past.

In this talk, I will describe new techniques to address both these problems: a way to produce prediction sets for arbitrary black-box prediction methods that have correct empirical coverage even when the data distribution might change in arbitrary, unanticipated ways and such that we have correct coverage even when we zoom in to focus on demographic groups that can be arbitrary and intersecting. When we just want correct group-wise coverage and are willing to assume that the future will look like the past, our algorithms are especially simple. Our approach is based on a quantile analogue of (mean) multi-calibration, a recent solution concept arising from the algorithmic fairness literature. We close by asking which distributional properties (beyond means and quantiles) we can achieve multicalibration with respect to, and provide a complete characterization via a connection to property elicitation.

This talk is based on two papers, that are joint work with Osbert Bastani, Varun Gupta, Chris Jung, Georgy Noarov, and Ramya Ramalingam.

Min-max optimization is a classical problem in optimization and game theory and has recently played a central role in modern machine learning (ML) applications. These applications range from generative adversarial networks, adversarial examples, robust optimization, to multi-agent reinforcement learning. These ML applications present novel challenges to min-max optimization, necessitating that algorithms (i) demonstrate last-iterate convergence, in contrast to the more traditional average-iterate convergence, and (ii) be robust in nonconvex-nonconcave environments.

In this talk, we first focus on the last-iterate convergence rates of two classical and widely-used algorithms for solving convex-concave min-max optimization – the extragradient (EG) method by Korpelevich (1976) and the optimistic gradient (OG) method by Popov (1980). Despite the considerable attention these algorithms have received from both the optimization and machine learning communities over the years, the last-iterate convergence rates for both algorithms remained open. We resolve this open problem by showing both EG and OG exhibit a tight O(1/\sqrt{T}) last-iterate convergence rate under arbitrary convex constraints. In the second part of the talk, we discuss some recent progress on designing optimal first-order methods for structured nonconvex-nonconcave min-max optimization. Our results are obtained via a new sum-of-squares programming based approach, which may be useful in analyzing other iterative methods. The talk is based on joint work with Argyris Oikonomou and Weiqiang Zheng.

Talk 1: School districts in many cities employ school choice mechanisms, i.e., algorithms matching students to schools on the basis of students’ reported preferences, and the priorities students have for attending each school. Since simplicity and ease of participation are paramount to these mechanisms, an exact understanding of their structural complexities—e.g., how the matching can be described, and how one student’s input can affect the outputs—should be a first-order concern.

In this talk, I will give one example of this type of complexity: that of describing the outcome matching. Prior work has observed that for one popular real-world mechanism (DA), the outcome can be described in terms of a single "priority cutoff" per school, even when there are many more students than there are schools. We prove that, for another popular mechanism (TTC), the outcome cannot be described using less than a bit for each pair of schools. This result clarifies and formalizes one way in which, as often informally argued in both the literature and in practice, TTC may be more complex than DA.

Depending on time, I may also mention connections to verification (in the sense of nondeterministic communication), and how we formalize the question "how sensitive is the mechanism to one student’s input" in this setting.

Based on joint work with Yannai Gonczarowski.

Talk 2: Two of the fundamental no-go theorems of quantum information are the no-cloning theorem (that it is impossible to make copies of general quantum states) and the no-teleportation theorem (the prohibition on sending quantum states over classical channels without pre-shared entanglement). They are known to be equivalent, in the sense that a collection of quantum states is clonable if and only if it is teleportable.

Our main result suggests that this is not the case when computational efficiency is considered. We give a collection of quantum states and oracles relative to which these states are efficiently clonable but not efficiently teleportable. Given that the opposite scenario is impossible (states that can be teleported can always trivially be cloned), this gives the most complete oracle separation possible between these two important no-go properties.

In doing so, we introduce a related quantum no-go property, reconstructibility, which refers to the ability to construct a quantum state from a uniquely identifying classical description. We show the stronger result of a collection of quantum states that are efficiently clonable but not efficiently reconstructible. This novel no-go property only exists in relation to computational efficiency, as it is trivial for unbounded computation. It thus opens up the possibility of further computational no-go properties that have not yet been studied because they do not exist outside the computational context.

Joint work with Mark Zhandry.

Constructing decision tree representations of data is a basic problem of computer science, sitting right at the boundary of our understanding of efficient computation. I will discuss two recent results about this problem, a new algorithm and a new lower bound:

1. An almost-polynomial time membership query algorithm for the uniform-distribution setting. The previous fastest algorithm ran in quasipolynomial time, a consequence of a classic algorithm of Ehrenfeucht and Haussler from 1989. (https://dl.acm.org/doi/abs/10.1145/3561047)

2. A conditional quasipolynomial lower bound for the distribution-free setting, matching the upper bound of Ehrenfeucht and Haussler. This builds on and improves upon prior work by Alekhnovich, Braverman, Feldman, Klivans, and Pitassi from 2004. (https://arxiv.org/abs/2210.06375)

Joint work with Guy Blanc, Caleb Koch, Jane Lange, Mingda Qiao, and Carmen Strassle.

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

We present a new approach for finding matchings in dense graphs by building on Szemeredi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit (very) slight improvements over long-standing bounds for computing near-optimal matchings in streaming and dynamic graphs. The key idea behind our improved bounds is to maintain a matching cover which is a “sparse” subgraph that approximately preserves matchings in each induced subgraph of the input graph. However, given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some function of $(log* n)$. Nevertheless, these results show that the “right” answer to these problems is not what is dictated by the previous bounds.

This is joint work with Sepehr Assadi, Soheil Behnezhad, and Huan Li.

Three decades of quantum complexity theory have largely focused on quantum algorithms for classical tasks -- those with classical inputs and outputs. However there has been increasing interest in studying the computational difficulty of tasks with quantum inputs and/or outputs. Examples include preparing ground states of Hamiltonians or breaking quantum cryptographic protocols. Many techniques and approaches from traditional complexity theory are inadequate for reasoning about such inherently quantum tasks, suggesting a need for a "fully quantum" complexity theory.

In this talk I discuss some facets and themes of a "fully quantum" complexity theory. In particular I show that seemingly-unrelated quantum tasks such as achieving capacity over a noisy quantum channel, breaking a quantum bit-commitment scheme, and decoding the radiation of an evaporating black hole are all polynomial-time equivalent to something called the Uhlmann Transformation Problem. I also show that the Uhlmann Transformation Problem is complete for a "unitary complexity" analogue of SZK. Along the way I describe our framework for classifying the complexity of unitary synthesis problems.

Joint work with John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, and Luowen Qian.

The decades-old Patience Sorting algorithm computes the Longest Increasing Subsequence (LIS) of a sequence of length n in O(n log n) time. Yet, it is unknown how well one can estimate the (length of the) LIS in *sublinear* time, say, when it is >sqrt{n}?

We present an algorithm that, given a sequence with LIS > n/k, approximates the LIS up to a factor of k^c in k*n^c time for any arbitrarily small c>0. Our run-time essentially matches the trivial sample complexity lower bound of ~k. All the past work had polynomial factors in both approximation and extra time slowdown.

An important corollary is the first algorithm to estimate the Longest *Common* Subsequence in O(n) time up to a sub-polynomial, n^o(1), factor.

Our algorithm is based on a van Emde Boas style recursion. To accomplish such a recursion for a sublinear algorithm, we develop a generic sampling scheme that allows efficient composition of recursive sampling algorithms.

Joint work with Negev Shekel Nosatzki, Sandip Sinha, and Cliff Stein.

In the talk, we discuss the probability of Boolean functions with small max influence to become constant under random restrictions. Let f be a Boolean function such that the variance of f is $\Omega(1)$ and all its individual influences are bounded by $\tau$. We show that when restricting all but a $\tilde{\Omega}((\log1/\tau)^{-1})$ fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function $AND_{n/C\log n} \circ OR_{C\log n}$.

We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability $1-o(1)$. This gives a sharp version of the "it ain't over till it's over" theorem due to Mossel, O'Donnell, and Oleszkiewicz.

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, can be negative, and are $\geq -W$. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are $\~{O}((m+n^{1.5})\log W)$ and $m^{4/3+o(1)}\log W$. Near-linear time algorithms were known previously only for the special case of planar directed graphs. Also, independently of our work, the recent breakthrough on min-cost flow [Chen, Kyng, Liu, Peng, Probst-Gutenberg and Sachdeva] implies an algorithm for negative-weight SSSP with running time $m^{1+o(1)}$.

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. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic $O(m\sqrt{n}\log nW)$ bound from over three decades ago [Gabow and Tarjan SICOMP'89].

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge (SZK), as well as the related classes NISZK_L and SZK_L.

This is joint work with Shuichi Hirahara and Harsha Tirumala. A paper is available as ECCC TR22-127.

This talk will present two new directions in the study of derandomization, which are related to each other. The talk is based on a sequence of recent works with Lijie Chen (some of the works are upcoming).

The first direction is avoiding classical PRGs in favor of *non-black-box techniques*, which extract pseudorandomness for a probabilistic machine from the code of that specific machine. This approach allows constructing derandomization algorithms from weaker hypotheses (compared to classical results), and also constructing very fast derandomization algorithms that cannot be obtained using classical PRGs. The second direction is the fine-grained study of *superfast derandomization*, asking what is the smallest possible overhead that we need to pay when eliminating randomness (and whether we can get away with paying nothing at all).

As examples, we will mention four results:

1. Connecting the BPP = P conjecture to new types of lower bounds.

2. "Free lunch" derandomization with essentially no time overhead.

3. Superfast derandomization of interactive proof systems.

4. Average-case derandomization from weak hardness assumptions. (Joint work with Ron Rothblum.)

Expander graphs are fundamental objects in theoretical computer science and mathematics. They have numerous applications in diverse fields such as algorithm design, complexity theory, coding theory, pseudorandomness, group theory, etc.

In this talk, we will describe an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d \leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree $d$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders.

This transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects.

Our results generalize Ta-Shma's technique in his breakthrough paper [STOC 2017] used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma's analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way.

Joint work with: Tushant Mittal, Sourya Roy and Avi Wigderson

We show that there exists a convex body that tiles $\mathbb{R}^n$ under translations by $\mathbb{Z}^n$ whose surface area is $\tilde{O}(\sqrt{n})$. No asymptotic improvement over the trivial $O(n)$ (achieved by the cube $[0,1]^n$) was previously known. A non-convex body achieving surface area $O(\sqrt{n})$ was constructed by Kindler, O’Donnell, Rao, and Wigderson [FOCS 2008].

For some fun background on this question, see Kindler et al.'s CACM article: https://cacm.acm.org/magazines/2012/10/155546-spherical-cubes/fulltext and Klarreich's broader review: https://www.jstor.org/stable/27857995.

Joint work with Assaf Naor.

The problem of learning from imbalanced datasets, where the label classes are not equally represented, arises often in practice. A widely used method to combat this problem is preprocessing techniques to amplify the minority class, e.g., by reusing or resampling the existing minority instances. However, when the training data are sensitive and privacy is a concern, this will also amplify privacy leakage from members of the minority class. Therefore this oversampling pre-processing step must be designed with privacy in mind. In this work, we present an algorithm for differentially private synthetic minority oversampling technique (DP-SMOTE) that guarantees formal privacy for the minority class. We show empirically that there is no statistically significant loss in performance relative to existing non-private SMOTE tools. We also show that even when non-private SMOTE is used as a part of a DP learning pipeline as a pre-processing step before downstream private classification, the upstream non-private oversampling increases sensitivity exponentially in the dimensionality of the data, which harms classification accuracy at a corresponding rate. The algorithmic structure also yields insights about the implications for pre-processing before the use of DP algorithms, which may be of independent interest.

(joint work with Yuliia Lut, Eitan Turok, and Marco Avella Medina)

The relatively new Hypergraph Container Method (Saxton and Thomason 2015, Balogh, Morris and Samotij 2015), generalizing an earlier version for graphs (Sapozhenko 2001), has been used extensively in recent years in extremal combinatroics. In essence, it shows that independent sets in regular-enough uniform hypergraphs must be clustered in some fashion. We show how to use this method algorithmically to convert algorithms for arbitrary inputs into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum degree is larger than the average degree by at most a constant factor. This vastly generalizes several families of inputs for which we commonly have improved algorithms.

An important component of our work is the generalization of (hyper-)graph containers to Partition Containers. While standard containers apply to a single independent set, partition containers apply to several independent sets at the same time.

Our first main application is a resolution of a major open problem about Graph Coloring algorithms, for almost-regular graphs. The chromatic number of a graph can be computed in $2^n$. Better algorithms are known only for $k<7$. We solve $k$-coloring in $(2-\epsilon)^n$ time for graphs in which the maximum degree is at most $C$ times the average degree, where $\epsilon > 0$ for any $k, C$. This includes, for example, regular graphs of any degree (with $C = 1$), and graphs with at least $\epsilon n^2$ edges for any fixed constant $\epsilon$ (with $C = 1 / 2 \epsilon$).

Our second main application is the first improved $k$-SAT algorithm for dense formulas. The celebrated sparsification lemma (Impagliazzo, Paturi and Zane 2001) implies that solving $k$-SAT can be reduced to solving $k$-SAT on sparse formulas. We show a complementing statement; For every $k, b$ there exists a $C$ such that if $k$-SAT can be solved in $b^n$ time, then $k$-SAT on formulas with at least $C \cdot n$ clauses that are well-spread can be solved in $(b-\epsilon)^n$ time.

We give additional applications including faster algorithms for unweighted and weighted Maximum Independent Set in almost-regular graphs.

The linear-probing hash table is one of the oldest and most widely used data structures in computer science. However, linear probing also famously comes with a major drawback: as soon as the hash table reaches a high memory utilization, elements within the hash table begin to cluster together, causing insertions to become slow. This phenomenon, now known as "primary clustering", was first captured by Donald Knuth in 1963; at a load factor of $1 - 1/x$, the expected time per insertion becomes $\Theta(x^2)$, rather than the more desirable $\Theta(x)$.

We show that there is more to the story than the classic analysis would seem to suggest. It turns out that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions. If these design decisions are made correctly, then even a hash table that is continuously at a load factor $1 - \Theta(1/x)$ can achieve average insertion time $\tilde{O}(x)$. A key insight is that the tombstones left behind by deletions cause a surprisingly strong "anti-clustering" effect, and that when insertions and deletions are one-for-one, the anti-clustering effects of deletions actually overpower the clustering effects of insertions.

We also present a new variant of linear probing, which we call "graveyard hashing", that completely eliminates primary clustering on any sequence of operations. If, when an operation is performed, the current load factor is $1 - 1/x$ for some $x$, then the expected cost of the operation is $O(x)$.

Based on joint work with Michael A. Bender and Bradley C. Kuszmaul. FOCS '21. Available at https://arxiv.org/abs/2107.01250.

Talk 1: We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in an ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then study the approximation ratios achievable by dominant strategy mechanisms. For combinatorial auctions with general valuations, we show that no dominant-strategy mechanism achieves an approximation ratio of $m^{1−\eps}$, where m is the number of items. In contrast, a randomized dominant strategy mechanism that achieves an O(√m) approximation. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones. Joint work with Shahar Dobzinski and Jan Vondrak.

Talk 2: In this talk, I will present our study on classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n^2) bits of classical memory or $\Omega(n)$ bits of quantum memory or an exponential number of samples. The work by Raz showed that any classical algorithm requires either Ω(n^2) bits of memory or an exponential number of samples, and our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning. I will briefly review the techniques used in the proof for classical memory-sample lower bound, discuss what prevents us from directly applying these techniques to the quantum case, and give a sketch of the actual proof for our results. This is a joint work with Qipeng Liu and Ran Raz.

The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We present a new algorithm that constructs a strong learner from a weak learner but uses less training data than AdaBoost and all other weak to strong learners to achieve the same generalization bounds. A sample complexity lower bound shows that our new algorithm uses the minimum possible amount of training data and is thus optimal. Hence, this work settles the sample complexity of the classic problem of constructing a strong learner from a weak learner.

This work was accepted at NeurIPS’22 and is joint work with Martin Ritzert from Aarhus University

Since the introduction of randomness as an algorithmic tool, researchers have been trying to study how to reduce the amount of randomness that these probabilistic algorithms need. This is achieved through lots of different ways, but a common one is to develop algorithms that produce objects (like sequences of bits) that "look random" enough that they fool probabilistic algorithms. These algorithms that produce random looking objects are known as pseudorandom generators. In addition to the intrinsic motivation of understanding how randomness and computation interact, there is a broader appeal to using these tools to find explicit constructions of objects that are known to exist through probabilistic methods.

One of the many successes of this area is the observation that very often we only need bounded independence. Broadly speaking, sampling a truly uniform random $N$-dimensional object may require $\Omega(N)$ bits of randomness, but for many applications it is sufficient to use objects that only look truly random when inspecting $k \ll N$ dimensions, known as "$k$-wise independent". One basic example of this is $k$-wise independent permutations: a distribution over of permutations on $N$ elements is $k$-wise independent if a permutation sampled from it maps any distinct $k$ elements to any distinct $k$ elements equally likely (i.e. any subset of $k$ elements looks uniform). Thanks to Kassabov [Kas07] and Kaplan–Naor–Reingold [KNR09], it turns out that such a distribution can be created using only $O(k\log N)$ random bits to sample from (with a small error), much less than in the fully independent case.

In this talk, we present a framework that generalizes these works to obtain $k$-wise independent approximate orthogonal and unitary matrices (formally known as approximate orthogonal/unitary designs). Given a classical group of Lie type with certain properties, our framework uses the properties of the group to approximate to "$k$-locally" approximate the Haar (uniform) measure over elements of the group. We do so by first showing how to obtain a pseudorandom generator with a non-trivial yet big error, and then showing how to reduce this error using a generalization of expander random walks to operators.

Joint work with Ryan O'Donnell and Rocco Servedio