Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads to randomized algorithms with no clear path to derandomization because the analyses rely on a union bound over exponentially many events. In this work, we revisit this goal of derandomizing randomized sampling in graphs. We give several results related to bounded-independence edge subsampling, and in the process of doing so, generalize several of the results of Alon and Nussboim (FOCS 2008), who studied bounded-independence analogues of random graphs (which can be viewed as edge subsamples of the complete graph). Most notably, we show: 1) O(log(m))-wise independence suffices for preserving connectivity when sampling at rate 1/2 in a graph with minimum cut ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 2) O(log(m))-wise (1/poly(m))-almost independence suffices for ensuring cycle-freeness when sampling at rate 1/2 in a graph with minimum cycle length ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 3) If we relax to arbitrary distributions, we show there is an explicit distribution with marginals ≤ 1/2 generated using O(log(m)log log(m)) random bits such that in a graph with minimum cut ≥ κ log(m) (for a sufficiently large constant κ), a sample from the distribution has is still connected with probability 1- 1/poly(m). To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms to find graphic matroid bases, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In this regime, we show that the optimal algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.

Whether or not the Sparsest Cut problem admits an efficient $O(1)$-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture. Revisiting spectral algorithms for Sparsest Cut, we present a novel, simple algorithm that combines eigenspace enumeration with a new algorithm for the Cut Improvement problem. The runtime of our algorithm is parametrized by a quantity that we call the solution dimension $\text{SD}_\varepsilon(G)$: the smallest $k$ such that the subspace spanned by the first $k$ Laplacian eigenvectors contains all but $\varepsilon$ fraction of a sparsest cut. Our algorithm matches the guarantees of prior methods based on the threshold-rank paradigm, while also extending beyond them. To illustrate this, we study its performance on low degree Cayley graphs over Abelian groups -- canonical examples of graphs with poor expansion properties. We prove that low degree Abelian Cayley graphs have small solution dimension, yielding an algorithm that computes a $(1+\varepsilon)$-approximation to the uniform Sparsest Cut of a degree-$d$ Cayley graph over an Abelian group of size $n$ in time $n^{O(1)}\cdot\exp(d/\varepsilon)^{O(d)}$. Along the way to bounding the solution dimension of Abelian Cayley graphs, we analyze their sparse cuts and spectra, proving that the collection of $O(1)$-approximate sparsest cuts has an $\varepsilon$-net of size $\exp(d/\varepsilon)^{O(d)}$ and that the multiplicity of $λ_2$ is bounded by $2^{O(d)}$. The latter bound is tight and improves on a previous bound of $2^{O(d^2)}$ by Lee and Makarychev.

Given a sequence of samples x_1, … , x_k promised to be drawn from one of two distributions X₀, X₁, a well-studied problem in statistics is to decide which distribution the samples are from. Information theoretically, the maximum advantage in distinguishing the two distributions given k samples is captured by the total variation distance between X₀^{⊗k} and X₁^{⊗k}. However, when we restrict our attention to efficient distinguishers (i.e., small circuits) of these two distributions, exactly characterizing the ability to distinguish X₀^{⊗k} and X₁^{⊗k} is more involved and less understood. In this work, we give a general way to reduce bounds on the computational indistinguishability of X₀ and X₁ to bounds on the information-theoretic indistinguishability of some specific, related variables X̃₀ and X̃₁. As a consequence, we prove a new, tight characterization of the number of samples k needed to efficiently distinguish X₀^{⊗k} and X₁^{⊗k} with constant advantage as k = Θ(d_H^{-2}(X̃₀, X̃₁)), which is the inverse of the squared Hellinger distance d_H between two distributions X̃₀ and X̃₁ that are computationally indistinguishable from X₀ and X₁. Likewise, our framework can be used to re-derive a result of Halevi and Rabin (TCC 2008) and Geier (TCC 2022), proving nearly-tight bounds on how computational indistinguishability scales with the number of samples for arbitrary product distributions. At the heart of our work is the use of the Multicalibration Theorem (Hébert-Johnson, Kim, Reingold, Rothblum 2018) in a way inspired by recent work of Casacuberta, Dwork, and Vadhan (STOC 2024). Multicalibration allows us to relate the computational indistinguishability of X₀, X₁ to the statistical indistinguishability of X̃₀, X̃₁ (for lower bounds on k) and construct explicit circuits to distinguish between X̃₀, X̃₁ and consequently X₀, X₁ (for upper bounds on k).

We initiate the study of the randomness complexity of differential privacy, i.e., how many random bits an algorithm needs in order to generate accurate differentially private releases. As a test case, we focus on the task of releasing the results of d counting queries, or equivalently all one-way marginals on a d-dimensional dataset with boolean attributes. While standard differentially private mechanisms for this task have randomness complexity that grows linearly with d, we show that, surprisingly, only log₂ d+O(1) random bits (in expectation) suffice to achieve an error that depends polynomially on d (and is independent of the size n of the dataset), and furthermore this is possible with pure, unbounded differential privacy and privacy-loss parameter ε = 1/poly(d). Conversely, we show that at least log₂ d-O(1) random bits are also necessary for nontrivial accuracy, even with approximate, bounded DP, provided the privacy-loss parameters satisfy ε,δ ≤ 1/poly(d). We obtain our results by establishing a close connection between the randomness complexity of differentially private mechanisms and the geometric notion of "deterministic rounding schemes" recently introduced and studied by Vander Woude et al. (2022, 2023).

In this paper, we study differentially private point and confidence interval estimators for simple linear regression. Motivated by recent work that highlights the strong empirical performance of an algorithm based on robust statistics, DPTheilSen, we provide a rigorous, finite-sample analysis of its privacy and accuracy properties, offer guidance on setting hyperparameters, and show how to produce differentially private confidence intervals to accompany its point estimates.

The standard definition of differential privacy (DP) ensures that a mechanism's output distribution on adjacent datasets is indistinguishable. However, real-world implementations of DP can, and often do, reveal information through their runtime distributions, making them susceptible to timing attacks.

We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors are correct in expectation on each member of an arbitrary collection of pre-specified sets. Multicalibrated predictors satisfy a stronger condition: they are calibrated on each set in the collection. Multiaccuracy is equivalent to a regularity notion for functions defined by Trevisan, Tulsiani, and Vadhan (2009). They showed that, given a class F of (possibly simple) functions, an arbitrarily complex function g can be approximated by a low-complexity function h that makes a small number of oracle calls to members of F, where the notion of approximation requires that h cannot be distinguished from g by members of F. This complexity-theoretic Regularity Lemma is known to have implications in different areas, including in complexity theory, additive number theory, information theory, graph theory, and cryptography. Starting from the stronger notion of multicalibration, we obtain stronger and more general versions of a number of applications of the Regularity Lemma, including the Hardcore Lemma, the Dense Model Theorem, and the equivalence of conditional pseudo-min-entropy and unpredictability. For example, we show that every boolean function (regardless of its hardness) has a small collection of disjoint hardcore sets, where the sizes of those hardcore sets are related to how balanced the function is on corresponding pieces of an efficient partition of the domain.

