Boaz Barak

JMLR Journal 2025 Journal Article

Scaling Data-Constrained Language Models

• Niklas Muennighoff
• Alexander M. Rush
• Boaz Barak
• Teven Le Scao
• Aleksandra Piktus
• Nouamane Tazi
• Sampo Pyysalo
• Thomas Wolf

The current trend of scaling language models involves increasing both parameter count and training data set size. Extrapolating this trend suggests that training data set size may soon be limited by the amount of text data available on the internet. Motivated by this limit, we investigate scaling language models in data-constrained regimes. Specifically, we run a large set of experiments varying the extent of data repetition and compute budget, ranging up to 900 billion training tokens and 9 billion parameter models. We find that with constrained data for a fixed compute budget, training with up to 4 epochs of repeated data yields negligible changes to loss compared to having unique data. However, with more repetition, the value of adding compute eventually decays to zero. We propose and empirically validate a scaling law for compute optimality that accounts for the decreasing value of repeated tokens and excess parameters. Finally, we experiment with approaches mitigating data scarcity, including augmenting the training data set with code data or removing commonly used filters. Models and data sets from our 400 training runs are freely available at https://github.com/huggingface/datablations. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2025. ( edit, beta )

ICML Conference 2024 Conference Paper

Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning

• Nikhil Vyas 0001
• Depen Morwani
• Rosie Zhao
• Gal Kaplun
• Sham M. Kakade
• Boaz Barak

The success of SGD in deep learning has been ascribed by prior works to the implicit bias induced by finite batch sizes (”SGD noise”). While prior works focused on offline learning (i. e. , multiple-epoch training), we study the impact of SGD noise on online (i. e. , single epoch) learning. Through an extensive empirical analysis of image and language data, we demonstrate that small batch sizes do not confer any implicit bias advantages in online learning. In contrast to offline learning, the benefits of SGD noise in online learning are strictly computational, facilitating more cost-effective gradient steps. This suggests that SGD in the online regime can be construed as taking noisy steps along the ”golden path” of the noiseless gradient descent algorithm. We study this hypothesis and provide supporting evidence in loss and function space. Our findings challenge the prevailing understanding of SGD and offer novel insights into its role in online learning.

ICML Conference 2024 Conference Paper

Distinguishing the Knowable from the Unknowable with Language Models

• Gustaf Ahdritz
• Tian Qin
• Nikhil Vyas 0001
• Boaz Barak
• Benjamin L. Edelman

We study the feasibility of identifying epistemic uncertainty (reflecting a lack of knowledge), as opposed to aleatoric uncertainty (reflecting entropy in the underlying distribution), in the outputs of large language models (LLMs) over free-form text. In the absence of ground-truth probabilities, we explore a setting where, in order to (approximately) disentangle a given LLM’s uncertainty, a significantly larger model stands in as a proxy for the ground truth. We show that small linear probes trained on the embeddings of frozen, pretrained models accurately predict when larger models will be more confident at the token level and that probes trained on one text domain generalize to others. Going further, we propose a fully unsupervised method that achieves non-trivial accuracy on the same task. Taken together, we interpret these results as evidence that LLMs naturally contain internal representations of different types of uncertainty that could potentially be leveraged to devise more informative indicators of model confidence in diverse practical settings. Code can be found at: https: //github. com/KempnerInstitute/llm_uncertainty

ICML Conference 2024 Conference Paper

Watermarks in the Sand: Impossibility of Strong Watermarking for Language Models

• Hanlin Zhang 0002
• Benjamin L. Edelman
• Danilo Francati
• Daniele Venturi 0001
• Giuseppe Ateniese
• Boaz Barak

Watermarking generative models consists of planting a statistical signal (watermark) in a model’s output so that it can be later verified that the output was generated by the given model. A strong watermarking scheme satisfies the property that a computationally bounded attacker cannot erase the watermark without causing significant quality degradation. In this paper, we study the (im)possibility of strong watermarking schemes. We prove that, under well-specified and natural assumptions, strong watermarking is impossible to achieve. This holds even in the private detection algorithm setting, where the watermark insertion and detection algorithms share a secret key, unknown to the attacker. To prove this result, we introduce a generic efficient watermark attack; the attacker is not required to know the private key of the scheme or even which scheme is used. Our attack is based on two assumptions: (1) The attacker has access to a "quality oracle" that can evaluate whether a candidate output is a high-quality response to a prompt, and (2) The attacker has access to a "perturbation oracle" which can modify an output with a nontrivial probability of maintaining quality, and which induces an efficiently mixing random walk on high-quality outputs. We argue that both assumptions can be satisfied in practice by an attacker with weaker computational capabilities than the watermarked model itself, to which the attacker has only black-box access. Furthermore, our assumptions will likely only be easier to satisfy over time as models grow in capabilities and modalities. We demonstrate the feasibility of our attack by instantiating it to attack three existing watermarking schemes for large language models: Kirchenbauer et al. (2023), Kuditipudi et al. (2023), and Zhao et al. (2023), and include preliminary results on vision-language models. The same attack successfully removes the watermarks planted by all schemes, with only minor quality degradation.

