Multiaccuracy and multicalibration are multi-group fairness notions for prediction that have found numerous applications in learning and computational complexity [HKRR18]. They can be achieved from a single learning primitive: weak agnostic learning. A line of work starting from [GKR+22] has shown that multicalibration implies a very strong form of learning. Here we investigate the power of multiaccuracy as a learning primitive, both with and without the additional assumption of calibration. We find that multiaccuracy in itself is rather weak, but that the addition of global calibration (this notion is called calibrated multiaccuracy) boosts its power substantially, enough to recover implications that were previously known only assuming the stronger notion of multicalibration. We give evidence that multiaccuracy might not be as powerful as standard weak agnostic learning, by showing that there is no way to post-process a multiaccurate predictor to get a weak learner, even assuming the best hypothesis has correlation 1/2. Rather, we show that it yields a restricted form of weak agnostic learning, which requires some concept in the class to have correlation greater than 1/2 with the labels. However, by also requiring the predictor to be calibrated, we recover not just weak, but strong agnostic learning. A similar picture emerges when we consider the derivation of hardcore measures from predictors satisfying multigroup fairness notions [TTV09], [CDV24]. On the one hand, while multiaccuracy only yields hardcore measures of density half the optimal, we show that (a weighted version of) calibrated multiaccuracy achieves optimal density. Our results yield new insights into the complementary roles played by multiaccuracy and calibration in each setting. They shed light on why multiaccuracy and global calibration, although not particularly powerful by themselves, together yield considerably stronger notions.

We introduce "representative generation," extending the theoretical framework for generation proposed by Kleinberg et al. (2024) and formalized by Li et al. (2024), to additionally address diversity and bias concerns in generative models. Our notion requires outputs of a generative model to proportionally represent groups of interest from the training data. We characterize representative uniform and non-uniform generation, introducing the “group closure dimension” as a key combinatorial quantity. For representative generation in the limit, we analyze both information-theoretic and computational aspects, demonstrating feasibility for countably infinite hypothesis classes and collections of groups under certain conditions, but proving a negative result for computability using only membership queries. This contrasts with Kleinberg et al.’s (2024) positive results for standard generation in the limit. Our findings provide a rigorous foundation for developing more diverse and representative generative models.

While modern explanation methods have been shown to be inconsistent and contradictory, the explainability of black-box models nevertheless remains desirable. When the role of explanations extends from understanding models to aiding decision making, the semantics of explanations is not always fully understood – to what extent do explanations ``explain” a decision and to what extent do they merely advocate for a decision? Can we help humans gain insights from explanations accompanying correct predictions and not over-rely on incorrect predictions advocated for by explanations? With this perspective in mind, we introduce the notion of dissenting explanations: conflicting predictions with accompanying explanations. We first explore the advantage of dissenting explanations in the setting of model multiplicity, where multiple models with similar performance may have different predictions. Through a human study on the task of identifying deceptive reviews, we demonstrate that dissenting explanations reduce overreliance on model predictions, without reducing overall accuracy. Motivated by the utility of dissenting explanations we present both global and local methods for their generation.

A recent line of work has shown a surprising connection between multicalibration, a multi- group fairness notion, and omniprediction, a learning paradigm that provides simultaneous loss minimization guarantees for a large family of loss functions [20, 19, 21, 18]. Prior work studies omniprediction in the batch setting. We initiate the study of omniprediction in the online adversarial setting. Although there exist algorithms for obtaining notions of multicalibration in the online adversarial setting [23], unlike batch algorithms, they work only for small finite classes of benchmark functions F, because they require enumerating every function f ∈ F at every round. In contrast, omniprediction is most interesting for learning theoretic hypothesis classes F, which are generally continuously (or at least exponentially) large.

This work initiates the systematic study of explicit distributions that are indistinguishable from a single exponential-size combinatorial object. In this we extend the work of Goldreich, Goldwasser and Nussboim (SICOMP 2010) that focused on the implementation of huge objects that are indistinguishable from the uniform distribution, satisfying some global properties (which they coined truthfulness). Indistinguishability from a single object is motivated by the study of generative models in learning theory and regularity lemmas in graph theory. Problems that are well understood in the setting of pseudorandomness present significant challenges and at times are impossible when considering generative models of huge objects. We demonstrate the versatility of this study by providing a learning algorithm for huge indistinguishable objects in several natural settings including: dense functions and graphs with a truthfulness requirement on the number of ones in the function or edges in the graphs, and a version of the weak regularity lemma for sparse graphs that satisfy some global properties. These and other results generalize basic pseudorandom objects as well as notions introduced in algorithmic fairness. The results rely on notions and techniques from a variety of areas including learning theory, complexity theory, cryptography, and game theory.

The notion of omnipredictors (Gopalan, Kalai, Reingold, Sharan and Wieder ITCS 2022), suggested a new paradigm for loss minimization. Rather than learning a predictor based on a known loss function, omnipredictors can easily be post-processed to minimize any one of a rich family of loss functions compared with the loss of hypotheses in a class $\mathcal C$. It has been shown that such omnipredictors exist and are implied (for all convex and Lipschitz loss functions) by the notion of multicalibration from the algorithmic fairness literature. In this paper, we introduce omnipredictors for constrained optimization and study their complexity and implications. The notion that we introduce allows the learner to be unaware of the loss function that will be later assigned as well as the constraints that will be later imposed, as long as the subpopulations that are used to define these constraints are known. We show how to obtain omnipredictors for constrained optimization problems, relying on appropriate variants of multicalibration. We also investigate the implications of this notion when the constraints used are so-called group fairness notions.