Abstract The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for space-bounded computation uses a seed of length $$O(\log n \cdot \log (nw/\varepsilon )+\log d)$$ O ( log n · log ( n w / ε ) + log d ) to fool ordered branching programs of length n, width w, and alphabet size d to within error $$\varepsilon $$ ε . A series of works have shown that the analysis of the INW generator can be improved for the class of permutation branching programs or the more general regular branching programs, improving the $$O(\log ^2 n)$$ O ( log 2 n ) dependence on the length n to $$O(\log n)$$ O ( log n ) or $${\tilde{O}}(\log n)$$ O ~ ( log n ) . However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length $$O(\log (nwd/\varepsilon ))$$ O ( log ( n w d / ε ) ) . In this paper, we prove that any “spectral analysis” of the INW generator requires seed length $$\begin{aligned} \Omega \left( \log n\cdot \log \log \left( \min \{n,d\}\right) +\log n\cdot \log \left( w/\varepsilon \right) +\log d\right) \end{aligned}$$ Ω log n · log log min { n , d } + log n · log w / ε + log d to fool ordered permutation branching programs of length n, width w, and alphabet size d to within error $$\varepsilon $$ ε . By “spectral analysis” we mean an analysis of the INW generator that relies only on the spectral expansion of the graphs used to construct the generator; this encompasses all prior analyses of the INW generator. Our lower bound matches the upper bound of Braverman–Rao–Raz–Yehudayoff (FOCS 2010, SICOMP 2014) for regular branching programs of alphabet size $$d=2$$ d = 2 except for a gap between their $$O\left( \log n \cdot \log \log n\right) $$ O log n · log log n term and our $$\Omega \left( \log n \cdot \log \log \min \{n,d\}\right) $$ Ω log n · log log min { n , d } term. It also matches the upper bounds of Koucký–Nimbhorkar–Pudlák (STOC 2011), De (CCC 2011), and Steinke (ECCC 2012) for constant-width ( $$w=O(1)$$ w = O ( 1 ) </

Differential privacy (DP) is a promising framework for privacy-preserving data science, but recent studies have exposed challenges in bringing this theoretical framework for privacy into practice. These tensions are particularly salient in the context of open-source software libraries for DP data analysis, which are emerging tools to help data stewards and analysts build privacy-preserving data pipelines for their applications. While there has been significant investment into such libraries, we need further inquiry into the role of these libraries in promoting understanding of and trust in DP, and in turn, the ways in which design of these open-source libraries can shed light on the challenges of creating trustworthy data infrastructures in practice. In this study, we use qualitative methods and mental models approaches to analyze the differences between conceptual models used to design open-source DP libraries and mental models of DP held by users. Through a two-stage study design involving formative interviews with 5 developers of open-source DP libraries and user studies with 17 data analysts, we find that DP libraries often struggle to bridge the gaps between developer and user mental models. In particular, we highlight the tension DP libraries face in maintaining rigorous DP implementations and facilitating user interaction. We conclude by offering practical recommendations for further development of DP libraries.

For Boolean functions computed by read-once, depth-$D$ circuits with unbounded fan-in over the de Morgan basis, we present an explicit pseudorandom generator with seed length $\tilde{O}(\log^{D+1} n)$. The previous best seed length known for this model was $\tilde{O}(\log^{D+4} n)$, obtained by Trevisan and Xue (CCC `13) for all of $AC^0$ (not just read-once). Our work makes use of Fourier analytic techniques for pseudorandomness introduced by Reingold, Steinke, and Vadhan (RANDOM `13) to show that the generator of Gopalan et al. (FOCS `12) fools read-once $AC^0$. To this end, we prove a new Fourier growth bound for read-once circuits, namely that for every $F: \{0,1\}^n\to\{0,1\}$ computed by a read-once, depth-$D$ circuit, \begin{equation*}\sum_{s\subseteq[n], |s|=k}|\hat{F}[s]|\le O(\log^{D-1}n)^k,\end{equation*} where $\hat{F}$ denotes the Fourier transform of $F$ over $\mathbb{Z}^n_2$.

In this paper, we study the concurrent composition of interactive mechanisms with adaptively chosen privacy-loss parameters. In this setting, the adversary can interleave queries to existing interactive mechanisms, as well as create new ones. We prove that every valid privacy filter and odometer for noninteractive mechanisms extends to the concurrent composition of interactive mechanisms if privacy loss is measured using (ε, δ)-DP, ƒ-DP, or Rényi DP of fixed order. Our results offer strong theoretical foundations for enabling full adaptivity in composing differentially private interactive mechanisms, showing that concurrency does not affect the privacy guarantees. We also provide an implementation for users to deploy in practice.

Across academia, government, and industry, data stewards are facing increasing pressure to make datasets more openly accessible for researchers while also protecting the privacy of data subjects. Differential privacy (DP) is one promising way to offer privacy along with open access, but further inquiry is needed into the tensions between DP and data science. In this study, we conduct interviews with 19 data practitioners who are non-experts in DP as they use a DP data analysis prototype to release privacy-preserving statistics about sensitive data, in order to understand perceptions, challenges, and opportunities around using DP. We find that while DP is promising for providing wider access to sensitive datasets, it also introduces challenges into every stage of the data science workflow. We identify ethics and governance questions that arise when socializing data scientists around new privacy constraints and offer suggestions to better integrate DP and data science.

In this paper, we introduce a new, spectral notion of approximation between directed graphs, which we call singular value (SV) approximation. SV-approximation is stronger than previous notions of spectral approximation considered in the literature, including spectral approximation of Laplacians for undirected graphs [ST04], standard approximation for directed graphs [CKP+17], and unit-circle (UC) approximation for directed graphs [AKM+20]. Further, SV approximation enjoys several useful properties not possessed by previous notions of approximation, e.g., it is preserved under products of randomwalk matrices and bounded matrices. We provide a nearly linear-time algorithm for SV-sparsifying (and hence UC-sparsifying) Eulerian directed graphs, as well as $\ell$-step random walks on such graphs, for any $\ell \leq \operatorname{poly}(n)$. Combined with the Eulerian scaling algorithms of [CKK+18], given an arbitrary (not necessarily Eulerian) directed graph and a set S of vertices, we can approximate the stationary probability mass of the $\left(S, S^{c}\right)$ cut in an $\ell$-step random walk to within a multiplicative error of $1 / \operatorname{polylog}(n)$ and an additive error of $1 / \operatorname{poly}(n)$ in nearly linear time. As a starting point for these results, we provide a simple black-box reduction from SV-sparsifying Eulerian directed graphs to SV-sparsifying undirected graphs; such a directed-to-undirected reduction was not known for previous notions of spectral approximation.

We study the concurrent composition properties of interactive differentially private mechanisms, whereby an adversary can arbitrarily interleave its queries to the different mechanisms. We prove that all composition theorems for non-interactive differentially private mechanisms extend to the concurrent composition of interactive differentially private mechanisms, whenever differential privacy is measured using the hypothesis testing framework of f-DP, which captures standard (,δ)-DP as a special case. We prove the concurrent composition theorem by showing that every interactive f-DP mechanism can be simulated by interactive post-processing of a non-interactive f-DP mechanism.

In this work, we design differentially private hypothesis tests for the following problems in the multivariate linear regression model: testing a linear relationship and testing for the presence of mixtures. The majority of our hypothesis tests are based on differentially private versions of the $F$-statistic for the multivariate linear regression model framework. We also present other differentially private tests---not based on the $F$-statistic---for these problems. We show that the differentially private $F$-statistic converges to the asymptotic distribution of its non-private counterpart. As a corollary, the statistical power of the differentially private $F$-statistic converges to the statistical power of the non-private $F$-statistic. Through a suite of Monte Carlo based experiments, we show that our tests achieve desired significance levels and have a high power that approaches the power of the non-private tests as we increase sample sizes or the privacy-loss parameter. We also show when our tests outperform existing methods in the literature.

We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper [Paul Beame and Sajin Koroth, 2023] introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that for any m ≥ 4 deterministic decision tree complexity of a function f can be lifted to the so called semi-structured communication complexity of f∘Ind_m, where Ind_m is the Indexing gadget. As our main contribution we extend these results to randomized setting. Our results also apply to a substantially larger set of gadgets. More specifically, we introduce a new complexity measure of gadgets, linear diversity. For all gadgets g with non-trivial linear diversity we show that randomized decision tree complexity of f lifts to randomized semi-structured communication complexity of f∘g. In particular, this gives tight lifting results for Indexing gadget Ind_m, Inner Product gadget IP_m for all m ≥ 2, and for Majority gadget MAJ_m for all m ≥ 4. We prove the same results for deterministic case. From our result it immediately follows that deterministic/randomized decision tree complexity lifts to deterministic/randomized parity decision tree complexity. For randomized case this is the first result of this type. For deterministic case, our result improves the bound in [Arkadev Chattopadhyay et al., 2023] for Inner Product gadget. To obtain our results we introduce a new secret sets approach to simulation of semi-structured communication protocols by decision trees. It allows us to simulate (restricted classes of) communication protocols on truly uniform distribution of inputs.

We identify a new class of vulnerabilities in implementations of differential privacy. Specifically, they arise when computing basic statistics such as sums, thanks to discrepancies between the implemented arithmetic using finite data types (namely, ints or floats) and idealized arithmetic over the reals or integers. These discrepancies cause the sensitivity of the implemented statistics (i.e., how much one individual's data can affect the result) to be much larger than the sensitivity we expect. Consequently, essentially all differential privacy libraries fail to introduce enough noise to hide individual-level information as required by differential privacy, and we show that this may be exploited in realistic attacks on differentially private query systems. In addition to presenting these vulnerabilities, we also provide a number of solutions, which modify or constrain the way in which the sum is implemented in order to recover the idealized or near-idealized bounds on sensitivity.

In this work, we design differentially private hypothesis tests for the following problems in the general linear model: testing a linear relationship and testing for the presence of mixtures. The majority of our hypothesis tests are based on differentially private versions of the $F$-statistic for the general linear model framework, which are uniformly most powerful unbiased in the non-private setting. We also present another test for testing mixtures, based on the differentially private nonparametric tests of Couch, Kazan, Shi, Bray, and Groce (CCS 2019), which is especially suited for the small dataset regime. We show that the differentially private $F$-statistic converges to the asymptotic distribution of its non-private counterpart. As a corollary, the statistical power of the differentially private $F$-statistic converges to the statistical power of the non-private $F$-statistic. Through a suite of Monte Carlo based experiments, we show that our tests achieve desired \textit{significance levels} and have a high \textit{power} that approaches the power of the non-private tests as we increase sample sizes or the privacy-loss parameter. We also show when our tests outperform existing methods in the literature.

Abstract Economics and social science research often require analyzing datasets of sensitive personal information at fine granularity, with models fit to small subsets of the data. Unfortunately, such fine-grained analysis can easily reveal sensitive individual information. We study regression algorithms that satisfy differential privacy, a constraint which guarantees that an algorithm’s output reveals little about any individual input data record, even to an attacker with side information about the dataset. Motivated by the Opportunity Atlas, a high-profile, small-area analysis tool in economics research, we perform a thorough experimental evaluation of differentially private algorithms for simple linear regression on small datasets with tens to hundreds of records—a particularly challenging regime for differential privacy. In contrast, prior work on differentially private linear regression focused on multivariate linear regression on large datasets or asymptotic analysis. Through a range of experiments, we identify key factors that affect the relative performance of the algorithms. We find that algorithms based on robust estimators—in particular, the median-based estimator of Theil and Sen—perform best on small datasets (e.g., hundreds of datapoints), while algorithms based on Ordinary Least Squares or Gradient Descent perform better for large datasets. However, we also discuss regimes in which this general finding does not hold. Notably, the differentially private analogues of Theil–Sen (one of which was suggested in a theoretical work of Dwork and Lei) have not been studied in any prior experimental work on differentially private linear regression.

Motivated by the derandomization of space-bounded computation, there has been a long line of work on constructing pseudorandom generators (PRGs) against various forms of read-once branching programs (ROBPs), with a goal of improving the O(log² n) seed length of Nisan’s classic construction [Noam Nisan, 1992] to the optimal O(log n). In this work, we construct an explicit PRG with seed length Õ(log n) for constant-width ROBPs that are monotone, meaning that the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state. This result is complementary to a line of work that gave PRGs with seed length O(log n) for (ordered) permutation ROBPs of constant width [Braverman et al., 2014; Koucký et al., 2011; De, 2011; Thomas Steinke, 2012], since the monotonicity constraint can be seen as the "opposite" of the permutation constraint. Our PRG also works for monotone ROBPs that can read the input bits in any order, which are strictly more powerful than read-once AC⁰. Our PRG achieves better parameters (in terms of the dependence on the depth of the circuit) than the best previous pseudorandom generator for read-once AC⁰, due to Doron, Hatami, and Hoza [Doron et al., 2019]. Our pseudorandom generator construction follows Ajtai and Wigderson’s approach of iterated pseudorandom restrictions [Ajtai and Wigderson, 1989; Gopalan et al., 2012]. We give a randomness-efficient width-reduction process which proves that the branching program simplifies to an O(log n)-junta after only O(log log n) independent applications of the Forbes-Kelley pseudorandom restrictions [Michael A. Forbes and Zander Kelley, 2018].

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a weighted pseudorandom generator (WPRG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of WPRGs for ordered branching programs whose seed length has a better dependence on the error parameter ε than the classic PRG construction of Nisan (STOC 1990 and Combinatorica 1992). In this work, we give an explicit construction of WPRGs that achieve parameters that are impossible to achieve by a PRG. In particular, we construct a WPRG for ordered permutation branching programs of unbounded width with a single accept state that has seed length Õ(log^{3/2} n) for error parameter ε = 1/poly(n), where n is the input length. In contrast, recent work of Hoza et al. (ITCS 2021) shows that any PRG for this model requires seed length Ω(log² n) to achieve error ε = 1/poly(n). As a corollary, we obtain explicit WPRGs with seed length Õ(log^{3/2} n) and error ε = 1/poly(n) for ordered permutation branching programs of width w = poly(n) with an arbitrary number of accept states. Previously, seed length o(log² n) was only known when both the width and the reciprocal of the error are subpolynomial, i.e. w = n^{o(1)} and ε = 1/n^{o(1)} (Braverman, Rao, Raz, Yehudayoff, FOCS 2010 and SICOMP 2014). The starting point for our results are the recent space-efficient algorithms for estimating random-walk probabilities in directed graphs by Ahmadenijad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), which are based on spectral graph theory and space-efficient Laplacian solvers. We interpret these algorithms as giving WPRGs with large seed length, which we then derandomize to obtain our results. We also note that this approach gives a simpler proof of the original result of Braverman, Cohen, and Garg, as independently discovered by Cohen, Doron, Renard, Sberlo, and Ta-Shma (these proceedings).

We prove that the Impagliazzo-Nisan-Wigderson [Impagliazzo et al., 1994] pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of Õ(log d + log n ⋅ log(1/ε)), assuming the program has only one accepting vertex in the final layer. Here, n is the length of the program, d is the degree (equivalently, the alphabet size), and ε is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length Ω(n log d) to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is "better than random." Except when the program’s width w is very small, this is an improvement over prior work. For example, when w = poly(n) and d = 2, the best prior PRG for permutation branching programs was simply Nisan’s PRG [Nisan, 1992], which fools general ordered branching programs with seed length O(log(wn/ε) log n). We prove a seed length lower bound of Ω̃(log d + log n ⋅ log(1/ε)) for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when ε ≤ 1/log n, our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan [Rozenman and Vadhan, 2005] and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. [Ahmadinejad et al., 2020].

We give a deterministic $O(\log n\cdot\log\log n)$-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs. Previously, such systems were known to be solvable by randomized algorithms using $O(\log n)$ space [D. Doron, F. Le Gall, and A. Ta-Shma, Probabilistic logarithmic-space algorithms for Laplacian solvers, in APPROX/RANDOM 2017, LIPIcs. Leibniz Int. Proc. Inform. 81, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2017, 41] and hence by deterministic algorithms using $O(\log^{3/2} n)$ space [M. Saks and S. Zhou, J. Comput. System Sci., 58 (1999), pp. 376--403]. Our algorithm combines ideas from time-efficient Laplacian solvers [D. A. Spielman and S.-H. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, in STOC 2004, ACM, New York, 2004, pp. 81--90; R. Peng and D. A. Spielman, An efficient parallel solver for SDD linear systems, in STOC 2014, ACM, New York, 2014, pp. 333--342] with ideas used to show that Undirected S-T Connectivity is in deterministic logspace [O. Reingold, J. ACM, 55 (2008); E. Rozenman and S. Vadhan, Derandomized squaring of graphs, in RANDOM 2005, Lecture Notes in Comput. Sci. 3624, Springer, Berlin, 2005, pp. 436--447].

In this paper, we provide a deterministic ~O(log N)-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error (ε = 1/poly(N)) where N is the length of the input. Previously, this problem was known to be solvable by a randomized algorithm using space O(log N) (following Aleliunas et al., FOCS '79) and by a deterministic algorithm using space O(log3/2N) (Saks and Zhou, FOCS '95 and JCSS '99), both of which held for arbitrary directed graphs but had not been improved even for undirected graphs. We also give improvements on the space complexity of both of these previous algorithms for non-Eulerian directed graphs when the error is negligible (ε = 1/Nω(1)), generalizing what Hoza and Zuckerman (FOCS '18) recently showed for the special case of distinguishing whether a random walk probability is 0 or greater than ε. We achieve these results by giving new reductions between powering Eulerian random-walk matrices and inverting Eulerian Laplacian matrices, providing a new notion of spectral approximation for Eulerian graphs that is preserved under powering, and giving the first deterministic ~O(log N)-space algorithm for inverting Eulerian Laplacian matrices. The latter algorithm builds on the work of Murtagh et al. (FOCS '17) that gave a deterministic ~O(log N)-space algorithm for inverting undirected Laplacian matrices, and the work of Cohen et al. (FOCS '19) that gave a randomized ~O(N)-time algorithm for inverting Eulerian Laplacian matrices. A running theme throughout these contributions is an analysis of “cycle-lifted graphs,” where we take a graph and “lift” it to a new graph whose adjacency matrix is the tensor product of the original adjacency matrix and a directed cycle (or variants of one).

We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph G, a positive integer r, and a set S of vertices, approximates the conductance of S in the r-step random walk on G to within a factor of 1+epsilon, where epsilon>0 is an arbitrarily small constant. More generally, our algorithm computes an epsilon-spectral approximation to the normalized Laplacian of the r-step walk. Our algorithm combines the derandomized square graph operation [Eyal Rozenman and Salil Vadhan, 2005], which we recently used for solving Laplacian systems in nearly logarithmic space [Murtagh et al., 2017], with ideas from [Cheng et al., 2015], which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even r (while ours works for all r). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd r. Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.

We study entropy flattening: Given a circuit C_X implicitly describing an n-bit source X (namely, X is the output of C_X on a uniform random input), construct another circuit C_Y describing a source Y such that (1) source Y is nearly flat (uniform on its support), and (2) the Shannon entropy of Y is monotonically related to that of X. The standard solution is to have C_Y evaluate C_X altogether Theta(n^2) times on independent inputs and concatenate the results (correctness follows from the asymptotic equipartition property). In this paper, we show that this is optimal among black-box constructions: Any circuit C_Y for entropy flattening that repeatedly queries C_X as an oracle requires Omega(n^2) queries. Entropy flattening is a component used in the constructions of pseudorandom generators and other cryptographic primitives from one-way functions [Johan Håstad et al., 1999; John Rompel, 1990; Thomas Holenstein, 2006; Iftach Haitner et al., 2006; Iftach Haitner et al., 2009; Iftach Haitner et al., 2013; Iftach Haitner et al., 2010; Salil P. Vadhan and Colin Jia Zheng, 2012]. It is also used in reductions between problems complete for statistical zero-knowledge [Tatsuaki Okamoto, 2000; Amit Sahai and Salil P. Vadhan, 1997; Oded Goldreich et al., 1999; Vadhan, 1999]. The Theta(n^2) query complexity is often the main efficiency bottleneck. Our lower bound can be viewed as a step towards proving that the current best construction of pseudorandom generator from arbitrary one-way functions by Vadhan and Zheng (STOC 2012) has optimal efficiency.

We study the problem of estimating finite sample confidence intervals of the mean of a normal population under the constraint of differential privacy. We consider both the known and unknown variance cases and construct differentially private algorithms to estimate confidence intervals. Crucially, our algorithms guarantee a finite sample coverage, as opposed to an asymptotic coverage. Unlike most previous differentially private algorithms, we do not require the domain of the samples to be bounded. We also prove lower bounds on the expected size of any differentially private confidence set showing that our the parameters are optimal up to polylogarithmic factors.

We show new information-theoretic lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database $D \in (\{0,1\}^d)^n$ has the form “What fraction of the individual records in the database satisfy the property $q$?” We show that in order to answer an arbitrary set $\mathcal{Q}$ of $\gg d/\alpha^2$ counting queries on $D$ to within error $\pm \alpha$ it is necessary that $ n \geq \tilde{\Omega}({\sqrt{d} \log |\mathcal{Q}|}/{\alpha^2 \varepsilon}). $ This bound is optimal up to polylogarithmic factors, as demonstrated by the private multiplicative weights algorithm (Hardt and Rothblum, FOCS'10). In particular, our lower bound is the first to show that the sample complexity required for accuracy and $(\varepsilon, \delta)$-differential privacy is asymptotically larger than what is required merely for accuracy, which is $O(\log |\mathcal{Q}| / \alpha^2)$. In addition, we show that our lower bound holds for the specific case of $k$-way marginal queries (where $|\mathcal{Q}| = 2^k \binom{d}{k}$) when $\alpha$ is not too small compared to $d$ (e.g., when $\alpha$ is any fixed constant). Our results rely on the existence of short fingerprinting codes (Boneh and Shaw, CRYPTO'95; Tardos, STOC'03), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample-complexity lower bounds into stronger lower bounds.

Building on the work of Daniely et al. (STOC 2014, COLT 2016), we study the connection between computationally efficient PAC learning and refutation of constraint satisfaction problems. Specifically, we prove that for every concept class $\mathcal{P}$, PAC-learning $\mathcal{P}$ is \em polynomially equivalent to “random-right-hand-side-refuting” (“RRHS-refuting”) a dual class $\mathcal{P}^*$, where RRHS-refutation of a class $\mathcal{Q}$ refers to refuting systems of equations where the constraints are (worst-case) functions from the class $\mathcal{Q}$ but the right-hand-sides of the equations are uniform and independent random bits. The reduction from refutation to PAC learning can be viewed as an abstraction of (part of) the work of Daniely, Linial, and Shalev-Schwartz (STOC 2014). The converse, however, is new, and is based on a combination of techniques from pseudorandomness (Yao ‘82) with boosting (Schapire ‘90). In addition, we show that PAC-learning the class of $\mathit{DNF}$ formulas is polynomially equivalent to PAC-learning its dual class $\mathit{DNF}^*$, and thus PAC-learning $\mathit{DNF}$ is equivalent to RRHS-refutation of $\mathit{DNF}$, suggesting an avenue to obtain stronger lower bounds for PAC-learning $\mathit{DNF}$ than the quasipolynomial lower bound that was obtained by Daniely and Shalev-Schwartz (COLT 2016) assuming the hardness of refuting $k$-SAT.

We give a deterministic Õ(log n)-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs. Previously, such systems were known to be solvable by randomized algorithms using O(log n) space (Doron, Le Gall, and Ta-Shma, 2017) and hence by deterministic algorithms using O(log3/2n) space (Saks and Zhou, FOCS 1995 and JCSS 1999). Our algorithm combines ideas from time-efficient Laplacian solvers (Spielman and Teng, STOC `04; Peng and Spielman, STOC `14) with ideas used to show that UNDIRECTED S-T CONNECTIVITY is in deterministic logspace (Reingold, STOC `05 and JACM `08; Rozenman and Vadhan, RANDOM `05).

Hypothesis testing is a useful statistical tool in determining whether a given model should be rejected based on a sample from the population. Sample data may contain sensitive information about individuals, such as medical information. Thus it is important to design statistical tests that guarantee the privacy of subjects in the data. In this work, we study hypothesis testing subject to differential privacy, specifically chi-squared tests for goodness of fit for multinomial data and independence between two categorical variables.

In this paper we initiate the study of adaptive composition in differential privacy when the length of the composition, and the privacy parameters themselves can be chosen adaptively, as a function of the outcome of previously run analyses. This case is much more delicate than the setting covered by existing composition theorems, in which the algorithms themselves can be chosen adaptively, but the privacy parameters must be fixed up front. Indeed, it isn't even clear how to define differential privacy in the adaptive parameter setting. We proceed by defining two objects which cover the two main use cases of composition theorems. A privacy filter is a stopping time rule that allows an analyst to halt a computation before his pre-specified privacy budget is exceeded. A privacy odometer allows the analyst to track realized privacy loss as he goes, without needing to pre-specify a privacy budget. We show that unlike the case in which privacy parameters are fixed, in the adaptive parameter setting, these two use cases are distinct. We show that there exist privacy filters with bounds comparable (up to constants) with existing privacy composition theorems. We also give a privacy odometer that nearly matches non-adaptive private composition theorems, but is sometimes worse by a small asymptotic factor. Moreover, we show that this is inherent, and that any valid privacy odometer in the adaptive parameter setting must lose this factor, which shows a formal separation between the filter and odometer use-cases.

We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private data exploration, clustering, and removal of outliers. Furthermore, we use it to significantly relax the requirements of the sample and aggregate technique [Nissim, Raskhodnikova, and Smith, 2007], which allows compiling of "off the shelf" (non-private) analyses into analyses that preserve differential privacy.

We prove new upper and lower bounds on the sample complexity of (ε, δ) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function c over a totally ordered domain X evaluates to cz(y) = 1 if y ≤ x, and evaluates to 0 otherwise. We give the first nontrivial lower bound for releasing thresholds with (ε, δ) differential privacy, showing that the task is impossible over an infinite domain X, and moreover requires sample complexity n ≥ Ω(log* |X|), which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with n ≤ 2(1+ο(1)) log*|X| samples. This improves the previous best upper bound of 8(1+ο(1)) log*|X| (Beimel et al., RANDOM '13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with (ε, δ) differential privacy and learning without privacy. For properly learning thresholds in ℓ dimensions, this lower bound extends to n ≥ Ω(ℓ · log* |X|). To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database D of elements from X, the interior point problem asks for an element between the smallest and largest elements in D. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.

The privacy risks inherent in the release of a large number of summary statistics were illustrated by Homer et al. (PLoS Genetics, 2008), who considered the case of 1-way marginals of SNP allele frequencies obtained in a genome-wide association study: Given a large number of minor allele frequencies from a case group of individuals diagnosed with a particular disease, together with the genomic data of a single target individual and statistics from a sizable reference dataset independently drawn from the same population, an attacker can determine with high confidence whether or not the target is in the case group. In this work we describe and analyze a simple attack that succeeds even if the summary statistics are significantly distorted, whether due to measurement error or noise intentionally introduced to protect privacy. Our attack only requires that the vector of distorted summary statistics is close to the vector of true marginals in ℓ1norm. Moreover, the reference pool required by previous attacks can be replaced by a single sample drawn from the underlying population. The new attack, which is not specific to genomics and which handles Gaussian as well as Bernouilli data, significantly generalizes recent lower bounds on the noise needed to ensure differential privacy (Bun, Ullman, and Vadhan, STOC 2014, Steinke and Ullman, 2015), obviating the need for the attacker to control the exact distribution of the data.

We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ). The previously best known seed length for this model is n^{1/2+o(1)} due to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM'13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f : {0,1}^n -> {0,1} computed by such a branching program, and k in [n], sum_{|s|=k} |hat{f}(s)| < n^2 * (O(\log n))^k, where f(x) = sum_s hat{f}(s) (-1)^ is the standard Fourier transform over Z_2^n. The base O(log n) of the Fourier growth is tight up to a factor of log log n.

We give two new characterizations of ( 2-linear, smooth) locally testable error-correcting codes in terms of Cayley graphs over Fh2:

We prove new positive and negative results concerning the existence of truthful and individually rational mechanisms for purchasing private data from individuals with unbounded and sensitive privacy preferences. We strengthen the impossibility results of Ghosh and Roth (EC 2011) by extending it to a much wider class of privacy valuations. In particular, these include privacy valuations that are based on (ε δ)-differentially private mechanisms for non-zero δ, ones where the privacy costs are measured in a per-database manner (rather than taking the worst case), and ones that do not depend on the payments made to players (which might not be observable to an adversary).

We show new lower bounds on the sample complexity of (ε, δ)-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database D ∈ ({0, 1}d)n has the form "What fraction of the individual records in the database satisfy the property q?" We show that in order to answer an arbitrary set Q of » nd counting queries on D to within error ±α it is necessary that

We construct a publicly verifiable protocol for proving computational work based on collision-resistant hash functions and a new plausible complexity assumption regarding the existence of "inherently sequential" hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled "puzzle" P getsr Dn, where $n$ is the security parameter and Dn is the distribution of the puzzles, a corresponding "solution" can be generated using N evaluations of the sequential hash function, where N>n is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as Ω(N) serial evaluations of the hash function after receiving $P$. Thus, valid solutions constitute a "proof" that Ω(N) parallel time elapsed since p was received. Solutions can be publicly and efficiently verified in time poly(n) ⋅ polylog(N). Applications of these "time-lock puzzles" include noninteractive timestamping of documents (where the distribution over the possible documents corresponds to the puzzle distribution Dn) and universally verifiable CPU benchmarks. Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic.

Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately from the truthfulness; it is not incorporated in players' utility functions (and doing so has been shown to lead to non-truthfulness in some cases). In this work, we propose a new, general way of modelling privacy in players' utility functions. Specifically, we only assume that if an outcome o has the property that any report of player i would have led to o with approximately the same probability, then o has small privacy cost to player i. We give three mechanisms that are truthful with respect to our modelling of privacy: for an election between two candidates, for a discrete version of the facility location problem, and for a general social choice problem with discrete utilities (via a VCG-like mechanism). As the number n of players increases, the social welfare achieved by our mechanisms approaches optimal (as a fraction of n).

We study interactive proofs with sublinear-time verifiers. These proof systems can be used to ensure approximate correctness for the results of computations delegated to an untrusted server. Following the literature on property testing, we seek proof systems where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear. We call such a proof system an Interactive Proof of Proximity (IPP). On the positive side, our main result is that all languages in NC have Interactive Proofs of Proximity with roughly √n query and communication and complexities, and polylog(n) communication rounds. This is achieved by identifying a natural language, membership in an affine subspace (for a structured class of subspaces), that is complete for constructing interactive proofs of proximity, and providing efficient protocols for it. In building an IPP for this complete language, we show a tradeoff between the query and communication complexity and the number of rounds. For example, we give a 2-round protocol with roughly n3/4 queries and communication. On the negative side, we show that there exist natural languages in NC1, for which the sum of queries and communication in any constant-round interactive proof of proximity must be polynomially related to n. In particular, for any 2-round protocol, the sum of queries and communication must be at least ~Ω(√n). Finally, we construct much better IPPs for specific functions, such as bipartiteness on random or well-mixing graphs, and the majority function. The query complexities of these protocols are provably better (by exponential or polynomial factors) than what is possible in the standard property testing model, i.e. without a prover.

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of H\aastad, Impagliazzo, Levin, and Luby [SIAM J. Comput., 28 (1999), pp. 1364--1396]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired by the notion of “inaccessible entropy” recently introduced in [I. Haitner, O. Reingold, S. Vadhan, and H. Wee, Proceedings of the $41$st Annual ACM Symposium on Theory of Computing (STOC), 2009, pp. 611--620]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a nonadaptive manner. Using [B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845--888], this implies the existence of pseudorandom generators in NC$^0$ based on the existence of one-way functions in NC$^1$.

We initiate the study of "privacy for the analyst" in differentially private data analysis. That is, not only will we be concerned with ensuring differential privacy for the data (i.e. individuals or customers), which are the usual concern of differential privacy, but we also consider (differential) privacy for the set of queries posed by each data analyst. The goal is to achieve privacy with respect to other analysts, or users of the system. This problem arises only in the context of stateful privacy mechanisms, in which the responses to queries depend on other queries posed (a recent wave of results in the area utilized cleverly coordinated noise and state in order to allow answering privately hugely many queries). We argue that the problem is real by proving an exponential gap between the number of queries that can be answered (with non-trivial error) by stateless and stateful differentially private mechanisms. We then give a stateful algorithm for differentially private data analysis that also ensures differential privacy for the analyst and can answer exponentially many queries.

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near-optimal seed-length even in the low-error regime: We get seed-length Õ(log (n/ε)) for error ε. Previously, only constructions with seed-length O(log3/2n) or O(log2n) were known for these classes with error ε = 1/poly(n). The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using small-bias spaces.

We provide a characterization of “pseudoentropy” in terms of hardness of sampling: Let (X, B) be jointly distributed random variables such that B takes values in a polynomial-sized set. We show that no polynomial-time algorithm can distinguish B from some random variable of higher Shannon entropy given X if and only if there is no probabilistic polynomial-time S such that (X, S(X)) has small KL divergence from (X, B). As an application of this characterization, we show that if f is a one-way function (f is easy to compute but hard to invert), then (f(Un),Un) has “next-bit pseudoentropy” at least n + log n, establishing a conjecture of Haitner, Reingold, and Vadhan (STOC '10). Plugging this into the construction of Haitner et al., we obtain a simpler construction of pseudorandom generators from one-way functions.

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let (X,B) be jointly distributed random variables such that B takes values in a polynomial-sized set. We show that B is computationally indistinguishable from a random variable of higher Shannon entropy given X if and only if there is no probabilistic polynomial-time S such that (X,S(X)) has small KL divergence from (X,B). This can be viewed as an analogue of the Impagliazzo Hardcore Theorem (FOCS '95) for Shannon entropy (rather than min-entropy).

Abstract. Informally, an obfuscator O is an (ecient, probabilistic) \\compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is \\unintel-ligible " in some sense. Obfuscators, if they exist, would have a wide vari-ety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice’s theorem. Most of these applications are based on an interpretation of the \\unintelligibility " condition in obfuscation as mean-ing that O(P) is a \\virtual black box, " in the sense that anything one can eciently compute given O(P), one could also eciently compute given oracle access to P. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above in-tuition, obfuscation is impossible. We prove this by constructing a family of functions F that are inherently unobfuscatable in the following sense:

This section of SIAM Journal on Computing contains extended versions of selected papers from the 43rd ACM Symposium on Theory of Computing (STOC), held June 6--8, 2011, in San Jose, California, as part of the fifth Federated Computing Research Conference (FCRC). The STOC proceedings contained 84 papers, which were selected from 304 submissions by the program committee, consisting of Ittai Abraham, Alexandr Andoni, Avrim Blum, Allan Borodin, Kousha Etessami, Lisa Fleischer, Venkatesan Guruswami, David Kempe, Frederic Magniez, Dieter van Melkebeek, Daniele Micciancio, Moni Naor, Kobbi Nissim, Seth Pettie, Ronitt Rubinfeld, Amir Shpilka, Ravi Sundaram, Eva Tardos, Prasad Tetali, Salil Vadhan (chair), Kasturi Varadarajan, Nisheeth Vishnoi, John Watrous, and Ryan Williams. Five of the STOC papers appear in this special section, each one expanded and fully refereed according to the high standards of the journal. They cover a diverse collection of topics: In “Distributed Verification and Hardness of Distributed Approximation,” Das Sarma, Holzer, Kor, Korman, Nanongkai, Pandurangan, Peleg, and Wattenhofer prove strong lower bounds on the power of distributed networks to verify their own properties (such as connectivity) and solve optimization problems such as computing approximate shortest paths or approximate min-cuts. They establish new connections between distributed computation and two-party communication complexity. The paper “Pareto Optimal Solutions for Smoothed Analysts” by Moitra and O'Donnell considers the smoothed complexity of discrete multi-objective optimization problems with $d+1$ linear objectives and with a solution space consisting of binary $n$-vectors. The authors show that, in a suitable smoothed analysis framework for such problems, the expected number of Pareto optimal solutions is at most $n^{2d}$. This improves greatly, as a function of the dimension d, an earlier upper bound established by Roeglin and Teng, which had roughly the form $n^{d^d}$. The paper “Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter” by Saxena and Seshadhri provides the first deterministic polynomial-time identity test for depth-3 arithmetic circuits with bounded top-fanin that only needs blackbox access to the circuit. Their construction has the feature that it works for arbitrary fields. In their paper “An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance,” Chakrabarti and Regev prove a lower bound establishing that the randomized communication complexity of the gap-Hamming-distance problem is linear. In obtaining this result, they have resolved an important and well-studied communication complexity problem having a fundamental connection to the data stream model of computation. Svensson's paper “Santa Claus Schedules Jobs on Unrelated Machines” breaks the barrier of 2 for efficiently approximating the minimum makespan for scheduling jobs on unrelated machines in the setting where all machines on which a given job can run take the same amount of time for that job. We thank the authors, the referees, and the full program committee for all their work, which made this special section possible.

We present a deterministic logspace algorithm for solving S-T Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices s and t have nonnegligible probability mass and (ii) the random walk which starts at the source vertex s has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T Connectivity on undirected graphs [Reingold, 2008]. It identifies knowledge of the stationary distribution as the gap between the S-T Connectivity problems we know how to solve in logspace ( L ) and those that capture all of randomized logspace ( RL ).

Boosting is a general method for improving the accuracy of learning algorithms. We use boosting to construct improved privacy-pre serving synopses of an input database. These are data structures that yield, for a given set Q of queries over an input database, reasonably accurate estimates of the responses to every query in Q, even when the number of queries is much larger than the number of rows in the database. Given a base synopsis generator that takes a distribution on Q and produces a "weak" synopsis that yields "good" answers for a majority of the weight in Q, our Boosting for Queries algorithm obtains a synopsis that is good for all of Q. We ensure privacy for the rows of the database, but the boosting is performed on the queries. We also provide the first synopsis generators for arbitrary sets of arbitrary low-sensitivity queries, i.e., queries whose answers do not vary much under the addition or deletion of a single row. In the execution of our algorithm certain tasks, each incurring some privacy loss, are performed many times. To analyze the cumulative privacy loss, we obtain an O(ε2) bound on the expected privacy loss from a single e-differentially private mechanism. Combining this with evolution of confidence arguments from the literature, we get stronger bounds on the expected cumulative privacy loss due to multiple mechanisms, each of which provides e-differential privacy or one of its relaxations, and each of which operates on (potentially) different, adaptively chosen, databases.

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and in general. Our bounds expose a sharp contrast between the two-party setting and the simpler client-server setting (where privacy guarantees are one-sided). In addition, those bounds demonstrate a dramatic gap between the accuracy that can be obtained by differentially private data analysis versus the accuracy obtainable when privacy is relaxed to a computational variant of differential privacy. The first proof technique we develop demonstrates a connection between differential privacy and deterministic extraction from Santha-Vazirani sources. A second connection we expose indicates that the ability to approximate a function by a low-error differentially private protocol is strongly related to the ability to approximate it by a low communication protocol. (The connection goes in both directions).

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Hastad, Impagliazzo, Levin, and Luby [SICOMP '99]. The key to our construction is a new notion of "next-block pseudoentropy", which is inspired by the notion of "inaccessible entropy" recently introduced in [Haitner, Reingold, Vadhan, Wee, STOC '09]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a non-adaptive manner. Using [Applebaum, Ishai, Kushilevitz, SICOMP '06], this implies the existence of pseudorandom generators in NC^0 based on the existence of one-way functions in NC^1.

Aq-ary error-correcting codeC⊆ {1,2,...,q}nis said to be list decodable to radius ρ with list sizeLif every Hamming ball of radius ρ contains at mostLcodewords ofC. We prove that in order for aq-ary code to be list-decodable up to radius (1-1/q)(1- ε)n, we must haveL= Ω(1/ ε2) . Specifically, we prove that there exists a constantcq> 0 and a functionfqsuch that for small enough ε > 0, ifCis list-decodable to radius (1-1/q)(1- ε)nwith list sizecq/ ε2, thenChas at mostfq( ε) codewords, independent ofn. This result is asymptotically tight (treatingqas a constant), since such codes with an exponential (inn) number of codewords are known for list sizeL=O(1/ ε2). A result similar to ours is implicit in Blinovsky ( Problems of Information Transmission, 1986) for the binary (q=2) case. Our proof is simpler and works for all alphabet sizes, and provides more intuition for why the lower bound arises.

Starting with Kilian (STOC '92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs are inherent in efficient arguments, and to what extent. We give evidence that they are, by showing how to convert any argument system whose soundness is reducible to the security of some cryptographic primitive into a PCP system whose efficiency is related to that of the argument system and the reduction (under certain complexity assumptions).

We show that every bounded function g: {0,1}nrarr [0,1] admits an efficiently computable "simulator" function h: {0,1}nrarr [0,1] such that every fixed polynomial size circuit has approximately the same correlation with g as with h. If g describes (up to scaling) a high min-entropy distribution D, then h can be used to efficiently sample a distribution D' of the same min-entropy that is indistinguishable from D by circuits of fixed polynomial size. We state and prove our result in a more abstract setting, in which we allow arbitrary finite domains instead of {0,1}n, and arbitrary families of distinguishers, instead of fixed polynomial size circuits. Our result implies (a) the weak Szemeredi regularity Lemma of Frieze and Kannan (b) a constructive version of the dense model theorem of Green, Tao and Ziegler with better quantitative parameters (polynomial rather than exponential in the distinguishing probability), and (c) the Impagliazzo hardcore set Lemma. It appears to be the general result underlying the known connections between "regularity" results in graph theory, "decomposition" results in additive combinatorics, and the hardcore Lemma in complexity theory. We present two proofs of our result, one in the spirit of Nisan's proof of the hardcore Lemma via duality of linear programming, and one similar to Impagliazzo's "boosting" proof. A third proof by iterative partitioning, which gives the complexity of the sampler to be exponential in the distinguishing probability, is also implicit in the Green-Tao-Ziegler proofs of the dense model theorem.

We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. The sanitization may be in the form of an arbitrary data structure, accompanied by a computational procedure for determining approximate answers to queries on the original data set, or it may be a "synthetic data set" consisting of data items drawn from the same universe as items in the original data set; queries are carried out as if the synthetic data set were the actual input. In either case the process is non-interactive; once the sanitization has been released the original data and the curator play no further role.

We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the i'th round of a protocol (A,B) has *accessible entropy* at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the i'th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. We say that the protocol has *inaccessible entropy* if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of A's messages, conditioned only on prior messages (but not the coin tosses of A). As applications of this notion, we -- Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions. -- Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma et al. [2007] required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy [2005]. Our expanders can be interpreted as near-optimal “randomness condensers,” that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new, self-contained construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. [2003] and improving upon it when the error parameter is small (e.g., 1/poly(n)).

We give a construction of statistically hiding commitment schemes (those in which the hiding property holds against even computationally unbounded adversaries) under the minimal complexity assumption that one-way functions exist. Consequently, one-way functions suffice to give statistical zero-knowledge arguments for any NP statement (whereby even a computationally unbounded adversarial verifier learns nothing other than the fact that the assertion being proven is true, and no polynomial-time adversarial prover can convince the verifier of a false statement). These results resolve an open question posed by Naor et al. [J. Cryptology, 11 (1998), pp. 87–108].

A theorem of Green, Tao, and Ziegler can be stated (roughly) as follows: ifR is a pseudorandom set, and D is a dense subset of R, then D may be modeled by a set M that is dense in the entire domain such that D and M are indistinguishable. (The precise statement refers to"measures" or distributions rather than sets.) The proof of this theorem is very general, and it applies to notions of pseudo-randomness and indistinguishability defined in terms of any family of distinguishers with some mild closure properties. The proof proceeds via iterative partitioning and an energy increment argument, in the spirit of the proof of the weak Szemeredi regularity lemma. The "reduction" involved in the proof has exponential complexity in the distinguishing probability. We present a new proof inspired by Nisan's proof of Impagliazzo's hardcore set theorem. The reduction in our proof has polynomial complexity in the distinguishing probability and provides a new characterization of the notion of "pseudoentropy" of a distribution. A proof similar to ours has also been independently discovered by Gowers [2]. We also follow the connection between the two theorems and obtain a new proof of Impagliazzo's hardcore set theorem via iterative partitioning and energy increment. While our reduction has exponential complexity in some parameters, it has the advantage that the hardcore set is efficiently recognizable.

We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded “bias,” even if one of the two parties deviates from the protocol (possibly using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on $\{0,1\}^n$ is bounded by a constant less than 1. We present a protocol for the above problem that has $2 \log^* n + O(1)$ rounds, improving a previous $2n$-round protocol of Goldreich, Goldwasser, and Linial (FOCS '91). Like the GGL Protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set $T \subseteq \{0,1\}^n$ of density $\mu$ with probability at most $O(\sqrt{\mu + \delta})$, where $\delta$ may be an arbitrarily small constant. We then prove a nearly matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least $\log^* n - \log^* \log^* n - O(1)$ rounds. We also prove several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set $T \subseteq \{0,1\}^n$.

We present a deterministic logspace algorithm for solving S-T CONNECTIVITY on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex s has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T CONNECTIVITY on undirected graphs [15]. It identifies knowledge of the stationary distribution as the gap between the S-T CONNECTIVITY problems we know how to solve in logspace (L) and those that capture all of randomized logspace (RL).

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma, Umans, and Zuckerman (STOC "01) required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy (FOCS "05). Our expanders can be interpreted as near-optimal "randomness condensers," that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. (STOC "03) and improving upon it when the error parameter is small (e.g. 1/poly(n)).

Average-case complexity, which examines the tractability of computational problems on ‘random instances,’ is a major topic in complexity theory with at least two distinct motivations. On one hand, it may provide a more realistic model than worst-case complexity for the problem instances actually encountered in practice. On the other hand, it provides us with methods to generate hard instances, allowing us to harness intractability for useful ends such as cryptography and derandomization. These two motivations are actually supported by a variety of different notions of average-case complexity (surveyed in [17, 13, 6]) and relating these notions is an important direction for research in the area. An even more ambitious goal is to understand the relationship between average-case complexity and worst-case complexity, e.g., whether NP = P implies that NP has problems that are hard on average. In recent years, there has been substantial progress on this front. This special issue aims to present a small sample of papers that are representative of the different types of results that have been obtained:

Impagliazzo and Wigderson (1998) gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely EXP ≠ BPP). Unlike results in the nonuniform setting, their result does not provide a continuous trade-off between worst-case hardness and pseudorandomness, nor does it explicitly establish an average-case hardness result. In this paper: We obtain an optimal worst-case to average-case connection for EXP: if EXP $$\nsubseteq$$ BPTIME(t(n)), then EXP has problems that cannot be solved on a fraction $$1/2 + 1/t^{\prime}(n)$$ of the inputs by BPTIME $$(t^{\prime}(n))$$ algorithms, for $$t^{\prime}= t^{\Omega(1)}$$ . We exhibit a PSPACE-complete self-correctible and downward self-reducible problem. This slightly simplifies and strengthens the proof of Impagliazzo and Wigderson, which used a #P-complete problem with these properties. We argue that the results of Impagliazzo and Wigderson, and the ones in this paper, cannot be proved via “black-box” uniform reductions.

We give two applications of Nisan–Wigderson‐type (NW‐type) (“noncryptographic”) pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW‐type generator, we construct the following two protocols: (1) a one‐message witness‐indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any setup assumption, so it is actually an “NP proof system.” (2) a noninteractive bit‐commitment scheme based on any one‐way function. The specific NW‐type generator we need is a hitting set generator fooling nondeterministic circuits. It is known how to construct such a generator if $E = DTIME(2^{O(n)})$ has a function of nondeterministic circuit complexity $2^{\Omega(n)}$. Our witness‐indistinguishable proofs are obtained by using the NW‐type generator to derandomize the ZAPs of Dwork and Naor [Proceedings of the 41st Annual ACM Symposium on Foundations of Computer Science, 2000, pp. 283–293]. To our knowledge, this is the first construction of an NP proof system achieving a secrecy property. Our commitment scheme is obtained by derandomizing the interactive commitment scheme of Naor [J. Cryptology, 4 (1991), pp. 151–158]. Previous constructions of noninteractive commitment schemes were known only under incomparable assumptions.

We show that every language in NP has a statistical zero-knowledge argument system under the (minimal) complexity assumption that one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the fact that the assertion being proven is true, whereas a polynomial-time prover cannot convince the verifier to accept a false assertion except with negligible probability. This resolves an open question posed by Naor et al. (1998). Departing from previous works on this problem, we do not construct standard statistically hiding commitments from any one-way function. Instead, we construct a relaxed variant of commitment schemes called "1-out-of-2-binding commitments," recently introduced by Nguyen et al. (2006)

Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number of agents grows. We study two models of concisely represented games: circuit games , where the payoffs are computed by a given boolean circuit, and graph games , where each agent’s payoff is a function of only the strategies played by its neighbors in a given graph. For these two models, we study the complexity of four questions: determining if a given strategy is a Nash equilibrium, finding a Nash equilibrium, determining if there exists a pure Nash equilibrium, and determining if there exists a Nash equilibrium in which the payoffs to a player meet some given guarantees. In many cases, we obtain tight results, showing that the problems are complete for various complexity classes.

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on (0,1)n as sources generated by width 2s branching programs: For every constant δ>0, we can extract .99 δ n bits that are exponentially close to uniform (in variation distance) from space s sources of min-entropy δ n, where s=Ω(n). In addition, assuming an efficient deterministic algorithm for finding large primes, there is a constant η > 0 such that for any δ>n-η, we can extract m=(δ-δ)n bits that are exponentially close to uniform from space s sources with min-entropy δ n, where s=Ω(β3 n). Previously, nothing was known for δ ≤ 1/2, even for space 0.Our results are obtained by a reduction to a new class of sources that we call independent-symbol sources, which generalize both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a string of n independent symbols over a d symbol alphabet with min-entropy k. We give deterministic extractors for such sources when k is as small as polylog(n), for small enough d.

We prove that every problem in NP that has a zero-knowledge proof also has a zero-knowledge proof where the prover can be implemented in probabilistic polynomial time given an NP witness. Moreover, if the original proof system is statistical zero knowledge, so is the resulting efficient-prover proof system. An equivalence of zero knowledge and efficient-prover zero knowledge was previously known only under the assumption that one-way functions exist (whereas our result is unconditional), and no such equivalence was known for statistical zero knowledge. Our results allow us to translate the many general results and characterizations known for zero knowledge with inefficient provers to zero knowledge with efficient provers.

We revisit the general RL vs. L question, obtaining the following results.

We continue the study of the trade‐off between the length of probabilistically checkable proofs (PCPs) and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size n): 1. We present PCPs of length $\exp(o(\log\log n)^2)\cdot n$ that can be verified by making $o(\log\log n)$ Boolean queries. 2. For every \epsilon>0, we present PCPs of length $\exp(\log^\epsilon n)\cdot n$ that can be verified by making a constant number of Boolean queries. In both cases, false assertions are rejected with constant probability (which may be set to be arbitrarily close to 1). The multiplicative overhead on the length of the proof, introduced by transforming a proof into a probabilistically checkable one, is just quasi polylogarithmic in the first case (of query complexity $o(\log\log n)$), and is $2^{(\log n)^\epsilon}$, for any $\epsilon > 0$, in the second case (of constant query complexity). Our techniques include the introduction of a new variant of PCPs that we call “robust PCPs of proximity.” These new PCPs facilitate proof composition, which is a central ingredient in the construction of PCP systems. (A related notion and its composition properties were discovered independently by Dinur and Reingold.) Our main technical contribution is a construction of a “length‐efficient” robust PCP of proximity. While the new construction uses many of the standard techniques used in PCP constructions, it does differ from previous constructions in fundamental ways, and in particular does not use the “parallelization” step of Arora et al. [J. ACM, 45 (1998), pp. 501–555]. The alternative approach may be of independent interest. We also obtain analogous quantitative results for locally testable codes. In addition, we introduce a relaxed notion of locally decodable codes and present such codes mapping k information bits to codewords of length $k^{1+\epsilon}$ for any $\epsilon>0$.

We revisit the problem of hardness amplification in $\mathcal{NP}$, as recently studied by O'Donnell [J. Comput. System Sci., 69 (2004), pp. 68-94]. We prove that if $\mathcal{NP}$ has a balanced function f such that any circuit of size $s(n)$ fails to compute f on a $1/\poly(n)$ fraction of inputs, then $\mathcal{NP}$ has a function $f'$ such that any circuit of size $s'(n)=s(\sqrt{n})^{\Omega(1)}$ fails to compute $f'$ on a $1/2 - 1/s'(n)$ fraction of inputs. In particular, \begin{enumerate} \item if $s(n)=n^{\omega(1)}$, we amplify to hardness $1/2-1/n^{\omega(1)}$; \item if $s(n)=2^{n^{\Omega(1)}}$, we amplify to hardness $1/2-1/2^{n^{\Omega(1)}}$; \item if $s(n)=2^{\Omega(n)}$, we amplify to hardness $1/2-1/2^{\Omega(\sqrt{n})}$. \end{enumerate} Our results improve those of of O'Donnell, which amplify to $1/2-1/\sqrt{n}$. O'Donnell also proved that no construction of a certain general form could amplify beyond $1/2-1/n$. We bypass this barrier by using both derandomization and nondeterminism in the construction of $f'$. We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero‐knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one‐way functions exist. We establish several new characterizations of ZK and use these characterizations to prove results such as the following: 1. Honest‐verifier ZK equals general ZK. 2. Public‐coin ZK equals private‐coin ZK. 3. ZK is closed under union. 4. ZK with imperfect completeness equals ZK with perfect completeness. 5. Any problem in ${\bf ZK} \cap {\bf NP}$ can be proven in computational zero knowledge by a ${\bf BPP}^{{\bf NP}}$ prover. 6. ZK with black‐box simulators equals ZK with general, non–black‐box simulators. The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of ZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero‐knowledge proofs. To enable this combination, we prove that every problem in ZK can be decomposed into a problem in SZK together with a set of instances from which a one‐way function can be constructed.

We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is "close" to a member of the language), where the verifier's running time is polylogarithmic in the input size and the length of the probabilistically checkable proof is only polylogarithmically larger that the length of the classical proof. (Such a verifier can only query polylogarithmically many bits of the input instance and the proof. Thus it needs oracle access to the input as well as the proof, and cannot guarantee that the input is in the language - only that it is close to some string in the language.) If the verifier is restricted further in its query complexity and only allowed q queries, then the proof size blows up by a factor of 2/sup (log n)c/q/ where the constant c depends only on the language (and is independent of q). Our results thus give efficient (in the sense of running time) versions of the shortest known PCPs, due to Ben-Sasson et al. (STOC '04) and Ben-Sasson and Sudan (STOC '05), respectively. The time complexity of the verifier and the size of the proof were the original emphases in the definition of holographic proofs, due to Babai et al. (STOC '91), and our work is the first to return to these emphases since their work. Of technical interest in our proof is a new complete problem for NEXP based on constraint satisfaction problems with very low complexity constraints, and techniques to arithmetize such constraints over fields of small characteristic.

We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on zon is bounded by a constant less than 1.We present a protocol for the above problem that has 2 log*n+O(1) rounds, improving a 2n-round protocol that follows from the work of Goldreich, Goldwasser, and Linial (FOCS'91). Like the GGL protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T⊆zon of density μ with probability at most O(√μ+δ), where δ is an arbitarily small constant.We then prove a matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log*n - log* log*n-O(1) rounds. As far as we know, this is the first nontrivial lower bound on the round complexity of random selection protocols (of any type) that does not impose additional constraints (e.g. on communication or "simulatability").We also state several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T ⊆ zon.

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0, 1} n ). 1. We show how to compress sources X samplable by logspace machines to expected length H(X) + O(1). Our next results concern flat sources whose support is in P. 2. If H(X) ≤ k = n − O(log n), we show how to compress to expected length k + polylog(n − k). 3. If the support of X is the witness set for a self-reducible NP relation, then we show how to compress to expected length H(X) + 5.

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0, l}/sup n/). 1) We show how to compress sources X samplable by logspace machines to expected length H(X) + O(1). Our next results concern flat sources whose support is in P. 2) If H(X) /spl les/ k = n - O(log n), we show how to compress to length k + /spl delta//spl middot/ (n - k) for any constant /spl delta/ > 0; in quasi-polynomial time we show how to compress to length k + O(polylog log (n - k)) even if k = n -polylog(n). 3) If the support of X is the witness set for a self-reducible NP relation, then we show how to compress to expected length H(X) + 4.