ICLR Conference 2023 Conference Paper

Deconstructing Distributions: A Pointwise Framework of Learning

• Gal Kaplun
• Nikhil Ghosh
• Saurabh Garg
• Boaz Barak
• Preetum Nakkiran

In machine learning, we traditionally evaluate the performance of a single model, averaged over a collection of test inputs. In this work, we propose a new approach: we measure the performance of a collection of models when evaluated at *single input point*. Specifically, we study a point's *profile*: the relationship between models' average performance on the test distribution and their pointwise performance on this individual point. We find that profiles can yield new insights into the structure of both models and data---in and out-of-distribution. For example, we empirically show that real data distributions consist of points with qualitatively different profiles. On one hand, there are ``compatible'' points with strong correlation between the pointwise and average performance. On the other hand, there are points with weak and even *negative* correlation: cases where improving overall model accuracy actually *hurts* performance on these inputs. As an application, we use profiles to construct a dataset we call CIFAR-10-NEG: a subset of CINIC-10 such that for standard models, accuracy on CIFAR-10-NEG is *negatively correlated* with CIFAR-10 accuracy. Illustrating for the first time an OOD dataset that completely inverts ``accuracy-on-the-line'' (Miller et al., 2021).

TMLR Journal 2023 Journal Article

Named Tensor Notation

• David Chiang
• Alexander M Rush
• Boaz Barak

We propose a notation for tensors with named axes, which relieves the author, reader, and future implementers of machine learning models from the burden of keeping track of the order of axes and the purpose of each. The notation makes it easy to lift operations on low-order tensors to higher order ones, for example, from images to minibatches of images, or from an attention mechanism to multiple attention heads. After a brief overview and formal definition of the notation, we illustrate it through several examples from modern machine learning, from building blocks like attention and convolution to full models like Transformers and LeNet. We then discuss differential calculus in our notation and compare with some alternative notations. Our proposals build on ideas from many previous papers and software libraries. We hope that this document will encourage more authors to use named tensors, resulting in clearer papers and more precise implementations.

ICML Conference 2023 Conference Paper

On Provable Copyright Protection for Generative Models

• Nikhil Vyas 0001
• Sham M. Kakade
• Boaz Barak

There is a growing concern that learned conditional generative models may output samples that are substantially similar to some copyrighted data $C$ that was in their training set. We give a formal definition of near access-freeness (NAF) and prove bounds on the probability that a model satisfying this definition outputs a sample similar to $C$, even if $C$ is included in its training set. Roughly speaking, a generative model $p$ is $k$-NAF if for every potentially copyrighted data $C$, the output of $p$ diverges by at most $k$-bits from the output of a model $q$ that did not access $C$ at all. We also give generative model learning algorithms, which efficiently modify the original generative model learning algorithm in a black box manner, that output generative models with strong bounds on the probability of sampling protected content. Furthermore, we provide promising experiments for both language (transformers) and image (diffusion) generative models, showing minimal degradation in output quality while ensuring strong protections against sampling protected content.

NeurIPS Conference 2023 Conference Paper

Scaling Data-Constrained Language Models

• Niklas Muennighoff
• Alexander Rush
• Boaz Barak
• Teven Le Scao
• Nouamane Tazi
• Aleksandra Piktus
• Sampo Pyysalo
• Thomas Wolf

The current trend of scaling language models involves increasing both parameter count and training dataset size. Extrapolating this trend suggests that training dataset size may soon be limited by the amount of text data available on the internet. Motivated by this limit, we investigate scaling language models in data-constrained regimes. Specifically, we run a large set of experiments varying the extent of data repetition and compute budget, ranging up to 900 billion training tokens and 9 billion parameter models. We find that with constrained data for a fixed compute budget, training with up to 4 epochs of repeated data yields negligible changes to loss compared to having unique data. However, with more repetition, the value of adding compute eventually decays to zero. We propose and empirically validate a scaling law for compute optimality that accounts for the decreasing value of repeated tokens and excess parameters. Finally, we experiment with approaches mitigating data scarcity, including augmenting the training dataset with code data or removing commonly used filters. Models and datasets from our 400 training runs are freely available at https: //github. com/huggingface/datablations.

NeurIPS Conference 2022 Conference Paper

Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit

• Boaz Barak
• Benjamin Edelman
• Surbhi Goel
• Sham Kakade
• Eran Malach
• Cyril Zhang

There is mounting evidence of emergent phenomena in the capabilities of deep learning methods as we scale up datasets, model sizes, and training times. While there are some accounts of how these resources modulate statistical capacity, far less is known about their effect on the computational problem of model training. This work conducts such an exploration through the lens of learning a $k$-sparse parity of $n$ bits, a canonical discrete search problem which is statistically easy but computationally hard. Empirically, we find that a variety of neural networks successfully learn sparse parities, with discontinuous phase transitions in the training curves. On small instances, learning abruptly occurs at approximately $n^{O(k)}$ iterations; this nearly matches SQ lower bounds, despite the apparent lack of a sparse prior. Our theoretical analysis shows that these observations are not explained by a Langevin-like mechanism, whereby SGD "stumbles in the dark" until it finds the hidden set of features (a natural algorithm which also runs in $n^{O(k)}$ time). Instead, we show that SGD gradually amplifies the sparse solution via a Fourier gap in the population gradient, making continual progress that is invisible to loss and error metrics.

