One of the most basic problems for studying the “price of privacy over time” is the so called {\em private counter problem}, introduced by Dwork et al. (2010) and Chan et al. (2011). In this problem, we aim to track the number of {\em events} that occur over time, while hiding the existence of every single event. More specifically, in every time step $t\in[T]$ we learn (in an online fashion) that $\Delta_t\geq 0$ new events have occurred, and must respond with an estimate $n_t\approx\sum_{j=1}^t \Delta_j$. The privacy requirement is that {\em all of the outputs together}, across all time steps, satisfy {\em event level} differential privacy. The main question here is how our error needs to depend on the total number of time steps $T$ and the total number of events $n$. Dwork et al. (2015) showed an upper bound of $O\left(\log(T)+\log^2(n)\right)$, and Henzinger et al. (2023) showed a lower bound of $\Omega\left( \min\{\log n, \log T\} \right)$. We show a new lower bound of $\Omega\left(\min\{n,\log T\}\right)$, which is tight w.r.t. the dependence on $T$, and is tight in the sparse case where $\log^2 n=O(\log T)$. Our lower bound has the following implications: \begin{itemize} \item We show that our lower bound extends to the {\em online thresholds} problem, where the goal is to privately answer many “quantile queries” when these queries are presented one-by-one. This resolves an open question of Bun et al. (2017). \item Our lower bound implies, for the first time, a separation between the number of mistakes obtainable by a private online learner and a non-private online learner. This partially resolves a COLT’22 open question published by Sanyal and Ramponi. \item Our lower bound also yields the first separation between the standard model of private online learning and a recently proposed relaxed variant of it, called {\em private online prediction}. \end{itemize}

We study the cost of parallelizing weak-to-strong boosting algorithms for learning, following the recent work of Karbasi and Larsen. Our main results are two-fold:•First, we prove a tight lower bound, showing that even “slight” parallelization of boosting requires an exponential blow-up in the complexity of training.Specifically, let γ be the weak learner's advantage over random guessing. The famous AdaBoost algorithm produces an accurate hypothesis by interacting with the weak learner for Õ(1/γ2)1 rounds where each round runs in polynomial time.Karbasi and Larsen showed that “significant” parallelization must incur exponential blow-up: Any boosting algorithm either interacts with the weak learner for Ω(1/γ) rounds or incurs an exp(d/γ) blow-up in the complexity of training, where d is the VC dimension of the hypothesis class. We close the gap by showing that any boosting algorithm either has Ω(1/γ2) rounds of interaction or incurs a smaller exponential blow-up of exp(d).•Complementing our lower bound, we show that there exists a boosting algorithm using Õ(1/(tγ2)) rounds, and only suffer a blow-up of exp(d · t2).Plugging in t = ω(1), this shows that the smaller blow-up in our lower bound is tight. More interestingly, this provides the first trade-off between the parallelism and the total work required for boosting.

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs fool width-3 programs, constant-width regular programs, and unbounded-width permutation programs with a single accepting vertex. In all three cases, the seed length is $\widetilde{O}(\log n \cdot \sqrt{\log (1 / \varepsilon)}+\log (1 / \varepsilon))$, where n is the length of the program and $\varepsilon$ is the error of the WPRG. For comparison, for all three of these models, the best explicit unweighted PRGs known have seed length $\widetilde{O}(\log n$. $\log (1 / \varepsilon)$) (Meka, Reingold, and Tal STOC 2019; Braverman, Rao, Raz, and Yehudayoff SICOMP 2014; Hoza, Pyne, and Vadhan ITCS 2021). Our WPRG seed length is superior when $\varepsilon$ is small. For the case of unbounded-width permutation programs, Pyne and Vadhan previously constructed a WPRG with a seed length that is similar to ours (CCC 2021), but their seed length has an extra additive $\log ^{3 / 2} n$ term, so our WPRG is superior when $\varepsilon \gg 1 / n$. Our results are based on a new, general framework for error reduction. Our framework builds on the remarkable recent work by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020) that gave a near-logarithmic space algorithm for estimating random walk probabilities in Eulerian digraphs with high precision. Our framework centers around the “inverse analysis” of random walks and a key combinatorial structure termed “shortcut graphs.” Using our new framework and the recent notion of singular value approximation (Ahmadinejad, Peebles, Pyne, Sidford, and Vadhan arXiv 2023), we also present an alternative, simpler proof of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan’s main theorem. Compared to the original proof, our new proof avoids much of the sophisticated machinery that was imported from recent work on fast Laplacian solvers.