We prove a number of general theorems about CZK, the class of problems possessing computational zero knowledge proofs. Our results are unconditional, in contrast to most previous works on CZK which rely on the assumption that one-way functions exist. We establish several new characterizations of CZK, and use these characterizations to prove results such as: 1) Honest-verifier CZK equals general CZK. 2) Public-coin CZK equals private-coin CZK. 3) CZK is closed under union (and more generally, "monotone formula closure"). 4) CZK with imperfect completeness equals CZK with perfect completeness. 5) Any problem in CZK /spl cap/ NP can be proven in computational zero knowledge by a BPP/sup NP/ prover. 6) CZK with black-box simulators equals CZK with general, non-black-box simulators. The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of CZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero knowledge proofs. To enable this combination, we prove that every problem in CZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.

We continue the study of the trade-off between the length of PCP sand their query complexity, establishing the following main results(which refer to proofs of satisfiability of circuits of size n): 1 We present PCPs of length exp(Õ(log log n)2)•n that can be verified by making o(log logn) Boolean queries.For every ε>0, we present PCPs of length exp(logε n)• n that can be verified by making a constant number of Boolean queries. In both cases, false assertions are rejected withconstant probability (which may be set to be arbitrarily close to 1). The multiplicative overhead on the length of the proof, introduced by transforming a proof into a probabilistically checkable one, is just quasi-polylogarithmic in the first case (ofquery complexity o(log logn)), and 2(log n)ε, for any ε>0, in the second case (of constant query complexity). In contrast, previous results required at least 2 √logn overhead in the length, even to get query complexity 2 √log n. Our techniques include the introduction of a new variant of PCPs that we call "Robust PCPs". These new PCPs facilitate proof composition, which is a central ingredient in construction of PCP systems. (A related notion and its composition properties were discovered independently by Dinur and Reingold. ) Our main technical contribution is a construction of a "length-efficient" Robust PCP. While the new construction uses many of the standard techniques in PCPs, it does differ from previous constructions in fundamental ways, and in particular does not use the "parallelization" step of Arora et al. . The alternative approach may be of independent interest. We also obtain analogous quantitative results for locally testable codes. In addition, we introduce a relaxed notion of locally decodable codes,and present such codes mapping k information bits to code words of length κ1+ε, for any ε>0.

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a function f′ such that any circuit of size s′(n)=s(√n)Ω(1) fails to compute f′ on a 1/2 - 1/s′(n) fraction of inputs. In particular, 1. If s(n)=nω(1), we amplify to hardness 1/2-1/nω(1). 2. If s(n)=2nω(1), we amplify to hardness 1/2-1/2nΩ(1). 3. If s(n)=2(n), we amplify to hardness 1/2-1/2 Ω(sqrtn).These improve the results of O'Donnell, which only amplified to 1/2-1/√n. O'Donnell also proved that no construction of a certain general form could amplify beyond 1/2-1/n. We bypass this barrier by using both derandomization and nondeterminism in the construction of f′.We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).