ICLR Conference 2021 Conference Paper

For self-supervised learning, Rationality implies generalization, provably

• Yamini Bansal
• Gal Kaplun
• Boaz Barak

We prove a new upper bound on the generalization gap of classifiers that are obtained by first using self-supervision to learn a representation $r$ of the training~data, and then fitting a simple (e.g., linear) classifier $g$ to the labels. Specifically, we show that (under the assumptions described below) the generalization gap of such classifiers tends to zero if $\mathsf{C}(g) \ll n$, where $\mathsf{C}(g)$ is an appropriately-defined measure of the simple classifier $g$'s complexity, and $n$ is the number of training samples. We stress that our bound is independent of the complexity of the representation $r$. We do not make any structural or conditional-independence assumptions on the representation-learning task, which can use the same training dataset that is later used for classification. Rather, we assume that the training procedure satisfies certain natural noise-robustness (adding small amount of label noise causes small degradation in performance) and rationality (getting the wrong label is not better than getting no label at all) conditions that widely hold across many standard architectures. We also conduct an extensive empirical study of the generalization gap and the quantities used in our assumptions for a variety of self-supervision based algorithms, including SimCLR, AMDIM and BigBiGAN, on the CIFAR-10 and ImageNet datasets. We show that, unlike standard supervised classifiers, these algorithms display small generalization gap, and the bounds we prove on this gap are often non vacuous.

STOC Conference 2021 Conference Paper

Playing unique games on certified small-set expanders

• Mitali Bafna
• Boaz Barak
• Pravesh K. Kothari
• Tselil Schramm
• David Steurer

We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) “characterized” by a low-degree sum-of-squares proof. Our results are obtained by rounding low-entropy solutions — measured via a new global potential function — to sum-of-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for worst-case optimization problems.

NeurIPS Conference 2021 Conference Paper

Revisiting Model Stitching to Compare Neural Representations

• Yamini Bansal
• Preetum Nakkiran
• Boaz Barak

We revisit and extend model stitching (Lenc & Vedaldi 2015) as a methodology to study the internal representations of neural networks. Given two trained and frozen models $A$ and $B$, we consider a "stitched model" formed by connecting the bottom-layers of $A$ to the top-layers of $B$, with a simple trainable layer between them. We argue that model stitching is a powerful and perhaps under-appreciated tool, which reveals aspects of representations that measures such as centered kernel alignment (CKA) cannot. Through extensive experiments, we use model stitching to obtain quantitative verifications for intuitive statements such as "good networks learn similar representations", by demonstrating that good networks of the same architecture, but trained in very different ways (eg: supervised vs. self-supervised learning), can be stitched to each other without drop in performance. We also give evidence for the intuition that "more is better" by showing that representations learnt with (1) more data, (2) bigger width, or (3) more training time can be "plugged in" to weaker models to improve performance. Finally, our experiments reveal a new structural property of SGD which we call "stitching connectivity", akin to mode-connectivity: typical minima reached by SGD are all "stitching-connected" to each other.

ICLR Conference 2020 Conference Paper

Deep Double Descent: Where Bigger Models and More Data Hurt

• Preetum Nakkiran
• Gal Kaplun
• Yamini Bansal
• Tristan Yang
• Boaz Barak
• Ilya Sutskever

We show that a variety of modern deep learning tasks exhibit a "double-descent" phenomenon where, as we increase model size, performance first gets worse and then gets better. Moreover, we show that double descent occurs not just as a function of model size, but also as a function of the number of training epochs. We unify the above phenomena by defining a new complexity measure we call the effective model complexity, and conjecture a generalized double descent with respect to this measure. Furthermore, our notion of model complexity allows us to identify certain regimes where increasing (even quadrupling) the number of train samples actually hurts test performance.

NeurIPS Conference 2019 Conference Paper

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

• Boaz Barak
• Chi-Ning Chou
• Zhixian Lei
• Tselil Schramm
• Yueqi Sheng

We consider the graph matching/similarity problem of determining how similar two given graphs $G_0, G_1$ are and recovering the permutation $\pi$ on the vertices of $G_1$ that minimizes the symmetric difference between the edges of $G_0$ and $\pi(G_1)$. Graph matching/similarity has applications for pattern matching, vision, social network anonymization, malware analysis, and more. We give the first efficient algorithms proven to succeed in the correlated Erdös-Rényi model (Pedarsani and Grossglauser, 2011). Specifically, we give a polynomial time algorithm for the graph similarity/hypothesis testing task which works for every constant level of correlation between the two graphs that can be arbitrarily close to zero. We also give a quasi-polynomial ($n^{O(\log n)}$ time) algorithm for the graph matching task of recovering the permutation minimizing the symmetric difference in this model. This is the first algorithm to do so without requiring as additional input a ``seed'' of the values of the ground truth permutation on at least $n^{\Omega(1)}$ vertices. Our algorithms follow a general framework of counting the occurrences of subgraphs from a particular family of graphs allowing for tradeoffs between efficiency and accuracy.