In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS’16, JACM’19]. A line of work that followed extended this result to a large class of learning problems. Until recently, all these results considered learning in the streaming model, where each sample is drawn independently, and the learner is allowed a single pass over the stream of samples. Garg, Raz, and Tal [CCC’19] considered a stronger model, allowing multiple passes over the stream. In the 2-pass model, they showed that learning parities of size n requires either a memory of size $n^{1.5}$ or at least $2^{\sqrt{n}}$ samples. (Their result also generalizes to other learning problems.) In this work, for any constant q, we prove tight memory-sample lower bounds for any parity learning algorithm that makes q passes over the stream of samples. We show that such a learner requires either $\Omega\left(n^{2}\right)$ memory size or at least $2^{\Omega(n)}$ samples. Beyond establishing a tight lower bound, this is the first nontrivial lower bound for q-pass learning for any $q \geq 3$. Similar to prior work, our results extend to any learning problem with many nearly-orthogonal concepts.We complement the lower bound with an upper bound, showing that parity learning with q passes can be done efficiently with $O\left(n^{2} / \log q\right)$ memory.

Composition theorems are general and powerful tools that facilitate privacy accounting across multiple data accesses from per-access privacy bounds. However they often result in weaker bounds compared with end-to-end analysis. Two popular tools that mitigate that are the exponential mechanism (or report noisy max) and the sparse vector technique, generalized in a recent private selection framework by Liu and Talwar (STOC 2019). In this work, we propose a flexible framework of private selection and testing that generalizes the one proposed by Liu and Talwar, supporting a wide range of applications. We apply our framework to solve several fundamental tasks, including query releasing, top-k selection, and stable selection, with improved confidence-accuracy tradeoffs. Additionally, for online settings, we apply our private testing to design a mechanism for adaptive query releasing, which improves the sample complexity dependence on the confidence parameter for the celebrated private multiplicative weights algorithm of Hardt and Rothblum (FOCS 2010).

We propose the \emph{Target Charging Technique} (TCT), a unified privacy analysis framework for interactive settings where a sensitive dataset is accessed multiple times using differentially private algorithms. Unlike traditional composition, where privacy guarantees deteriorate quickly with the number of accesses, TCT allows computations that don't hit a specified \emph{target}, often the vast majority, to be essentially free (while incurring instead a small overhead on those that do hit their targets). TCT generalizes tools such as the sparse vector technique and top-k selection from private candidates and extends their remarkable privacy enhancement benefits from noisy Lipschitz functions to general private algorithms.

The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of O(ξ−1 log(1/β)) (for generalization error ξ with confidence 1−β). The private version of the problem, however, is more challenging and in particular, the sample complexity must depend on the size |X| of the domain. Progress on quantifying this dependence, via lower and upper bounds, was made in a line of works over the past decade. In this paper, we finally close the gap for approximate-DP and provide a nearly tight upper bound of O(log* |X|), which matches a lower bound by Alon et al (that applies even with improper learning) and improves over a prior upper bound of O((log* |X|)1.5) by Kaplan et al. We also provide matching upper and lower bounds of Θ(2log*|X|) for the additive error of private quasi-concave optimization (a related and more general problem). Our improvement is achieved via the novel Reorder-Slice-Compute paradigm for private data analysis which we believe will have further applications.

The last decade saw impressive progress towards understanding the performance of algorithms in adaptive settings, where subsequent inputs may depend on the output from prior inputs. Adaptive settings arise in processes with feedback or with adversarial attacks. Existing designs of robust algorithms are generic wrappers of non-robust counterparts and leave open the possibility of better tailored designs. The lowers bounds (attacks) are similarly worst-case and their significance to practical setting is unclear. Aiming to understand these questions, we study the robustness of \texttt{CountSketch}, a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering $\ell_2$-heavy hitters of a vector (entries with $v[i]^2 \geq \frac{1}{k}\|\boldsymbol{v}\|^2_2$). We show that the classic estimator is not robust, and can be attacked with a number of queries of the order of the sketch size. We propose a robust estimator (for a slightly modified sketch) that allows for quadratic number of queries in the sketch size, which is an improvement factor of $\sqrt{k}$ (for $k$ heavy hitters) over prior "blackbox" approaches.