We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a constant-round zero-knowledge strong proof (or argument) of knowledge (as defined by Goldreich, 2001) for a nontrivial language; 2. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete language; 3. There does not exist a constant-round public-coin proof system for a nontrivial language that is resettable zero knowledge. This result also extends to bounded resettable zero knowledge. In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) argument system that is bounded-resettable zero knowledge.

We present the first explicit construction of Probabilistically Checkable Proofs (PCPs) and Locally Testable Codes (LTCs) of fixed constant query complexity which have almost-linear (= n * 2Õ(√log n)) size. Such objects were recently shown to exist (nonconstructively) by Goldreich and Sudan[17]. Previous explicit constructions required size n1 + Ω(ε) with 1/ε queries. The key to these constructions is a nearly optimal randomness-efficient version of the low degree test[32]. In a similar way we give a randomness-efficient version of the BLR linearity test[13] (which is used, for instance, in locally testing the Hadamard code). The derandomizations are obtained through ε-biased sets for vector spaces over finite fields. The analysis of the derandomized tests rely on alternative views of ε-biased sets --- as generating sets of Cayley expander graphs for the low degree test, and as defining linear error-correcting codes for the linearity test.

This paper provides the first explicit construction of extractors which are simultaneously optimal up to constant factors in both seed length and output length. More precisely, for every n,k, our extractor uses a random seed of length O(log n) to transform any random source on n bits with (min-)entropy k, into a distribution on (1-α)k bits that is e-close to uniform. Here α and e can be taken to be any positive constants. (In fact, e can be almost polynomially small.Our improvements are obtained via three new techniques, each of which may be of independent interest. The first is a general construction of mergers [22] from locally decodable error-correcting codes. The second introduces new condensers that have constant seed length (and retain a constant fraction of the min-entropy in the random source). The third is a way to augment the win-win repeated condensing paradigm of [17] with error reduction techniques like [15] so that the our constant seed-length condensers can be used without error accumulation.

We present the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called Statistical Difference, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge .We propose the use of complete problems to unify and extend the study of statistical zero knowledge. To this end, we examine several consequences of our Completeness Theorem and its proof, such as:---A way to make every (honest-verifier) statistical zero-knowledge proof very communication efficient, with the prover sending only one bit to the verifier (to achieve soundness error 1/2).---Simpler proofs of many of the previously known results about statistical zero knowledge, such as the Fortnow and Aiello--Hεstad upper bounds on the complexity of SZK and Okamoto's result that SZK is closed under complement.---Strong closure properties of SZK that amount to constructing statistical zero-knowledge proofs for complex assertions built out of simpler assertions already shown to be in SZK.---New results about the various measures of "knowledge complexity," including a collapse in the hierarchy corresponding to knowledge complexity in the "hint" sense.---Algorithms for manipulating the statistical difference between efficiently samplable distributions, including transformations that "polarize" and "reverse" the statistical relationship between a pair of distributions.

Impagliazzo and Wigderson (1998) gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely EXP = BPP). Unlike results in the nonuniform setting, their result does not provide a continuous trade-off between worst-case hardness and pseudorandomness, nor does it explicitly establish an average-case hardness result. We obtain an optimal worst-case to average-case connection for EXP: if EXP BPTIME(( )), EXP has problems that are cannot be solved on a fraction 1/2 1/'( ) of the inputs by BPTIME('( )) algorithms, for ' = /sup 1/. We exhibit a PSPACE-complete downward self-reducible and random self-reducible problem. This slightly simplifies and strengthens the proof of Impagliazzo and Wigderson (1998), which used a a P-complete problem with these properties. We argue that the results in Impagliazzo and Wigderson (1998) and in this paper cannot be proved via "black-box" uniform reductions.