NeurIPS Conference 2019 Conference Paper

SGD on Neural Networks Learns Functions of Increasing Complexity

• Dimitris Kalimeris
• Gal Kaplun
• Preetum Nakkiran
• Benjamin Edelman
• Tristan Yang
• Boaz Barak
• Haofeng Zhang

We perform an experimental study of the dynamics of Stochastic Gradient Descent (SGD) in learning deep neural networks for several real and synthetic classification tasks. We show that in the initial epochs, almost all of the performance improvement of the classifier obtained by SGD can be explained by a linear classifier. More generally, we give evidence for the hypothesis that, as iterations progress, SGD learns functions of increasing complexity. This hypothesis can be helpful in explaining why SGD-learned classifiers tend to generalize well even in the over-parameterized regime. We also show that the linear classifier learned in the initial stages is ``retained'' throughout the execution even if training is continued to the point of zero training error, and complement this with a theoretical result in a simplified model. Key to our work is a new measure of how well one classifier explains the performance of another, based on conditional mutual information.

STOC Conference 2017 Conference Paper

Quantum entanglement, sum of squares, and the log rank conjecture

• Boaz Barak
• Pravesh K. Kothari
• David Steurer

For every constant ε>0, we give an exp(Õ(∞ n ))-time algorithm for the 1 vs 1 - ε Best Separable State (BSS) problem of distinguishing, given an n 2 x n 2 matrix ℳ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ that ℳ accepts with probability 1, and the case that every separable state is accepted with probability at most 1 - ε. Equivalently, our algorithm takes the description of a subspace 𝒲 ⊆ 𝔽 n 2 (where 𝔽 can be either the real or complex field) and distinguishes between the case that contains a rank one matrix, and the case that every rank one matrix is at least ε far (in 𝓁 2 distance) from 𝒲. To the best of our knowledge, this is the first improvement over the brute-force exp( n )-time algorithm for this problem. Our algorithm is based on the sum-of-squares hierarchy and its analysis is inspired by Lovett's proof (STOC '14, JACM '16) that the communication complexity of every rank- n Boolean matrix is bounded by Õ(√ n ).

FOCS Conference 2016 Conference Paper

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

• Boaz Barak
• Samuel B. Hopkins 0001
• Jonathan A. Kelner
• Pravesh K. Kothari
• Ankur Moitra
• Aaron Potechin

We prove that with high probability over the choice of a random graph G from the Erdös-Rényi distribution G(n, 1/2), the n O(d) -time degree d Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least n 1/2-c(d/log n)1/2 for some constant c > 0. This yields a nearly tight n 1/2-o(1) bound on the value of this program for any degree d = o(log n). Moreover we introduce a new framework that we call pseudo-calibration to construct Sum-of-Squares lower bounds. This framework is inspired by taking a computational analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i. e. , dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.

STOC Conference 2015 Conference Paper

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

• Boaz Barak
• Jonathan A. Kelner
• David Steurer

We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown n x m matrix A (for m ≥ n) from examples of the form [y = Ax + e,] where x is a random vector in R m with at most τ m nonzero coordinates, and e is a random noise vector in R n with bounded magnitude. For the case m=O(n), our algorithm recovers every column of A within arbitrarily good constant accuracy in time m O(log m/log(τ -1 )) , in particular achieving polynomial time if τ = m -δ for any δ>0, and time m O(log m) if τ is (a sufficiently small) constant. Prior algorithms with comparable assumptions on the distribution required the vector $x$ to be much sparser---at most √n nonzero coordinates---and there were intrinsic barriers preventing these algorithms from applying for denser x.

STOC Conference 2015 Conference Paper

Sum of Squares Lower Bounds from Pairwise Independence

• Boaz Barak
• Siu On Chan
• Pravesh K. Kothari

We prove that for every ε>0 and predicate P:{0,1} k -> {0,1} that supports a pairwise independent distribution, there exists an instance I of the Max P constraint satisfaction problem on n variables such that no assignment can satisfy more than a ~(|P -1 (1)|)/(2 k )+ε fraction of I's constraints but the degree Ω(n) Sum of Squares semidefinite programming hierarchy cannot certify that I is unsatisfiable. Similar results were previously only known for weaker hierarchies.

STOC Conference 2014 Conference Paper

Rounding sum-of-squares relaxations

• Boaz Barak
• Jonathan A. Kelner
• David Steurer

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a combining algorithm ---an algorithm that maps a distribution over solutions into a (possibly weaker) solution---into a rounding algorithm that maps a solution of the relaxation to a solution of the original problem.