We develop a general framework that characterizes strong average-case lower bounds against circuit classes 𝒞 contained in NC¹, such as AC⁰[⊕] and ACC⁰. We apply this framework to show: - Generic seed reduction: Pseudorandom generators (PRGs) against 𝒞 of seed length ≤ n -1 and error ε(n) = n^{-ω(1)} can be converted into PRGs of sub-polynomial seed length. - Hardness under natural distributions: If 𝖤 (deterministic exponential time) is average-case hard against 𝒞 under some distribution, then 𝖤 is average-case hard against 𝒞 under the uniform distribution. - Equivalence between worst-case and average-case hardness: Worst-case lower bounds against MAJ∘𝒞 for problems in 𝖤 are equivalent to strong average-case lower bounds against 𝒞. This can be seen as a certain converse to the Discriminator Lemma [Hajnal et al., JCSS'93]. These results were not known to hold for circuit classes that do not compute majority. Additionally, we prove that classical and recent approaches to worst-case lower bounds against ACC⁰ via communication lower bounds for NOF multi-party protocols [Håstad and Goldmann, CC'91; Razborov and Wigderson, IPL'93] and Torus polynomials degree lower bounds [Bhrushundi et al., ITCS'19] also imply strong average-case hardness against ACC⁰ under the uniform distribution. Crucial to these results is the use of non-black-box hardness amplification techniques and the interplay between Majority (MAJ) and Approximate Linear Sum (SUM̃) gates. Roughly speaking, while a MAJ gate outputs 1 when the sum of the m input bits is at least m/2, a SUM̃ gate computes a real-valued bounded weighted sum of the input bits and outputs 1 (resp. 0) if the sum is close to 1 (resp. close to 0), with the promise that one of the two cases always holds. As part of our framework, we explore ideas introduced in [Chen and Ren, STOC'20] to show that, for the purpose of proving lower bounds, a top layer MAJ gate is equivalent to a (weaker) SUM̃ gate. Motivated by this result, we extend the algorithmic method and establish stronger lower bounds against bounded-depth circuits with layers of MAJ and SUM̃ gates. Among them, we prove that: - Lower bound: NQP does not admit fixed quasi-polynomial size MAJ∘SUM̃∘ACC⁰∘THR circuits. This is the first explicit lower bound against circuits with distinct layers of MAJ, SUM̃, and THR gates. Consequently, if the aforementioned equivalence between MAJ and SUM̃ as a top gate can be extended to intermediate layers, long sought-after lower bounds against the class THR∘THR of depth-2 polynomial-size threshold circuits would follow.

In this work we prove that there is a function f ∈ E NP such that, for every sufficiently large n and d = √n/logn, fn (f restricted to n-bit inputs) cannot be (1/2 + 2−d)-approximated by F2-polynomials of degree d. We also observe that a minor improvement (e.g., improving d to n1/2+ε for any ε > 0) over our result would imply E NP cannot be computed by depth-3 AC0-circuits of 2n1/2 + ε size, which is a notoriously hard open question in complexity theory.

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether NEXP is contained in i.o.-NP; that is, it is open whether nondeterministic exponential time computation can be simulated on infinitely many input lengths by an NP algorithm. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. [Murray and Williams, STOC 2018] proved that nondeterminstic quasi-polynomial time is not contained in ACC^0, while it remained an open problem to show that E^NP (2^O(n) time with an NP oracle) is not contained in i.o.-ACC^0. In this paper, we show how many infinitely-often circuit lower bounds proved by the algorithmic method can be adapted to establish almost-everywhere lower bounds. First, we show there is a function f in E^NP such that, for all sufficiently large input lengths n, f cannot be (1/2+exp(-n∧e))-approximated by exp(n^e)-size ACC^0 circuits on inputs of length n (for all small e), improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020]. Second, we construct rigid matrices in P^NP for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al. 2020]. Third, we show there is a positive c such that E^NP has constant-error probabilistic degree at least cn/(log^2 n) for all large enough n, improving an infinitely-often separation by [Viola, ECCC 2020]. Our key to proving almost-everywhere worst-case lower bounds is a new “constructive” proof of an NTIME hierarchy theorem proved by [Fortnow and Santhanam, CCC 2016], where we show for every “weak” nondeterminstic algorithm, a “refuter algorithm” exists that can construct “bad” inputs for the hard language. We use this refuter algorithm to construct an almost-everywhere hard function. To extend our lower bounds to the average case, we prove a new XOR Lemma based on approximate linear sums, and combine it with PCP of proximity ideas developed in [Chen and Williams, CCC 2019] and [Chen and Ren, STOC 2020]. As a byproduct of our new XOR Lemma, we obtain a nondeterministic pseudorandom generator for poly-size ACC^0 circuits with seed length polylog(n), which resolves an open question in [Chen and Ren, STOC 2020].