Since its introduction by Nisan and Zuckerman at STOC '93 (1996) nearly a decade ago, the notion of a randomness extractor has proven to be a fundamental and powerful one. Extractors and their variants have found widespread application in a variety of areas, including pseudorandomness and derandomization, combinatorics, cryptography, data structures, and computational complexity. Equally striking has been a sequence of discoveries showing that, under different interpretations, extractors are close relatives of a number of other important objects, such as expander graphs, hash functions, error-correcting codes, pseudorandom generators, and sampling algorithms. Through these connections, extractors have unified the study of these objects and have led to new and improved constructions of each. We give an introduction to the study of extractors. The article is built around the connections between extractors and the other objects mentioned above. Within the context of these connections, we hope to convey an understanding of the definition of extractors, some intuition for how they are constructed, and a glimpse of their use in applications.

The main concrete result of this paper is the first explicit construction of constant degree lossless expanders. In these graphs, the expansion factor is almost as large as possible: (1—ε)D, where D is the degree and ε is an arbitrarily small constant. The best previous explicit constructions gave expansion factor D/2, which is too weak for many applications. The D/2 bound was obtained via the eigenvalue method, and is known that that method cannot give better bounds.The main abstract contribution of this paper is the introduction and initial study of randomness conductors, a notion which generalizes extractors, expanders, condensers and other similar objects. In all these functions, certain guarantee on the input "entropy" is converted to a guarantee on the output "entropy". For historical reasons, specific objects used specific guarantees of different flavors. We show that the flexibility afforded by the conductor definition leads to interesting combinations of these objects, and to better constructions such as those above.The main technical tool in these constructions is a natural generalization to conductors of the zig-zag graph product, previously defined for expanders and extractors.