STOC Conference 2012 Conference Paper

Hypercontractivity, sum-of-squares proofs, and their applications

• Boaz Barak
• Fernando G. S. L. Brandão
• Aram W. Harrow
• Jonathan A. Kelner
• David Steurer
• Yuan Zhou 0007

We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as |A| 2->q = max v≠ 0 |Av| q /|v| 2 ) for q > 2, as well as connections between this question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture (UGC). We show the following: For any constant even integer q ≥ 4, a graph G is a small-set expander if and only if the projector into the span of the top eigenvectors of G's adjacency matrix has bounded 2->q norm. As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture --- a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n 2/q ) time, thus obtaining a different proof of the known subexponential algorithm for Small-Set-Expansion. Constant rounds of the "Sum of Squares" semidefinite programing hierarchy certify an upper bound on the 2->4 norm of the projector to low degree polynomials over the Boolean cube, as well certify the unsatisfiability of the "noisy cube" and "short code" based instances of Unique-Games considered by prior works. This improves on the previous upper bound of exp(log O(1) n) rounds (for the "short code"), as well as separates the "Sum of Squares"/"Lasserre" hierarchy from weaker hierarchies that were known to require ω(1) rounds. We show reductions between computing the 2->4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2->4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2->4 norm.

FOCS Conference 2012 Conference Paper

Making the Long Code Shorter

• Boaz Barak
• Parikshit Gopalan
• Johan Håstad
• Raghu Meka
• Prasad Raghavendra
• David Steurer

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1) For any ε >; 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - ε, but G's adjacency matrix has more than exp(log δ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2) A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of K polylog(K), improving over the previously known gadget with blowup of 2 Ω(K). 3) An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.

STOC Conference 2011 Conference Paper

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes

• Boaz Barak
• Zeev Dvir
• Amir Yehudayoff
• Avi Wigderson

FOCS Conference 2011 Conference Paper

Rounding Semidefinite Programming Hierarchies via Global Correlation

• Boaz Barak
• Prasad Raghavendra
• David Steurer

We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the in- put graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance 3, a rounding algorithm for r rounds of the Lasserre SDP hierarchy for 3 that obtains an integral solution which is at most ε worse than the relaxation's value (normalized to lie in [0, 1]), as long as r >; k·rank ≥θ (3)/ poly(ε), where k is the alphabet size of J, θ = poly(ε/k), and rank ≥θ (J) denotes the number of eigenvalues larger than θ in the normalized adjacency matrix of the constraint graph of J. In the case that J is a Unique Games instance, the threshold θ is only a polynomial in ε, and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for every instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the nol O(r) constraints specified by the r th level of the Lasserre hierarchy, and in some cases r rounds of our program can be evaluated in time 2 O(r) poly(n).

SODA Conference 2011 Conference Paper

Subsampling Mathematical Relaxations and Average-case Complexity

• Boaz Barak
• Moritz Hardt
• Thomas Holenstein
• David Steurer

We initiate a study of when the value of mathematical relaxations such as linear and semi-definite programs for constraint satisfaction problems (CSPs) is approximately preserved when restricting the instance to a sub-instance induced by a small random subsample of the variables. Let C be a family of CSPs such as 3SAT, Max-Cut, etc. , and let П be a mathematical program that is a relaxation for C, in the sense that for every instance P ∊ C, П( P ) is a number in [0, 1] upper bounding the maximum fraction of satisfiable constraints of P. Loosely speaking, we say that subsampling holds for C and П if for every sufficiently dense instance P ∊ C and every ε > 0, if we let P′ be the instance obtained by restricting P to a sufficiently large constant number of variables, then П( P′ ) ∊ (1 ± ε)П( P ). We say that weak subsampling holds if the above guarantee is replaced with П( P′ ) = 1 − Θ(γ) whenever П( P ) = 1 − γ, where Θ hides only absolute constants. We obtain both positive and negative results, showing that: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the semi-definite program considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every constraint-satisfaction problem under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type. 3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semi-definite programs. Also there are unique CSPs for which (even weak) subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semi-definite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value 1 − γ have a cut value at most 1 − γ/10. More generally, our results give an approach to obtaining average-case algorithms for CSPs using semi-definite programming hierarchies.

STOC Conference 2010 Conference Paper

How to compress interactive communication

• Boaz Barak
• Mark Braverman
• Xi Chen 0001
• Anup Rao 0001

We describe new ways to simulate 2-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most ~O(√CI) bits of communication. If the protocol reveals I bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with ~O(I) bits of communication. These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst case computation, computing n copies of a function requires √n times the communication required for computing one copy of the function. For average case complexity, given any distribution μ on inputs, computing n copies of the function on n inputs sampled independently according to μ requires √n times the communication for computing one copy. If μ is a product distribution, computing n copies on n independent inputs sampled according to μ requires n times the communication required for computing the function. We also study the complexity of computing the sum (or parity) of n evaluations of f, and obtain results analogous to those above.