We present a new perspective on loss minimization and the recent notion of Omniprediction through the lens of Outcome Indistingusihability. For a collection of losses and hypothesis class, omniprediction requires that a predictor provide a loss-minimization guarantee simultaneously for every loss in the collection compared to the best (loss-specific) hypothesis in the class. We present a generic template to learn predictors satisfying a guarantee we call Loss Outcome Indistinguishability. For a set of statistical tests--based on a collection of losses and hypothesis class--a predictor is Loss OI if it is indistinguishable (according to the tests) from Nature's true probabilities over outcomes. By design, Loss OI implies omniprediction in a direct and intuitive manner. We simplify Loss OI further, decomposing it into a calibration condition plus multiaccuracy for a class of functions derived from the loss and hypothesis classes. By careful analysis of this class, we give efficient constructions of omnipredictors for interesting classes of loss functions, including non-convex losses. This decomposition highlights the utility of a new multi-group fairness notion that we call calibrated multiaccuracy, which lies in between multiaccuracy and multicalibration. We show that calibrated multiaccuracy implies Loss OI for the important set of convex losses arising from Generalized Linear Models, without requiring full multicalibration. For such losses, we show an equivalence between our computational notion of Loss OI and a geometric notion of indistinguishability, formulated as Pythagorean theorems in the associated Bregman divergence. We give an efficient algorithm for calibrated multiaccuracy with computational complexity comparable to that of multiaccuracy. In all, calibrated multiaccuracy offers an interesting tradeoff point between efficiency and generality in the omniprediction landscape.

We introduce and study the notion of Swap Agnostic Learning. The problem can be phrased as a game between a *predictor* and an *adversary*: first, the predictor selects a hypothesis $h$; then, the adversary plays in response, and for each level set of the predictor, selects a loss-minimizing hypothesis $c_v \in \mathcal{C}$; the predictor wins if $h$ competes with the adaptive adversary's loss. Despite the strength of the adversary, our main result demonstrates the feasibility Swap Agnostic Learning for any convex loss. Somewhat surprisingly, the result follows by proving an *equivalence* between Swap Agnostic Learning and swap variants of the recent notions Omniprediction (ITCS'22) and Multicalibration (ICML'18). Beyond this equivalence, we establish further connections to the literature on Outcome Indistinguishability (STOC'20, ITCS'23), revealing a unified notion of OI that captures all existing notions of omniprediction and multicalibration.

Recently, Dwork et al. (STOC 2021) introduced Outcome Indistinguishability as a new desideratum for binary prediction tasks. Outcome Indistinguishability (OI) articulates the goals of prediction in the language of computational indistinguishability: a predictor is Outcome Indistinguishable if no computationally-bounded observer can distinguish Nature’s outcomes from outcomes that are generated based on the predictions. In this sense, OI suggests a generative model for binary outcomes that cannot be refuted given the empirical evidence and computational resources at hand. In this work, we extend Outcome Indistinguishability beyond Bernoulli, to outcomes that live in a large discrete or continuous domain. While the idea of OI for non-binary outcomes is natural for many applications, defining OI in generality is not simply a syntactic exercise. We introduce and study multiple definitions of OI—each with its own semantics—for predictors that completely specify each individuals’ outcome distributions, as well as predictors that only partially specify the outcome distributions through statistics, such as moments. With the definitions in place, we provide learning algorithms for producing OI generative outcome models for general random outcomes. Finally, we study the relation of Outcome Indistinguishability and Multicalibration of statistics (beyond the mean) and relate our findings to the recent work of Jung et al. (COLT 2021) on Moment Multicalibration. We find an equivalence between Outcome Indistinguishability and Multicalibration that is more subtle than in the binary case and sheds light on the techniques employed by Jung et al. to obtain Moment Multicalibration.

The ratio between the probability that two distributions assign to points in the domain are called importance weights or density ratios and they play a fundamental role in machine learning and information theory. However, there are strong lower bounds known for point-wise accurate estimation of density ratios, and most theoretical guarantees require strong assumptions about the distributions. We motivate the problem of seeking accuracy guarantees for the distribution of importance weights conditioned on sub-populations belonging to a family $\mathcal{C}$ of subsets of the domain. We formulate {\em sandwiching bounds} for sets: upper and lower bounds on the expected importance weight conditioned on a set; as a notion of set-wise accuracy for importance weights. We argue that they capture intuitive expectations about importance weights, and are not subject to the strong lower bounds for point-wise guarantees. We introduce the notion of multicalibrated partitions for a class $\mathcal{C}$, inspired by recent work on multi-calibration in supervised learning and show that the importance weights resulting from such partitions do satisfy sandwiching bounds. In contrast, we show that importance weights returned by popular algorithms in the literature may violate the sandwiching bounds. We present an efficient algorithm for constructing multi-calibrated partitions, given a weak agnostic learner for the class $\mathcal{C}$.

We give the first sample complexity characterizations for outcome indistinguishability, a theoretical framework of machine learning recently introduced by Dwork, Kim, Reingold, Rothblum, and Yona (STOC 2021). In outcome indistinguishability, the goal of the learner is to output a predictor that cannot be distinguished from the target predictor by a class $D$ of distinguishers examining the outcomes generated according to the predictors’ predictions. While outcome indistinguishability originated from the algorithmic fairness literature, it provides a flexible objective for machine learning even when fairness is not a consideration. In this work, we view outcome indistinguishability as a relaxation of PAC learning that allows us to achieve meaningful performance guarantees under data constraint. In the distribution-specific and realizable setting where the learner is given the data distribution together with a predictor class $P$ containing the target predictor, we show that the sample complexity of outcome indistinguishability is characterized by the metric entropy of $P$ w.r.t. the dual Minkowski norm defined by $D$, and equivalently by the metric entropy of $D$ w.r.t. the dual Minkowski norm defined by $P$. This equivalence makes an intriguing connection to the long-standing metric entropy duality conjecture in convex geometry. Our sample complexity characterization implies a variant of metric entropy duality, which we show is nearly tight. In the distribution-free setting, we focus on the case considered by Dwork et al. where $P$ contains all possible predictors, hence the sample complexity only depends on $D$. In this setting, we show that the sample complexity of outcome indistinguishability is characterized by the fat-shattering dimension of $D$. We also show a strong sample complexity separation between realizable and agnostic outcome indistinguishability in both the distribution-free and the distribution-specific settings. This is in contrast to distribution-free (resp. distribution-specific) PAC learning where the sample complexity in both the realizable and the agnostic settings can be characterized by the VC dimension (resp. metric entropy).

We study the problem of robustly estimating the mean of a $d$-dimensional distribution given $N$ examples, where most coordinates of every example may be missing and $\varepsilon N$ examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than $\varepsilon N$ examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time $\widetilde O(Nd)$. Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting.

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

Prediction algorithms assign numbers to individuals that are popularly understood as individual “probabilities”—what is the probability of 5-year survival after cancer diagnosis?—and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are Outcome Indistinguishable (OI) yield a generative model for outcomes that cannot be efficiently refuted on the basis of the real-life observations produced by .

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

The celebrated ${\sf IP}={\sf PSPACE}$ theorem [Lund, Fortnow, Karloff, and Nisan, J. ACM, 39 (1992), pp. 859--868; Shamir, J. ACM, 39 (1992), pp. 869--877] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an exponential-time (polynomial-space complete) prover. In this paper, we study the power of more efficient interactive proof systems. Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sublinear), and (3) the interaction consists of only a constant number of communication rounds. Prior to this work, very little was known about the power of efficient, constant-round interactive proofs (rather than arguments). This result represents significant progress on the round complexity of interactive proofs (even if we ignore the running time of the honest prover) and on the expressive power of interactive proofs with polynomial-time honest prover (even if we ignore the round complexity). This result has several applications, and in particular it can be used for verifiable delegation of computation. Our construction leverages several new notions of interactive proofs, which may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs ($\mathsf{PCIP}$s), where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of $\mathsf{PCIP}$s). An equivalent notion to $\mathsf{PCIP}$s, called interactive oracle proofs, was recently introduced in an independent work of Ben-Sasson, Chiesa, and Sponcer [Proceedings of TCC, 2016, pp. 31--60].

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.