We show that a number of graph-theoretic counting problems remain ${\cal NP}$-hard, indeed $#{\cal P}$-complete, in very restricted classes of graphs. In particular, we prove that the problems of counting matchings, vertex covers, independent sets, and extremal variants of these all remain hard when restricted to planar bipartite graphs of bounded degree or regular graphs of constant degree. We obtain corollaries about counting cliques in restricted classes of graphs and counting satisfying assignments to restricted classes of monotone 2-CNF formulae. To achieve these results, a new interpolation-based reduction technique which preserves properties such as constant degree is introduced.

The main contribution is a new type of graph product, which we call the zig-zag product. Taking a product of a large graph with a small graph, the resulting graph inherits (roughly) its size from the large one, its degree from the small one, and its expansion properties from both. Iteration yields simple explicit constructions of constant-degree expanders of every size, starting from one constant-size expander. Crucial to our intuition (and simple analysis) of the properties of this graph product is the view of expanders as functions which act as "entropy wave" propagators-they transform probability distributions in which entropy is concentrated in one area to distributions where that concentration is dissipated. In these terms, the graph product affords the constructive interference of two such waves. A variant of this product can be applied to extractors, giving the first explicit extractors whose seed length depends (poly)logarithmically on only the entropy deficiency of the source (rather than its length) and that extract almost all the entropy of high min-entropy sources. These high min-entropy extractors have several interesting applications, including the first constant-degree explicit expanders which beat the "eigenvalue bound".