STOC Conference 2010 Conference Paper

Public-key cryptography from different assumptions

• Benny Applebaum
• Boaz Barak
• Avi Wigderson

This paper attempts to broaden the foundations of public-key cryptography. We construct new public-key encryption schemes based on new hardness-on-average assumptions for natural combinatorial NP-hard optimization problems. We consider the following assumptions: It is infeasible to solve a random set of sparse linear equations mod 2, of which a small fraction is noisy. It is infeasible to distinguish between a random unbalanced bipartite graph, and such a graph in which we "plant" at random in the large side a set S with only |S|/3 neighbors. There is a pseudorandom generator in NCz where every output depends on a random constant-size subset of the inputs. We obtain semantically secure public key encryption schemes based on several combinations of these assumptions with different parameters. In particular we obtain public key encryption from Assumption~1 on its own, yielding the first noisy-equations type public key scheme in which the noise rate is higher than one over the square root of the number of equations. We also obtain public-key encryption based on a combination of Assumptions~2 and~3. These are arguably of more "combinatorial"/"private-key" nature than any assumptions used before for public-key cryptography. Our proof involves novel "search to decision" and "search to prediction" reductions for sparse noisy linear equations. The strength of our assumptions raise new algorithmic and pseudorandomness questions (and new parameters for old ones). We give some evidence for these assumptions by studying their resistance to certain classes of natural algorithms, including semi-definite programs, ACO circuits, low-degree polynomials, and cycle counting. We also relate our assumptions to other problems such as planted clique and learning juntas.

FOCS Conference 2010 Conference Paper

Subexponential Algorithms for Unique Games and Related Problems

• Sanjeev Arora
• Boaz Barak
• David Steurer

We give a subexponential time approximation algorithm for the Unique Games problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, n ε. The approximation guarantee depends on ε, but not on the alphabet size or the number of variables. We also obtain a subexponential algorithms with improved approximations for SMALL-SET EXPANSION and MULTICUT. For MAX CUT, SPARSEST CUT, and VERTEX COVER, we give subexponential algorithms with improved approximations on some interesting subclasses of instances. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for the Unique Games. While our results stop short of refuting the UGC, they do suggest that Unique Games is significantly easier than NP-hard problems such as MAX 3SAT, MAX 3LIN, Label Cover and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio. The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every ε > 0 and every regular n-vertex graph G, by changing at most ε fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most n ε eigenvalues larger than 1 - η, where η depends polynomially on ε.

SODA Conference 2009 Conference Paper

The uniform hardcore lemma via approximate Bregman projections

• Boaz Barak
• Moritz Hardt
• Satyen Kale

FOCS Conference 2008 Conference Paper

On Basing Lower-Bounds for Learning on Worst-Case Assumptions

• Benny Applebaum
• Boaz Barak
• David Xiao