Many selection procedures involve ordering candidates according to their qualifications. For example, a university might order applicants according to a perceived probability of graduation within four years, and then select the top 1000 applicants. In this work, we address the problem of ranking members of a population according to their "probability" of success, based on a training set of historical binary outcome data (e.g., graduated in four years or not). We show how to obtain rankings that satisfy a number of desirable accuracy and fairness criteria, despite the coarseness of the training data. As the task of ranking is global (the rank of every individual depends not only on their own qualifications, but also on every other individuals' qualifications) ranking is more subtle and vulnerable to manipulation than standard prediction tasks. Towards mitigating unfair discrimination caused by inaccuracies in rankings, we develop two parallel definitions of evidence-based rankings. The first definition relies on a semantic notion of domination-compatibility: if the training data suggest that members of a set S are more qualified (on average) than the members of T, then a ranking that favors T over S (i.e. where T dominates S) is blatantly inconsistent with the evidence, and likely to be discriminatory. The definition asks for domination-compatibility, not just for a pair of sets, but rather for every pair of sets from a rich collection C of subpopulations. The second definition aims at precluding even more general forms of discrimination; this notion of evidence-consistency requires that the ranking must be justified on the basis of consistency with the expectations for every set in the collection C. Somewhat surprisingly, while evidence-consistency is a strictly stronger notion than domination-compatibility when the collection C is predefined, the two notions are equivalent when the collection C may depend on the ranking in question.

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any l-query protocol can be revealed by an O(l^2)-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol of Merkle [CACM '78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly l^2 queries, the honest parties need to exchange Omega(l) bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments. Understanding the communication complexity of protocols whose security is proven (in the random-oracle model) is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.

We construct pseudorandom generators of seed length Õ(log(n)· log(1/є)) that є-fool ordered read-once branching programs (ROBPs) of width 3 and length n. For unordered ROBPs, we construct pseudorandom generators with seed length Õ(log(n) · poly(1/є)). This is the first improvement for pseudorandom generators fooling width 3 ROBPs since the work of Nisan [Combinatorica, 1992].

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by simply having the prover send the k NP witnesses, but this involves a lot of communication. Can interaction help? In particular, is it possible to construct interactive proofs for this task whose communication grows sub-linearly with k? Our main result is such an interactive proof for verifying the correctness of any k UP statements (i.e., NP statements that have a unique witness). The proof-system uses only a constant number of rounds and the communication complexity is k^delta * poly(m), where delta>0 is an arbitrarily small constant, m is the length of a single witness, and the poly term refers to a fixed polynomial that only depends on the language and not on delta. The (honest) prover strategy can be implemented in polynomial-time given access to the k (unique) witnesses. Our proof leverages "interactive witness verification" (IWV), a new type of proof-system that may be of independent interest. An IWV is a proof-system in which the verifier needs to verify the correctness of an NP statement using: (i) a sublinear number of queries to an alleged NP witness, and (ii) a short interaction with a powerful but untrusted prover. In contrast to the setting of PCPs and Interactive PCPs, here the verifier only has access to the raw NP witness, rather than some encoding thereof.

We develop and study multicalibration as a new measure of fairness in machine learning that aims to mitigate inadvertent or malicious discrimination that is introduced at training time (even from ground truth data). Multicalibration guarantees meaningful (calibrated) predictions for every subpopulation that can be identified within a specified class of computations. The specified class can be quite rich; in particular, it can contain many overlapping subgroups of a protected group. We demonstrate that in many settings this strong notion of protection from discrimination is provably attainable and aligned with the goal of obtaining accurate predictions. Along the way, we present algorithms for learning a multicalibrated predictor, study the computational complexity of this task, and illustrate tight connections to the agnostic learning model.

We study the problem of fair classification within the versatile framework of Dwork et al. [ITCS '12], which assumes the existence of a metric that measures similarity between pairs of individuals. Unlike earlier work, we do not assume that the entire metric is known to the learning algorithm; instead, the learner can query this arbitrary metric a bounded number of times. We propose a new notion of fairness called metric multifairness and show how to achieve this notion in our setting. Metric multifairness is parameterized by a similarity metric d on pairs of individuals to classify and a rich collection C of (possibly overlapping) "comparison sets" over pairs of individuals. At a high level, metric multifairness guarantees that similar subpopulations are treated similarly, as long as these subpopulations are identified within the class C.

We present an explicit pseudorandom generator with seed length Õ((logn)w+1) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impagliazzo, Meka and Zuckerman (FOCS’12) where they required seed length n1/2+o(1).

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

A crowdsourcing project is usually comprised of many unit tasks known as Human Intelligence Tasks (HITs). As answers to each HIT varies between workers, each HIT is often contracted to more than one worker to obtain a reliable and consistent enough answer. When implementing a project, an important design decision is how to formulate HITs and how to aggregate workers' answers. These decisions have strong impact on the quality of results and cost of elicitation process. One way to design an efficient elicitation procedure is to use adaptive stopping rules, which allows terminating the elicitation process as soon as a high quality result is guaranteed.

The celebrated IP=PSPACE Theorem of Lund et-al. (J.ACM 1992) and Shamir (J.ACM 1992), allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an exponential-time (polynomial-space complete) prover. In this paper, we study the power of more efficient interactive proof systems.

Online groups, including chat groups and forums, are becoming important avenues for gathering and exchanging information ranging from troubleshooting devices, to sharing experiences, to finding medical information and advice. Thus, issues about the health and stability of these groups are of particular interest to both industry and academia. In this paper we conduct a large scale study with the objectives of first, characterizing essential aspects of the interactions between the participants of such groups and second, characterizing how the nature of these interactions relate to the health of the groups. Specifically, we concentrate on Twitter Discussion Groups (TDGs), self-organized groups that meet on Twitter by agreeing on a hashtag, date and time. These groups have repeated, real-time meetings and are a rising phenomenon on Twitter. We examine the interactions in these groups in terms of the social equality and mobility of the exchange of attention between participants, according to the @mention convention on Twitter. We estimate the health of a group by measuring the retention rate of participants and the change in the number of meetings over time. We find that social equality and mobility are correlated, and that equality and mobility are related to a group's health. In fact, equality and mobility are as predictive of a group's health as some prior characteristics used to predict health of other online groups. Our findings are based on studying 100 thousand sessions of over two thousand discussion groups over the period of June 2012 to June 2013. These finding are not only relevant to stakeholders interested in maintaining these groups, but to researchers and academics interested in understanding the behavior of participants in online discussions. We also find the parallel with findings on the relationship between economic mobility and equality and health indicators in real-world nations striking and thought-provoking.

Overfitting is the bane of data analysts, even when data are plentiful. Formal approaches to understanding this problem focus on statistical inference and generalization of individual analysis procedures. Yet the practice of data analysis is an inherently interactive and adaptive process: new analyses and hypotheses are proposed after seeing the results of previous ones, parameters are tuned on the basis of obtained results, and datasets are shared and reused. An investigation of this gap has recently been initiated by the authors in (Dwork et al., 2014), where we focused on the problem of estimating expectations of adaptively chosen functions.In this paper, we give a simple and practical method for reusing a holdout (or testing) set to validate the accuracy of hypotheses produced by a learning algorithm operating on a training set. Reusing a holdout set adaptively multiple times can easily lead to overfitting to the holdout set itself. We give an algorithm that enables the validation of a large number of adaptively chosen hypotheses, while provably avoiding overfitting. We illustrate the advantages of our algorithm over the standard use of the holdout set via a simple synthetic experiment.We also formalize and address the general problem of data reuse in adaptive data analysis. We show how the differential-privacy based approach in (Dwork et al., 2014) is applicable much more broadly to adaptive data analysis. We then show that a simple approach based on description length can also be used to give guarantees of statistical validity in adaptive settings. Finally, we demonstrate that these incomparable approaches can be unified via the notion of approximate max-information that we introduce. This, in particular, allows the preservation of statistical validity guarantees even when an analyst adaptively composes algorithms which have guarantees based on either of the two approaches.

A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries, from the use of sophisticated validation techniques, to deep statistical methods for controlling the false discovery rate in multiple hypothesis testing. However, there is a fundamental disconnect between the theoretical results and the practice of data analysis: the theory of statistical inference assumes a fixed collection of hypotheses to be tested, or learning algorithms to be applied, selected non-adaptively before the data are gathered, whereas in practice data is shared and reused with hypotheses and new analyses being generated on the basis of data exploration and the outcomes of previous analyses.

We study the round and communication complexities of various cryptographic protocols. We give tight lower bounds on the round and communication complexities of any fully black-box reduction of a statistically hiding commitment scheme from one-way permutations and from trapdoor permutations. As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon [Advances in Cryptology---EUROCRYPT'98, Lecture Notes in Comput. Sci. 1403, Springer, Berlin, 1998, pp. 334--345] to the setting of interactive protocols and the reconstruction paradigm of Gennaro and Trevisan [Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2000, pp. 305--313].

Hashing is one of the main techniques in data processing and algorithm design for very large data sets. While random hash functions satisfy most desirable properties, it is often too expensive to store a fully random hash function. Motivated by this, much attention has been given to designing small families of hash functions suitable for various applications. In this work, we study the question of designing space-efficient hash families H = {h:[U] -> [N]} with the natural property of 'covering': H is said to be covering if any set of Omega(N log N) distinct items from the universe (the "coupon-collector limit") are hashed to cover all N bins by most hash functions in H. We give an explicit covering family H of size poly(N) (which is optimal), so that hash functions in H can be specified efficiently by O(log N) bits. We build covering hash functions by drawing a connection to "dispersers", which are quite well-studied and have a variety of applications themselves. We in fact need strong dispersers and we give new constructions of strong dispersers which may be of independent interest. Specifically, we construct strong dispersers with optimal entropy loss in the high min-entropy, but very small error (poly(n)/2^n for n bit sources) regimes. We also provide a strong disperser construction with constant error but for any min-entropy. Our constructions achieve these by using part of the source to replace seed from previous non-strong constructions in surprising ways. In doing so, we take two of the few constructions of dispersers with parameters better than known extractors and make them strong.

Interactive hashing, introduced by Naor, Ostrovsky, Venkatesan, and Yung (J. Cryptol. 11(2):87–108, 1998 ), plays an important role in many cryptographic protocols. In particular, interactive hashing is a major component in all known constructions of statistically hiding commitment schemes and of statistical zero-knowledge arguments based on general one-way permutations/functions. Interactive hashing with respect to a one-way function f is a two-party protocol that enables a sender who knows y = f ( x ) to transfer a random hash z = h ( y ) to a receiver such that the sender is committed to y : the sender cannot come up with x and x ′ such that f ( x )≠ f ( x ′), but h ( f ( x ))= h ( f ( x ′))= z . Specifically, if f is a permutation and h is a two-to-one hash function, then the receiver does not learn which of the two preimages { y , y ′}= h −1 ( z ) is the one the sender can invert with respect to f . This paper reexamines the notion of interactive hashing, and proves the security of a variant of the Naor et al. protocol, which yields a more versatile interactive hashing theorem. When applying our new proof to (an equivalent variant of) the Naor et al. protocol, we get an alternative proof for this protocol that seems simpler and more intuitive than the original one, and achieves better parameters (in terms of how security preserving the reduction is).

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, $\epsilon$-biased spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n\rightarrow\{0,1\}$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n\subseteq[m]$ and a symmetric function $h:\{0,1\}^n\rightarrow\{0,1\}$ such that $f(x_1,\ldots,x_n)=h(1_{A_1}(x_1),\ldots,1_{A_n}(x_n))$. Our generator uses seed-length $O(\log m+\log n+\log^2(1/\varepsilon))$ to get error $\varepsilon$. When $m=2$, this gives the first generator of seed-length $O(\log n)$ that fools all weight-based tests, meaning that the distribution of the weight of any subset is $\varepsilon$-close to the appropriate binomial distribution in statistical distance. Along the way, we give a generator for combinatorial rectangles with seed-length $O(\log^{3/2}n)$ and error $1/\mathrm{poly}(n)$, matching Lu's bound from ICALP 1998. For our proof we give a simple lemma which allows us to convert closeness in Kolmogorov (cdf) distance to closeness in statistical distance. As a corollary of our technique, we give an alternative proof of a powerful variant of the classical central limit theorem showing convergence in statistical distance, instead of the usual Kolmogorov distance.

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 give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a DNF or CNF. Given a DNF(or CNF) f on n variables and poly(n) terms, we give a deterministic nÕ((log log n)2)time algorithm that computes an (additive) ε approximation to the fraction of satisfying assignments of f for ε = 1/poly(logn). The previous best algorithm due to Luby and Velickovic from nearly two decades ago had a run-time of nexp(O(√log log n)). A crucial ingredient in our algorithm is a structural result which allows us to sparsify any small-width DNFformula. It says that any width w DNF(irrespective of the number of terms) can be ε-approximated by a width w DNFwith at most (w log(1/ε))O(w)terms. Further, our approximating DNFs have an additional “sandwiching” property which is crucial for applications to derandomization. We believe the sparsification result to be of independent interest and use it to show a weak derandomization of the switching lemma wherein the random restrictions need only have limited independence.

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 study fairness in classification, where individuals are classified, e.g., admitted to a university, and the goal is to prevent discrimination against individuals based on their membership in some group, while maintaining utility for the classifier (the university). The main conceptual contribution of this paper is a framework for fair classification comprising (1) a (hypothetical) task-specific metric for determining the degree to which individuals are similar with respect to the classification task at hand; (2) an algorithm for maximizing utility subject to the fairness constraint, that similar individuals are treated similarly. We also present an adaptation of our approach to achieve the complementary goal of "fair affirmative action," which guarantees statistical parity (i.e., the demographics of the set of individuals receiving any classification are the same as the demographics of the underlying population), while treating similar individuals as similarly as possible. Finally, we discuss the relationship of fairness to privacy: when fairness implies privacy, and how tools developed in the context of differential privacy may be applied to fairness.

A fundamental fact in the analysis of randomized algorithms is that when n balls are hashed into n bins independently and uniformly at random, with high probability each bin contains at most O(log n/ log log n) balls. In various applications, however, the assumption that a truly random hash function is available is not always valid, and explicit functions are required. In this paper we study the size of families (or, equivalently, the description length of their functions) that guarantee a maximal load of O(log n/ log log n) with high probability, as well as the evaluation time of their functions. Whereas such functions must be described using Omega(log n) bits, the best upper bound was formerly O(log2n/ log log n) bits, which is attained by O(log n/ log log n)-wise independent functions. Traditional constructions of the latter offer an evaluation time of O(log n/ log log n), which according to Siegel's lower bound [FOCS '89] can be reduced only at the cost of significantly increasing the description length. We construct two families that guarantee a maximal load of O(log n/ log log n) with high probability. Our constructions are based on two different approaches, and exhibit different trade-offs between the description length and the evaluation time. The first construction shows that O(log n/ log log n)-wise independence can in fact be replaced by "gradually increasing independence", resulting in functions that are described using O(log n log log n) bits and evaluated in time O(log n log log n). The second construction is based on derandomization techniques for space-bounded computations combined with a tailored construction of a pseudorandom generator, resulting in functions that are described using O(log3/2n) bits and evaluated in time O(√(log n)). The latter can be compared to Siegel's lower bound stating that O(log n / log log n)-wise independent functions that are evaluated in time O(√(log n)) must be described using Ω(2√(log n)) bits.

No abstract available.

We consider two of the most fundamental theorems in cryptography. The first, due to Håstad et al. [SIAM J. Comput., 28 (1999), pp. 1364–1396] is that pseudorandom generators can be constructed from any one-way function. The second, due to Yao [Proceedings of the $23$rd Annual Symposium on Foundations of Computer Science (FOCS), 1982, pp. 80–91], states that the existence of weak one-way functions implies the existence of full-fledged one-way functions. These powerful plausibility results shape our understanding of hardness and randomness in cryptography, but unfortunately their proofs are not as tight (i.e., security preserving) as one may desire. This work revisits a technique that we call the randomized iterate, introduced by Goldreich, Krawczyk, and Luby [SIAM J. Comput., 22 (1993), pp. 1163–1175]. This technique was used by Goldreich, Krawczyk, and Luby [SIAM J. Comput., 22 (1993), pp. 1163–1175] to give a construction of pseudorandom generators from regular one-way functions. We simplify and strengthen this technique in order to obtain a similar construction, where the seed length of the resulting generators is as short as $\Theta(n \log n)$ (rather than $\Theta(n^3)$ achieved by Goldreich, Krawczyk, and Luby [SIAM J. Comput., 22 (1993), pp. 1163–1175]). Our technique has the potential of implying seed length $\Theta(n)$, and the only bottleneck for such a result are the parameters of current generators against bounded-space computations. We give a construction with similar parameters for security amplification of regular one-way functions. This improves upon the construction of Goldreich et al. [Proceedings of the $31$st Annual Symposium on Foundations of Computer Science, (FOCS), 1990, pp. 318–326] in that the construction does not need to “know" the regularity parameter of the functions (in terms of security, the two reductions are incomparable). In addition, we use the randomized iterate to show a construction of a pseudorandom generator based on an exponentially hard one-way function that has a seed length of only $\Theta(n^2)$. This improves a recent result of Holenstein [Proceedings of the Theory of Cryptography, Third Theory of Cryptography Conference (TCC), 2006] that shows a construction with seed length $\Theta(n^5)$ based on such one-way functions. Finally, we show that the randomized iterate may even be useful in the general context of Håstad et al. [SIAM J. Comput., 28 (1999), pp. 1364–1396]. In particular, we use the randomized iterate to replace the basic building block of the Håstad et al. [SIAM J. Comput., 28 (1999), pp. 1364–1396] construction. Interestingly, this modification improves efficiency by an $\Theta(n^2)$ factor and reduces the seed length to $\Theta(n^7)$ (which also implies improvement in the security of the construction).

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

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.

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

A Nash equilibrium is an optimal strategy for each player under the assumption that others play according to their respective Nash strategies. In the presence of irrational

We present a deterministic , log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log 4/3 (⋅) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As undirected st-connectivity is complete for the class of problems solvable by symmetric, nondeterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov (STOC 2005) has presented an O (log n log log n )-space, deterministic algorithm for undirected st-connectivity. Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labeling and log-space constructible universal-exploration sequences for general graphs.

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 study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from oneway permutations, and even front trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other ctyptographicprotocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.

We give a construction of statistically-hiding commitment schemes (ones where the hiding propertyholds information theoretically), based on the minimal cryptographic assumption that one-way functions exist. Our construction employs two-phase commitment schemes, recently constructed by Nguyen, Ong and Vadhan (FOCS '06), and universal one-way hash functions introduced and constructedby Naor and Yung (STOC '89) and Rompel (STOC '90).

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

In this work we look back into the proof of the PCP (probabilistically checkable proofs) theorem, with the goal of finding new proofs that are “more combinatorial” and arguably simpler. For that we introduce the notion of an assignment tester, which is a strengthening of the standard PCP verifier, in the following sense. Given a statement and an alleged proof for it, while the PCP verifier checks correctness of the statement, the assignment tester checks correctness of the statement and the proof. This notion enables composition that is truly modular; i.e., one can compose two assignment testers without any assumptions on how they are constructed. A related notion called PCPs of proximity was independently introduced in [E. Ben‐Sasson et al., Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, 2004, ACM, New York, 2004, pp. 1–10]. We provide a toolkit of (nontrivial) generic transformations on assignment testers. These transformations may be interesting in their own right, and allow us to present the following two main results: 1. A new proof of the PCP theorem. This proof relies on a rather weak assignment tester given as a “black box.” From this, we construct combinatorially the full PCP. An important component of this proof is a new combinatorial aggregation technique (i.e., a new transformation that allows the verifier to read fewer, though possibly longer, “pieces” of the proof). An implementation of the black‐box tester can be obtained from the algebraic proof techniques that already appear in [L. Babai et al., Proceedings of the 23rd ACM Symposium on Theory of Computing, New Orleans, LA, 1991, ACM, New York, 1991, pp. 21–31; U. Feige et al., J. ACM, 43 (1996), pp. 268–292]. 2. Our second construction is a “standalone” combinatorial construction showing $NP \subseteq PCP[polylog, 1]$. This implies, for example, that approximating max‐SAT is quasi‐NP‐hard. This construction relies on a transformation that makes an assignment tester “oblivious,” so that the proof locations read are independent of the statement that is being proven. This eliminates, in a rather surprising manner, the need for aggregation in a crucial point in the proof.

Extractors (as defined by Nisan and Zuckerman) are procedures that use a small number of truly random bits (called the seed) to extract many (almost) truly random bits from arbitrary distributions as long as distributions have sufficient (min)-entropy. A natural weakening of an extractor is a condenser, whose output distribution has a higher entropy rate than the input distribution (without losing much of the initial entropy). An extractor can be viewed as an ultimate condenser because it outputs a distribution with the maximal entropy rate. In this paper we construct explicit condensers with short seed length. The condenser constructions combine (variants of or more efficient versions of) ideas from several works, including the block extraction scheme of [N. Nisan and D. Zuckerman, J. Comput. System Sci., 52 (1996), pp. 43-52], the observation made in [A. Srinivasanand D. Zuckerman, SIAM J. Comput., 28 (1999), pp. 1433-1459; N. Nisan and A. Ta-Shma, J. Comput. System Sci., 58 (1999), pp. 148-173] that a failure of the block extraction scheme is also useful, the recursive "win-win" case analysis of [R. Impagliazzo, R. Shaltiel, and A. Wigderson, Near-optimal conversion of hardness into pseudo-randomness, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Los Alamitos, CA, 1999, pp. 181-190; R. Impagliazzo, R. Shaltiel, and A. Wigderson, Extractors and pseudo-random generators with optimal seed length, in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 1-10], and the error correction of random sources used in [L. Trevisan, J. ACM, 48 (2001), pp. 860-879]. As a by-product (via repeated iterating of condensers), we obtain new extractor constructions. The new extractors give significant qualitative improvements over previous ones for sources of arbitrary min-entropy; they are nearly optimal simultaneously in the two main parameters of seed length and output length. Specifically, our extractors can make any one of these two parameters optimal (up to a constant factor) only at a polylogarithmic loss in the other. Previous constructions require polynomial loss in both cases for general sources. We also give a simple reduction converting "standard" extractors (which are good for an average seed) into "strong" ones (which are good for most seeds), with essentially the same parameters. With this reduction, all the above improvements apply to strong extractors as well.

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3 obtained by Armoni, Ta-Shma, Wigderson and Zhou [9]. As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov [45] has presented an O(log n log log n)-space, deterministic algorithm for undirected st-connectivity.Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labelling and log-space constructible universal-exploration sequences for general graphs.

In this work, we look back into the proof of the PCP theorem, with the goal of finding new proofs that are "more combinatorial" and arguably simpler. For that, we introduce the notion of an assignment tester, which is a strengthening of the standard PCP verifier, in the following sense. Given a statement and an alleged proof for it, while the PCP verifier checks correctness of the statement, the assignment-tester checks correctness of the statement and the proof. This notion enables composition that is truly modular, i.e., one can compose two assignment-testers without any assumptions on how they are constructed. A related notion was independently introduced in (Ben-Sasson et. al. STOC 04). We provide a toolkit of (non-trivial) generic transformations on assignment testers. These transformations may be interesting in their own right, and allow us to present the following two main results: 1. The first is a new proof of the PCP theorem. This proof relies on a rather weak assignment tester given as a "black box". From this, we construct combinatorially the full PCP. An important component of this proof is a new combinatorial aggregation technique (i.e., a new transformation that allows the verifier to read fewer, though possibly longer, "pieces" of the proof). An implementation of the black-box tester can be obtained from the algebraic proof techniques that already appear in L. Babai et al., 1991 and U. Feige et al., 1991. Obtaining a combinatorial implementation of this tester would give a purely combinatorial proof for the PCP theorem, which we view as an interesting open problem. 2. Our second construction is a "standalone" combinatorial construction showing NP /spl sube/ PCP (S. Arora et al., 1998). This implies, for example, that approximating max-SAT is quasi-NP-hard. This construction relies on a transformation that makes an assignment tester "oblivious": so that the proof locations read are independent of the statement that is being proven. This eliminates, in a rather surprising manner, the need for aggregation in a crucial point in the proof.

A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols.The previous study of these questions was mainly conducted from an Information Theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.

We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that factoring (Blum integers) is hard while the other construction is pseudo-random if the decisional version of the Diffie--Hellman assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC 0 (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form " y = f s ( x )" and " y ≠ f s ( x )" given a commitment to a key s of a pseudo-random function f s .

We describe Just Fast Keying (JFK), a new key-exchange protocol, primarily designed for use in the IP security architecture. It is simple, efficient, and secure; we sketch a proof of the latter property. JFK also has a number of novel engineering parameters that permit a variety of tradeoffs, most notably the ability to balance the need for perfect forward secrecy against susceptibility to denial-of-service attacks.

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 prove that three apparently unrelated fundamental problems in distributed computing, cryptography, and complexity theory, are essentially the same problem. These three problems and brief descriptions of them follow. (1) The selective decommitment problem. An adversary is given commitments to a collection of messages, and the adversary can ask for some subset of the commitments to be opened. The question is whether seeing the decommitments to these open plaintexts allows the adversary to learn something unexpected about the plaintexts that are unopened. (2) The power of 3-round weak zero-knowledge arguments. The question is what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument. In particular, is there a language outside of BPP that has a 3-round public-coin weak zero-knowledge argument? (3) The Fiat-Shamir methodology. This is a method for converting a 3-round public-coin argument (viewed as an identification scheme) to a 1-round signature scheme. The method requires what we call a "magic function" that the signer applies to the first-round message of the argument to obtain a second-round message (queries from the verifier). An open question here is whether every 3-round public-coin argument for a language outside of BPP has a magic function.It follows easily from definitions that if a 3-round public-coin argument system is zero-knowledge in the standard (fairly strong) sense, then it has no magic function. We define a weakening of zero-knowledge such that zero-knowledge ⇒ no-magic-function still holds. For this weakened form of zero-knowledge, we give a partial converse: informally, if a 3-round public-coin argument system is not weakly zero-knowledge, then some form of magic is possible for this argument system. We obtain our definition of weak zero-knowledge by a sequence of weakenings of the standard definition, forming a hierarchy. Intermediate forms of zero-knowledge in this hierarchy are reasonable ones, and they may be useful in applications. Finally, we relate the selective decommitment problem to public-coin proof systems and arguments at an intermediate level of the hierarchy, and obtain several positive security results for selective decommitment.

We describe JFK, a new key exchange protocol, primarily designed for use in the IP Security Architecture. It is simple, efficient, and secure; we sketch a proof of the latter property. JFK also has a number of novel engineering parameters that permit a variety of trade-offs, most notably the ability to balance the need for perfect forward secrecy against susceptibility to denial-of-service attacks.

We prove (mostly tight) space lower bounds for "streaming" (or "on-line") computations of four fundamental combinatorial objects: error-correcting codes, universal hash functions, extractors, and dispersers. Streaming computations for these objects are motivated algorithmically by massive data set applications and complexity-theoretically by pseudorandomness and derandomization for space-bounded probabilistic algorithms. Our results reveal a surprising separation of extractors and dispersers in terms of the space required to compute them in the streaming model. While online extractors require space linear in their output length, we construct dispersers that are computable online with exponentially less space. We also present several explicit constructions of online extractors that match the lower bound. We show that online universal and almost-universal hash functions require space linear in their output length (this bound was known previously only for "pure" universal hash functions). Finally, we show that both online encoding and online decoding of error-correcting codes require space proportional to the product of the length of the encoded message and the code's relative minimum distance. Block encoding trivially matches the lower bounds for constant rate codes.

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.

The computational hardness of factoring integers is the most established assumption on which cryptographic primitives are based. This work presents an efficient construction of pseudorandom functions whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudorandom functions, where each evaluation requires only a (small) constant number of modular multiplications per output bit. This is substantially more efficient than any previous construction of pseudorandom functions based on factoring and matches (up to a constant factor) the efficiency of the best-known factoring-based pseudorandom bit generators.

We prove that, somewhat surprisingly, there is no black-box reduction of (poly-to-one) trapdoor functions to trapdoor predicates (equivalently, to public-key encryption schemes). Our proof follows the methodology that was introduced by R. Impagliazzo and S. Rudich (1989), although we use a new, weaker model of separation.

In this paper we study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i.e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multi-party computation), key agreement and trapdoor permutations. Our main results show that public-key encryption and oblivious transfer are incomparable under black-box reductions. These separations are tightly matched by our positive results where a restricted (strong) version of one primitive does imply the other primitive. We also show separations between oblivious transfer and key agreement. Finally, we conclude that neither oblivious transfer nor trapdoor predicates imply trapdoor permutations. Our techniques for showing negative results follow the oracle separations of R. Impagliazzo and S. Rudich (1989).

On an input probability distribution with some (min-)entropy an extractor outputs a distribution with a (near) maximum entropy rate (namely the uniform distribution). A natural weakening of this concept is a condenser, whose output distribution has a higher entropy rate than the input distribution (without losing much of the initial entropy). We construct efficient explicit condensers. The condenser constructions combine (variants or more efficient versions of) ideas from several works, including the block extraction scheme of Nisan and Zuckerman (1996), the observation made by Srinivasan and Zuckerman (1994) and Nisan and Ta-Schma (1999) that a failure of the block extraction scheme is also useful, the recursive "win-win" case analysis of Impagliazzo et al. (1999, 2000), and the error correction of random sources used by Trevisan (1999). As a natural byproduct, (via repeated iterating of condensers), we obtain new extractor constructions. The new extractors give significant qualitative improvements over previous ones for sources of arbitrary min-entropy; they are nearly optimal simultaneously in the main two parameters-seed length and output length. Specifically, our extractors can make any of these two parameters optimal (up to a constant factor), only at a poly-logarithmic loss in the other. Previous constructions require polynomial loss in both cases for general sources. We also give a simple reduction converting "standard" extractors (which are good for an average seed) to "strong " ones (which are good for mast seeds), with essentially the same parameters.

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

Article Pseudo-random functions and factoring (extended abstract) Share on Authors: Moni Naor Dept. of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel Dept. of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, IsraelView Profile , Omer Reingold AT&T Labs - Research, 180 Park Avenue, Bldg. 103, Florham Park, NJ AT&T Labs - Research, 180 Park Avenue, Bldg. 103, Florham Park, NJView Profile , Alon Rosen Dept. of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel Dept. of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, IsraelView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 11–20https://doi.org/10.1145/335305.335307Online:01 May 2000Publication History 15citation492DownloadsMetricsTotal Citations15Total Downloads492Last 12 Months2Last 6 weeks0 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

In this paper we show that three apparently unrelated problems are in fact very closely related. We sketch these problems at a high level. The selective decommitment problem first arose in a slightly different form, selective decryption, in the context of Byzantine agreement, no later than 1985. Instead of seeing encryptions of plaintexts the adversary is given commitments to the plaintexts. This problem is poorly understood even in strong-receiver commitments, which leak no information about the plaintext values information-theoretically. The second problem is in complexity theory: what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument (interactive proof in which the prover is polynomial-time bounded)? The Fiat-Shamir Methodology is cryptographic, and addresses a methodology suggested by Fiat and Shamir (1987) to construct a (non-interactive) signature scheme from any 3-round (not necessarily zero-knowledge) public-coin identification scheme.

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.

Let M be a logarithmic space Turing machine (or a polynomial width branching program) that uses up to k 2 p log n (read once) random bits. For a fixed input, let P i (S) be the probability (over the random string) that at time i the machine M is in state S, and assume that some weak estimation of the probabilities P i (S) is known or given or can be easily computed. We construct a logarithmic space pseudo-random generator that uses only logarithmic number of truly random bits and outputs a sequence of k bits that looks random to M . This means that a very weak estimation of the state probabilities of M is sufficient for a full derandomization of M and for constructing pseudo-random sequences for M . We have several applications of the main theorem, as stated within. To prove our theorem, we introduce the idea of recycling the state S of the machine M at time i as part of the random string for the same machine at later time. That is, we use the entropy of the random variable S in o...

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.

Probabilistic hash functions that hide all partial information on their input were recently introduced. This new cryptographic primitive can be regarded as a function that offers "perfect one-wayness", in the following sense: Having access to the function value on some input is equivalent to having access only to an oracle that answers "yes" if the correct input is queried, and answers "no" otherwise. Constructions of this primitive (originally called oracle hashing and here re-named perfectly one-way functions) were given based on certain strong variants of the Diffie-Hellman assumption. In this work we present several constructions of perfectly one-way functions; some constructions are based on claw-free permutation, and others are based on any oneway permutation. One of our constructions is simple and efficient to the point of being attractive from a practical point of view.

We describe efficient constructions for various cryptographic primitives (both in private-key and in public-key cryptography). We show these constructions to be at least as secure as the decisional version of the Diffie-Hellman assumption or as the assumption that factoring is hard. Our major result is a new construction of pseudo-random functions such that computing their value at any given point involves two multiple products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC/sup 0/ (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates) which has several interesting applications. The simple algebraic structure of the functions implies additional features. In particular, we show a zero-knowledge proof for statements of the form "y=f/sub s/(x)" and "y/spl ne/f(x)" given a commitment to a key s of a pseudo-random function f/sub s/.

Luby and Rackoff [21] showed a method for constructing a pseudo-random permutation from a pseudorandom function.The method is based on composing four (or three for weakened security) so called Feistel permutations, each of which requires the evaluation of a pseudo-random function.We reduce somewhat the complexity of the construction and simplify its proof of security by showing that two Feistel permutations are sufficient together with initial and final pair-wise independent permutations.The revised construction and proof provide a framework in which similar constructions may be brought up and their security can be easily proved.We demonstrate this by presenting some additional adjustments of the construction that achieve the following:q Reduce the success probability of the adversary.q Provide a construction of pseudo-random permutations with large input size using pseudo-random functions with small input size.

We present a new cryptographic primitive called pseudo-random synthesizer and show how to use it in order to get a parallel construction of a pseudo-random function. We show an NC/sup 1/ implementation of pseudo-random synthesizers based on the RSA or the Diffie-Hellman assumptions. This yields the first parallel (NC/sup 2/) pseudo-random function and the only alternative to the original construction of Goldreich, Gold-wasser and Micali (GGM). The security of our constructions is similar to the security of the underling assumptions. We discuss the connection with problems in computational learning theory.