The standard notion of a randomness extractor is a procedure which converts any weak source of randomness into an almost uniform distribution. The conversion necessarily uses a small amount of pure randomness, which can be eliminated by complete enumeration in some, but not all, applications. We consider the problem of deterministically converting a weak source of randomness into an almost uniform distribution. Previously, deterministic extraction procedures were known only for sources satisfying strong independence requirements. We look at sources which are samplable, i.e. can be generated by an efficient sampling algorithm. We seek an efficient deterministic procedure that, given a sample from any samplable distribution of sufficiently large min-entropy, gives an almost uniformly distributed output. We explore the conditions under which such deterministic extractors exist. We observe that no deterministic extractor exists if the sampler is allowed to use more computational resources than the extractor. On the other hand, if the extractor is allowed (polynomially) more resources than the sampler, we show that deterministic extraction becomes possible. This is true unconditionally in the nonuniform setting (i.e., when the extractor can be computed by a small circuit), and (necessarily) relies on complexity assumptions in the uniform setting.

Article Free Access Share on On transformation of interactive proofs that preserve the prover's complexity Author: Salil Vadhan MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MAView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 200–207https://doi.org/10.1145/335305.335330Published:01 May 2000Publication History 5citation358DownloadsMetricsTotal Citations5Total Downloads358Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pair of circuits, and YES instances (resp., NO instances) are such pairs in which the first (resp., second) circuit generates a distribution with noticeably higher entropy. On one hand we show that any language having a (honest-verifier) statistical zero-knowledge proof is Karp-reducible to ED. On the other hand, we present a public-coin (honest-verifier) statistical zero-knowledge proof for ED. Thus, we obtain an alternative proof of Okamoto's result by which HVSZK: (i.e., honest-verifier statistical zero knowledge) equals public-coin HVSZK. The new proof is much simpler than the original one. The above also yields a trivial proof that HVSZK: is closed under complementation (since ED easily reduces to its complement). Among the new results obtained is an equivalence of a weak notion of statistical zero knowledge to the standard one.