We consider the question of whether P ne NP implies that there exists some concept class that is efficientlyrepresentable but is still hard to learn in the PAC model of Valiant (CACM '84), where the learner is allowed to output any efficient hypothesis approximating the concept, including an "improper" hypothesis that is not itself in the concept class. We show that unless the polynomial hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.

FOCS Conference 2008 Conference Paper

Rounding Parallel Repetitions of Unique Games

• Boaz Barak
• Moritz Hardt
• Ishay Haviv
• Anup Rao 0001
• Oded Regev 0001
• David Steurer

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically, denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(G l ) ges 1-radicsldelta. Here, G l denotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i. e. , k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(G l ) may be much larger than val(G) l, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS'08) has shown such an example using the max-cut game on oddcycles. Our results are based on a generalization of his techniques.

FOCS Conference 2007 Conference Paper

Lower Bounds on Signatures From Symmetric Primitives

• Boaz Barak
• Mohammad Mahmoody

We show that every black-box construction of one-time signature schemes from a random oracle achieves security at most poly(q)2 q. where q is the total number of queries to the oracle by the generation, signing, and verification algorithms. That is, any such scheme can be broken with probability close to 1 by a (computationally unbounded) adversary making poly(q)2 q queries to the oracle. This is tight up to a constant factor in the number of queries, since a simple modification of Lamport's scheme achieves 2 (0. 812-o(1))q security using q queries. Our results extend (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles, and so can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives such as block ciphers, hash functions, and message authentication codes.

STOC Conference 2006 Conference Paper

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction

• Boaz Barak
• Anup Rao 0001
• Ronen Shaltiel
• Avi Wigderson

The main result of this paper is an explicit disperser for two independent sources on n bits, each of entropy k=n o(1) . Put differently, setting N=2 n and K=2 k , we construct explicit N x N Boolean matrices for which no K x K submatrix is monochromatic. Viewed as adjacency matrices of bipartite graphs, this gives an explicit construction of K-Ramsey bipartite graphs of size N.This greatly improves the previous bound of k=o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson [4]. It also significantly improves the 25-year record of k = Õ (√n) on the special case of Ramsey graphs, due to Frankl and Wilson [9].The construction uses (besides "classical" extractor ideas) almost all of the machinery developed in the last couple of years for extraction from independent sources, including: Bourgain's extractor for 2 independent sources of some entropy rate 1/2 [18] Rao's extractor for 2 independent block-sources of entropy n Ω (1) [17] The "Challenge-Response" mechanism for detecting "entropy concentration" of [4].

FOCS Conference 2006 Conference Paper

Concurrent Non-Malleable Zero Knowledge

• Boaz Barak
• Manoj Prabhakaran 0001
• Amit Sahai

We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol Pi such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of Pi, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities {including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC2004). We obtain an Otilde(n) -round protocol under the assumption that one-to-one one-way functions exist. This can be improved to Otilde(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol

FOCS Conference 2005 Conference Paper

How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation

• Boaz Barak
• Amit Sahai

We construct a secure protocol for any multiparty functionality that remains secure (under a relaxed definition of security introduced by Prabhakaran and Sahai (STOC '04)) when executed concurrently with multiple copies of itself and other protocols, without any assumptions on existence of trusted parties, common reference string, honest majority or synchronicity of the network. The relaxation of security is obtained by allowing the ideal-model simulator to run in quasipolynomial (as opposed to polynomial) time. Quasipolynomial simulation suffices to ensure security for most applications of multiparty computation. Furthermore, Lindell (FOCS '03, TCC' 04) recently showed that such a protocol is impossible to obtain under the more standard definition of polynomial-time simulation by an ideal adversary. Our construction is the first such protocol under reasonably standard cryptographic assumptions (i. e. , existence of a hash function collection that is collision resistent with respect to circuits of subexponential size, and existence of trapdoor permutations which are secure with respect to circuits of quasi-polynomial size). We introduce a new technique: "protocol condensing". That is, taking a protocol that has strong security properties but requires super-polynomial communication and computation, and then transforming it into a protocol with polynomial communication and computation, that still inherits the strong security properties of the original protocol. Our result is obtained by combining this technique with previous techniques of Canetti, Lindell, Ostrovsky, and Sahai (STOC '02) and Pass (STOC '04).

STOC Conference 2005 Conference Paper

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors

• Boaz Barak
• Guy Kindler
• Ronen Shaltiel
• Benny Sudakov
• Avi Wigderson

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2 - k in X . We say that X is a δ-source if its rate k ⁄ n is at least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministic extractors, dispersers and related objects. All work for any fixed rate δ>0. No previous explicit construction was known for either of these, for any δ‹1⁄2. The first two constitute major progress to very long-standing open problems. Bipartite Ramsey f 1 : (0,1) n ) 2 →0,1, such that for any two independent δ-sources X 1 , X 2 we have f 1 ( X 1 , X 2 ) = 0,1 This implies a new explicit construction of 2N -vertex bipartite graphs where no induced N δ by N δ subgraph is complete or empty. Multiple source extraction f 2 : (0,1 n ) 3 →0,1 such that for any three independent δ-sources X 1 , X 2 , X 3 we have that f 2 ( X 1 , X 2 , X 3 ) is ( o (1)-close to being) an unbiased random bit. Constant seed condenser 2 f 3 : n →(0,1 m ) c , such that for any δ-source X , one of the c output distributions f 3 ( X ) i , is a 0.9-source over 0,1 m . Here c is a constant depending only on δ. Subspace Ramsey f 4: 0,1 n →0,1 such that for any affine -δ-source 3 X we have f 4 ( X )= 0,1.

FOCS Conference 2004 Conference Paper

Extracting Randomness Using Few Independent Sources

• Boaz Barak
• Russell Impagliazzo
• Avi Wigderson

In this work we give the first deterministic extractors from a constant number of weak sources whose entropy rate is less than 1/2. Specifically, for every /spl delta/ > 0 we give an explicit construction for extracting randomness from a constant (depending polynomially on 1//spl delta/) number of distributions over {0, l}n, each having min-entropy /spl delta/n. These extractors output n bits, which are 2/sup -n/ close to uniform. This construction uses several results from additive number theory, and in particular a recent one by Bourgain, Katz and Tao (2003) and of Konyagin (2003). We also consider the related problem of constructing randomness dispersers. For any constant output length m, our dispersers use a constant number of identical distributions, each with min-entropy /spl Omega/(log n) and outputs every possible m-bit string with positive probability. The main tool we use is a variant of the "stepping-up lemma" used in establishing lower bound on the Ramsey number for hyper-graphs (Erdos and Hajnal, 1980).

FOCS Conference 2004 Conference Paper

Universally Composable Protocols with Relaxed Set-Up Assumptions

• Boaz Barak
• Ran Canetti
• Jesper Buus Nielsen
• Rafael Pass

A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.

FOCS Conference 2003 Conference Paper

Lower Bounds for Non-Black-Box Zero Knowledge

• Boaz Barak
• Yehuda Lindell
• Salil P. Vadhan

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.

FOCS Conference 2002 Conference Paper

Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model

• Boaz Barak

We present the first constant-round non-malleable commitment scheme and the first constant-round non-malleable zero-knowledge argument system, as defined by Dolev, Dwork and Naor (1991). Previous constructions either used a non-constant number of rounds, or were only secure under stronger setup assumptions. An example of such an assumption is the shared random string model where we assume all parties have access to a reference string that was chosen uniformly at random by a trusted dealer. We obtain these results by defining an adequate notion of non-malleable coin-tossing, and presenting a constant-round protocol that satisfies it. This protocol allows us to transform protocols that are non-malleable in (a modified notion of) the shared random string model into protocols that are non-malleable in the plain model (without any trusted dealer or setup assumptions). Observing that known constructions of a non-interactive non-malleable zero-knowledge argument systems in the shared random string model (De Santis et. al. , 2001) are in fact non-malleable in the modified model, and combining them with our coin-tossing protocol we obtain the results mentioned above. The techniques we use are different from those used in previous constructions of non-malleable protocols. In particular our protocol uses diagonalization and a non-black-box proof of security (in a sense similar to Barak's zero-knowledge argument (2001)).

STOC Conference 2002 Conference Paper

Strict polynomial-time in simulation and extraction

• Boaz Barak
• Yehuda Lindell

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge (for NP ), one had to allow simulators and knowledge-extractors to run in time which is only polynomial on the average (i.e., expected polynomial time). Whether or not allowing expected polynomial-time is necessary for obtaining constant-round zero-knowledge proofs and proofs of knowledge, has been posed as an important open question. This question is interesting not only for its theoretical ramifications, but also because expected polynomial time simulation is not closed under composition. Therefore, in some cases security is not maintained when a protocol that utilizes expected polynomial time simulation (or extraction) is used as a part of a larger protocol.A partial answer to the question of the necessity (or non-necessity) of expected polynomial-time was provided recently by Barak, who gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) polynomial-time simulator. His was also the first protocol that is not black-box zero-knowledge. That is, the simulator in his protocol utilizes the description of the code of the verifier in an essential way.In this paper, we completely resolve the question of expected polynomial-time in zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors . As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and uses the code of the prover in an essential way.On the negative side, we show that non-black-box techniques are essential to both strict polynomial-time simulation and extraction. That is, we show that no constant-round zero-knowledge argument (or proof) can have a strict polynomial-time black-box simulator. Similarly, we show that no constant-round zero-knowledge argument (or proof) of knowledge can have a strict polynomial-time black-box knowledge extractor. Thus, for constant-round black-box zero-knowledge arguments (resp., arguments of knowledge), it is imperative that the simulator (resp., extractor) be allowed to run in expected polynomial-time.

FOCS Conference 2001 Conference Paper

How to Go Beyond the Black-Box Simulation Barrier

• Boaz Barak

The simulation paradigm is central to cryptography. A simulator is an algorithm that tries to simulate the interaction of the adversary with an honest party, without knowing the private input of this honest party. Almost all known simulators use the adversary's algorithm as a black-box. We present the first constructions of non-black-box simulators. Using these new non-black-box techniques, we obtain several results that were previously proven to be impossible to obtain using black-box simulators. Specifically, assuming the existence of collision resistent hash functions, we construct a new zero-knowledge argument system for NP that satisfies the following properties: 1. This system has a constant number of rounds with negligible soundness error. 2. It remains zero knowledge even when composed concurrently n times, where n is the security parameter. Simultaneously obtaining 1 and 2 has been recently proven to be impossible to achieve using black-box simulators. 3. It is an Arthur-Merlin (public coins) protocol. Simultaneously obtaining 1 and 3 was known to be impossible to achieve with a black-box simulator. 4. It has a simulator that runs in strict polynomial time, rather than in expected polynomial time. All previously known constant-round, negligible-error zero-knowledge arguments utilized expected polynomial-time simulators.

FOCS Conference 2001 Conference Paper

Resettably-Sound Zero-Knowledge and its Applications

• Boaz Barak
• Oded Goldreich 0001
• Shafi Goldwasser
• Yehuda Lindell

Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. We show that resettably-sound zero-knowledge arguments for NP exist if collision-free hash functions exist. In contrast, resettably-sound zero-knowledge proofs are possible only for languages in P/poly. We present two applications of resettably-sound zero-knowledge arguments. First, we construct resettable zero-knowledge arguments of knowledge for NP, using a natural relaxation of the definition of arguments (and proofs) of knowledge. We note that, under the standard definition of proof of knowledge, it is impossible to obtain resettable zero-knowledge arguments of knowledge for languages outside BPP. Second, we construct a constant-round resettable zero-knowledge argument for NP in the public-key model, under the assumption that collision-free hash functions exist. This improves upon the sub-exponential hardness assumption required by previous constructions. We emphasize that our results use non-black-box zero-knowledge simulations. Indeed, we show that some of the results are impossible to achieve using black-box simulations. In particular, only languages in BPP have resettably-sound arguments that are zero-knowledge with respect to black-box simulation.