Summary form only given. R. Impagliazzo and A. Wigderson (1997) have recently shown that if there exists a decision problem solvable in time 2/sup O(n)/ and having circuit complexity 2/sup /spl Omega/(n)/ (for all but finitely many n) then P=BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators. The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-Wigderson (1994) generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs.

We efficiently combine unpredictability and verifiability by extending the Goldreich-Goldwasser-Micali (1986) construction of pseudorandom functions f/sub s/ from a secret seed s, so that knowledge of s not only enables one to evaluate f/sub s/ at any point x, but also to provide an NP-proof that the value f/sub s/(x) is indeed correct without compromising the unpredictability of f/sub s/ at any other point for which no such a proof was provided.

An extractor is a function which extracts (almost) truly random bits from a weak random source, using a small number of additional random bits as a catalyst. We present a general method to reduce the error of any extractor. Our method works particularly well in the case that the original extractor extracts up to a constant function of the source min-entropy and achieves a polynomially small error. In that case, we are able to reduce the error to (almost) any /spl epsiv/, using only O(log(1//spl epsiv/)) additional truly random bits (while keeping the other parameters of the original extractor more or less the same). In other cases (e.g. when the original extractor extracts all the min-entropy or achieves only a constant error), our method is not optimal but it is still quite efficient and leads to improved constructions of extractors. Using our method, we are able to improve almost all known extractors in the case where the error required is relatively small (e.g. less than a polynomially small error). In particular, we apply our method to the new extractors of L. Trevisan (1999) and R. Raz et al. (1999) to obtain improved constructions in almost all cases. Specifically, we obtain extractors that work for sources of any min-entropy on strings of length n which (a) extract any 1/n/sup /spl gamma// fraction of the min-entropy using O[log n+log(1//spl epsiv/)] truly random bits (for any /spl gamma/>0), (b) extract any constant fraction of the min-entropy using O[log/sup 2/n+log(1//spl epsiv/)] truly random bits, and (c) extract all the min-entropy using O[log/sup 3/n+log n/spl middot/log(1//spl epsiv/)] truly random bits.

We give explicit constructions of extractors which work for a source of any min.entropyon strings of length n.The first construction extracts any constant fraction of the min-entropy using O(log* n) additional random bits, The second extracts all the tin-entropy using O(log3 n) additional random bits.Both of these constmcdons use fewer truly random bits than any previous construction which works for all min.entropiesand extracts a constant fraction of the min.entropy.We then improve our second construction and show that we can reduce the entropy loss to 2 log(l/e) +0(l) bits, while still using O(log3 n) truly random bits (where entropy loss is defined as [(source min-entropy) + (# truly random bits used) -(#output bits)], and E is the statistical difference from uniform achieved).This entropy loss is optimal up to a constant additive term.Our extractors are obtained by observing that a weaker notion of "combinatorial design" suffices for the Nisan-Wigderson pseudorandom generator, which underlies the recent extractor of Trevisa We give near-optimal constructions of such "weak designs" which achieve much better parameters than possible with the notion of designs used by Nisan-Wigderson and Trevisan.We also show how to improve our constructions (and Trevisan's construction) when the required statistical difference from uniform distribution E is relatively small.This improvement is obtained by using multilinear error correcting codes over finite fields, rather than the arbitrary error correcting codes used by Trevisan.

] Madhu Sudan y Luca Trevisan z Salil Vadhan x Abstract Impagliazzo and Wigderson [IW97] have recently shown that if there exists a decision problem solvable in time 2 O(n) and having circuit complexity 2 \\Omega\\Gamma n) (for all but finitely many n) then P = BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators. The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-- Wigderson [NW94] generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs. Our firs...

Article The power of a pebble: exploring and mapping directed graphs Share on Authors: Michael A. Bender Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA Division of Engineering and Applied Sciences, Harvard University, Cambridge, MAView Profile , Antonio Fernández Dpto de Arquitectura y Tecnología de Computadores, Universidad Politécnica de Madrid and Laboratory for Computer Science, MIT Dpto de Arquitectura y Tecnología de Computadores, Universidad Politécnica de Madrid and Laboratory for Computer Science, MITView Profile , Dana Ron Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile , Amit Sahai Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile , Salil Vadhan Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 269–278https://doi.org/10.1145/276698.276759Online:23 May 1998Publication History 103citation603DownloadsMetricsTotal Citations103Total Downloads603Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We show how to transform any interactive proof system which is statistical zero-knowledge with respect to the honest-verifier, into a proof systemwhich is statistical zero-knowledgewith respect to any verifier. This is done by limiting the behavior of potentially cheating verifiers, without using computational assumptions or even referring to the complexity of such verifier strategies. (Previous transformations have either relied on computational assumptions or were applicable only to constant-round public-coin proof systems.) Our transformation also applies to public-coin (aka Arthur-Merlin) computational zero-knowledge proofs: We transform any ArthurMerlin proof system which is computational zero-knowledge with respect to the honest-verifier, into an Arthur-Merlin proof system which is computational zero-knowledge with respect to any probabilistic polynomial-time verifier. A crucial ingredient in our analysis is a new lemma regarding 2-universal hashing functions. 1 Introduction Zer...

We present a Monte Carlo algorithm for testing multivariate polynomial identities over any field using fewer random bits than other methods. To test if a polynomial \\(P(x_1, ..., x_n)\\) is zero, our method uses \\(\\sum_{i=1}^n \\log \\lceil d_i+1 \\rceil\\) random bits, where \\(d_i\\) is the degree of \\(x_i\\) in \\(P\\), to obtain any inverse polynomial error in polynomial time. The algorithm applies to polynomials given as a black box or in some implicit representation such as a straight-line program. Our method works by evaluating P at truncated formal power series representing square roots of irreducible polynomials over the field. This approach is similar to that of Chen and Kao (STOC '97), but with the advantage that the techniques are purely algebraic and apply to any field. We also prove a lower bound showing that the number of random bits used by our algorithm is essentially optimal in the black-box model.

We present a complete promise problem for SZK, the class of languages possessing statistical zero-knowledge proofs (against an honest verifier). The problem is to decide whether two efficiently samplable distributions are either statistically close or far apart. This characterizes SZK with no reference to interaction or zero-knowledge. From this theorem and its proof we are able to establish several other results about SZK, knowledge complexity, and efficiently samplable distributions.