Avi Wigderson

FOCS Conference 2024 Conference Paper

Constant-Depth Arithmetic Circuits for Linear Algebra Problems

• Robert Andrews 0003
• Avi Wigderson

We design polynomial size, constant depth (namely, $\text{AC}_{\mathbb{F}}^{0})$ arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any number of polynomials. Previously, the best known arithmetic formulae for these problems required super-polynomial size, regardless of depth. These results are based on new algorithmic techniques to compute various symmetric functions in the roots of polynomials, as well as manipulate the multiplicities of these roots, without having access to them. These techniques allow $\text{AC}_{\mathbb{F}}^{0}$ computation of a large class of linear and polynomial algebra problems, which include the above as special cases. We extend these techniques to problems whose inputs are multivariate polynomials, which are represented by constant-depth arithmetic circuits. Here too we solve problems such as computing the GCD and squarefree decomposition in $\text{AC}_{\mathbb{F}}^{0}$.

STOC Conference 2023 Conference Paper

An Optimal "It Ain't Over Till It's Over" Theorem

• Ronen Eldan
• Avi Wigderson
• Pei Wu

We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let f be a Boolean function such that the variance of f is Ω(1) and all its individual influences are bounded by τ. We show that when restricting all but a ρ=Ω((log1/τ) −1 ) fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function = n / C log n ∘ C log n . We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability 1− o (1). This gives a sharp version of the “it ain’t over till it’s over” theorem due to Mossel, O’Donnell, and Oleszkiewicz. Our proof is discrete, and avoids the use of the invariance principle. We also show two consequences of our above result: (i) As a corollary, we prove that for a uniformly random input x , the block sensitivity of f at x is Ω(log1/τ) with probability 1− o (1). This should be compared with the implication of Kahn, Kalai and Linial’s result, which implies that the average block sensitivity of f is Ω(log1/τ). (ii) Combining our proof with a well-known result due to O’Donnell, Saks, Schramm and Servedio, one can also conclude that: Restricting all but a ρ=Ω(1/√log(1/τ) ) fraction of the coordinates of a monotone function f , then the restricted function has decision tree complexity Ω(τ −Θ(ρ) ) with probability Ω(1).

FOCS Conference 2022 Conference Paper

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

• Fernando Granha Jeronimo
• Tushant Mittal
• Sourya Roy
• Avi Wigderson

We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d\leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree d. Furthermore, the algorithm is local: every vertex can compute its new neighbors as a subset of its original neighborhood of radius $O(\log(1/\lambda))$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc. , from existing (suboptimal) constructions of such objects. Another consequence is a “derandomized” random walk on the original (suboptimal) expander with almost optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma’s technique in his breakthrough paper [STOC 2017], used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma’s analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma’s explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert-Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit (high-dimensional”) spectral amplification.

FOCS Conference 2021 Conference Paper

Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

• Oded Goldreich 0001
• Avi Wigderson

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model. It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers. We show that this general result is essentially tight; that is, there exist graph properties for which any non-adaptive tester must have query complexity that is almost quadratic in the query complexity of the best general (i. e. , adaptive) tester. More generally, for every $q$: $\mathbb{N}\rightarrow \mathbb{N}$ such that $q(n)\leq \sqrt{n}$ and constant $c\in[1, 2]$, we show a graph property that is testable in $\Theta(q(n))$ queries, but its non-adaptive query complexity is $\Theta(q(n)^{c})$, omitting poly(log $n$ ) factors and ignoring the effect of the proximity parameter $\epsilon$. Furthermore, the upper bounds hold for one-sided error testers, and are at most quadratic in $1/\epsilon$. These results are obtained through the use of general reductions that transport properties of ordered structured (like bit strings) to those of unordered structures (like unlabeled graphs). The main features of these reductions are query-efficiency and preservation of distance to the properties. This method was initiated in our prior work (ECCC, TR20-149), and we significantly extend it here.

FOCS Conference 2020 Conference Paper

Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties

• Visu Makam
• Avi Wigderson

The object of study of this paper is the following multi-determinantal algebraic variety, SINGn, m, which captures the symbolic determinant identity testing (SDIT) problem (a canonical version of the polynomial identity testing (PIT) problem), and plays a central role in algebra, algebraic geometry and computational complexity theory. SINGn, m is the set of all m-tuples of n×n complex matrices which span only singular matrices. In other words, the determinant of any linear combination of the matrices in such a tuple vanishes. The algorithmic complexity of testing membership in SINGn, m is a central question in computational complexity. Having almost a trivial probabilistic algorithm, finding an efficient deterministic algorithm is a holy grail of derandomization, and to top it, will imply super-polynomial circuit lower bounds! A sequence of recent works suggests efficient deterministic “geodesic descent” algorithms for memberships in a general class of algebraic varieties, namely the null cones of (reductive) linear group actions. Can such algorithms be used for the problem above? Our main result is negative: SINGn, m is not the null cone of any such group action! This stands in stark contrast to a non-commutative analog of this variety (for which such algorithms work), and points to an inherent structural difficulty of SINGn, m. In other words, we provide a barrier for the attempts of derandomizing SDIT via these algorithms. To prove this result we identify precisely the group of symmetries of SINGn, m. We find this characterization, and the tools we introduce to prove it, of independent interest. Our characterization significantly generalizes a result of Frobenius for the special case m=1 (namely, computing the symmetries of the determinant). Our proof suggests a general method for determining the symmetries of general algebraic varieties, an algorithmic problem that was hardly studied and we believe is central to algebraic complexity.

FOCS Conference 2019 Conference Paper

More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer

• Ankit Garg 0001
• Visu Makam
• Rafael Oliveira 0002
• Avi Wigderson

We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal rank lower bounds on k-tensors cannot yield non-trivial lower bounds on the rank of d-tensors, for any constant d larger than k. This significantly extends recent barrier results on the limits of (matrix) rank methods by [EGOW17], which handles the (very important) case k=2. Our generalization requires the development of new technical tools and results in algebraic geometry, which are interesting in their own right and possibly applicable elsewhere. The basic issue they probe is the relation between numeric and symbolic rank of tensors, essential in the proofs of previous and current barriers. Our main technical result implies that for every symbolic k-tensor (namely one whose entries are polynomials in some set of variables), if the tensor rank is small for every evaluation of the variables, then it is small symbolically. This statement is obvious for k=2. To prove an analogous statement for k larger than 2 we develop a "numeric to symbolic'' transfer of algebraic %analytic relations to algebraic %analytic functions, somewhat in the spirit of the implicit function theorem. It applies in the general setting of inclusion of images of polynomial maps, in the form appearing in Raz's elusive functions approach to proving VP ≠ VNP. We give a toy application showing how our transfer theorem may be useful in pursuing this approach to prove arithmetic complexity lower bounds.

FOCS Conference 2019 Conference Paper

Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes

• Peter Bürgisser
• Cole Franks
• Ankit Garg 0001
• Rafael Oliveira 0002
• Michael Walter 0005
• Avi Wigderson

This paper initiates a systematic development of a theory of non-commutative optimization, a setting which greatly extends ordinary (Euclidean) convex optimization. It aims to unify and generalize a growing body of work from the past few years which developed and analyzed algorithms for natural geodesic convex optimization problems on Riemannian manifolds that arise from the symmetries of non-commutative groups. More specifically, these are algorithms to minimize the moment map (a non-commutative notion of the usual gradient), and to test membership in moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which quite magically arise from this a-priori non-convex, non-linear setting). The importance of understanding this very general setting of geodesic optimization, as these works unveiled and powerfully demonstrate, is that it captures a diverse set of problems, many non-convex, in different areas of CS, math, and physics. Several of them were solved efficiently for the first time using non-commutative methods; the corresponding algorithms also lead to solutions of purely structural problems and to many new connections between disparate fields. In the spirit of standard convex optimization, we develop two general methods in the geodesic setting, a first order and a second order method, which respectively receive first and second order information on the "derivatives" of the function to be optimized. These in particular subsume all past results. The main technical work, again unifying and extending much of the previous work, goes into identifying the key parameters of the underlying group actions which control convergence to the optimum in each of these methods. These non-commutative analogues of "smoothness" in the commutative case are far more complex, and require significant algebraic and analytic machinery (much existing and some newly developed here). Despite this complexity, the way in which these parameters control convergence in both methods is quite simple and elegant. We also bound these parameters in several general cases. Our work points to intriguing open problems and suggests further research directions. We believe that extending this theory, namely understanding geodesic optimization better, is both mathematically and computationally fascinating; it provides a great meeting place for ideas and techniques from several very different research areas, and promises better algorithms for existing and yet unforeseen applications.

FOCS Conference 2018 Conference Paper

Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes

• Peter Bürgisser
• Cole Franks
• Ankit Garg 0001
• Rafael Oliveira 0002
• Michael Walter 0005
• Avi Wigderson

We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of "numerical" methods for classical problems in invariant theory that are significantly faster than "symbolic" methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

STOC Conference 2018 Conference Paper

Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing

• Zeyuan Allen-Zhu
• Ankit Garg 0001
• Yuanzhi Li
• Rafael Oliveira 0002
• Avi Wigderson

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, "commutative" metric (for which the above problem is not convex). Our method is general and applicable to other settings. As a consequence, we solve the equivalence problem for the left-right group action underlying the operator scaling problem. This yields a deterministic polynomial-time algorithm for a new class of Polynomial Identity Testing (PIT) problems, which was the original motivation for studying operator scaling.

STOC Conference 2017 Conference Paper

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling

• Ankit Garg 0001
• Leonid Gurvits
• Rafael Oliveira 0002
• Avi Wigderson

The celebrated Brascamp-Lieb (BL) inequalities [BL76, Lie90], and their reverse form of Barthe [Bar98], are an important mathematical tool, unifying and generalizing numerous in- equalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters below (which we later define). Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute: (1) Feasibility of BL-datum, (2) Optimal BL- constant, (3) Weak separation oracle for BL-polytopes. What is particularly exciting about this progress, beyond the better understanding of BL- inequalities, is that the objects above naturally encode rich families of optimization problems which had no prior efficient algorithms. In particular, the BL-constants (which we efficiently compute) are solutions to non-convex optimization problems, and the BL-polytopes (for which we provide efficient membership and separation oracles) are linear programs with exponentially many facets. Thus we hope that new combinatorial optimization problems can be solved via reductions to the ones above, and make modest initial steps in exploring this possibility. Our algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by [Gur04]. To obtain the results above, we utilize the two (very recent and different) algorithms for the operator scaling problem [GGOW16, IQS15a]. Our reduction implies algorithmic versions of many of the known structural results on BL-inequalities, and in some cases provide proofs that are different or simpler than existing ones. Further, the analytic properties of the [GGOW16] algorithm provide new, effective bounds on the magnitude and continuity of BL-constants, with applications to non-linear versions of BL-inequalities; prior work relied on compactness, and thus provided no bounds. On a higher level, our application of operator scaling algorithm to BL-inequalities further connects analysis and optimization with the diverse mathematical areas used so far to mo- tivate and solve the operator scaling problem, which include commutative invariant theory, non-commutative algebra, computational complexity and quantum information theory.

FOCS Conference 2017 Conference Paper

Much Faster Algorithms for Matrix Scaling

• Zeyuan Allen-Zhu
• Yuanzhi Li
• Rafael Oliveira 0002
• Avi Wigderson

We develop several efficient algorithms for the classical Matrix Scaling problem, which is used in many diverse areas, from preconditioning linear systems to approximation of the permanent. On an input n×n matrix A, this problem asks to find diagonal (scaling) matrices X and Y (if they exist), so that XAY ε-approximates a doubly stochastic matrix, or more generally a matrix with prescribed row and column sums. We address the general scaling problem as well as some important special cases. In particular, if A has m nonzero entries, and if there exist X and Y with polynomially large entries such that XAY is doubly stochastic, then we can solve the problem in total complexity Õ(m + n 4/3 ). This greatly improves on the best known previous results, which were either Õ(n 4 ) or O(mn 1/2 /ε). Our algorithms are based on tailor-made first and second order techniques, combined with other recent advances in continuous optimization, which may be of independent interest for solving similar problems.

FOCS Conference 2016 Conference Paper

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

• Ankit Garg 0001
• Leonid Gurvits
• Rafael Oliveira 0002
• Avi Wigderson

Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) invariant theory and representationtheory, linear algebra, optimization, linear system theory, quantum information theory, and naturally in non-commutativealgebra.

SODA Conference 2016 Conference Paper

Towards Optimal Deterministic Coding for Interactive Communication

• Ran Gelles
• Bernhard Haeupler
• Gillat Kol
• Noga Ron-Zewi
• Avi Wigderson

We study efficient, deterministic interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length. For channels that flip bits independently with probability ∊ < 1/2, our coding scheme achieves a communication rate of and a failure probability of exp(− n /log n ) in length n protocols. Prior to our work, all nontrivial deterministic schemes (either efficient or not) had a rate bounded away from 1. Furthermore, the best failure probability achievable by an efficient deterministic coding scheme with constant rate was only quasi-polynomial, i. e. , of the form exp(− log O (1) n ) (Braverman, ITCS 2012). For channels in which an adversary controls the noise pattern our coding scheme can tolerate Ω(1/log n ) fraction of errors with rate approaching 1. Once more, all previously known nontrivial deterministic schemes (either efficient or not) in the adversarial setting had a rate bounded away from 1, and no nontrivial efficient deterministic coding schemes were known with any constant rate. Essential to both results is an explicit, efficiently encodable and decodable systematic tree code of length n that has relative distance Ω(1/log n ) and rate approaching 1, defined over an O (log n )-bit alphabet. No nontrivial tree code (either efficient or not) was known to approach rate 1, and no nontrivial distance bound was known for any efficient constant rate tree code. The fact that our tree code is systematic, turns out to play an important role in obtaining rate in the random error model, and approaching rate 1 in the adversarial error model.

FOCS Conference 2015 Conference Paper

Compressing and Teaching for Low VC-Dimension

• Shay Moran
• Amir Shpilka
• Avi Wigderson
• Amir Yehudayoff

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. Namely, the quality of sample compression schemes and of teaching sets for classes of low VC-dimension. Let C be a binary concept class of size m and VC-dimension d. Prior to this work, the best known upper bounds for both parameters were log(m), while the best lower bounds are linear in d. We present significantly better upper bounds on both as follows. We construct sample compression schemes of size exp(d) for C. This resolves a question of Littlest one and Warmuth (1986). Roughly speaking, we show that given an arbitrary set of labeled examples from an unknown concept in C, one can retain only a subset of exp(d) of them, in a way that allows to recover the labels of all other examples in the set, using additional exp(d) information bits. We further show that there always exists a concept c in C with a teaching set (i. e. A list of c-labeled examples uniquely identifying c in C) of size exp(d) log log(m). This problem was studied by Kuhlmann (1999). Our construction also implies that the recursive teaching (RT) dimension of C is at most exp(d) log log(m) as well. The RT-dimension was suggested by Zilles et al. And Doliwa et al. (2010). The same notion (under the name partial-ID width) was independently studied by Wigderson and Yehuday off (2013). An upper bound on this parameter that depends only on d is known just for the very simple case d=1, and is open even for d=2. We also make small progress towards this seemingly modest goal.

STOC Conference 2015 Conference Paper

Reed-Muller Codes for Random Erasures and Errors

• Emmanuel Abbe
• Amir Shpilka
• Avi Wigderson

STOC Conference 2015 Conference Paper

Sum-of-squares Lower Bounds for Planted Clique

• Raghu Meka
• Aaron Potechin
• Avi Wigderson

Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for k = Θ(√n). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy. We prove the first average case lower bound for this model: for almost all graphs in G(n,1/2), r rounds of the SOS hierarchy cannot find a planted k-clique unless k ≥ (√n/log n) 1/r C r . Thus, for any constant number of rounds planted cliques of size n o(1) cannot be found by this powerful class of algorithms. This is shown via an integrability gap for the natural formulation of maximum clique problem on random graphs for SOS and Lasserre hierarchies, which in turn follow from degree lower bounds for the Positivestellensatz proof system. We follow the usual recipe for such proofs. First, we introduce a natural "dual certificate" (also known as a "vector-solution" or "pseudo-expectation") for the given system of polynomial equations representing the problem for every fixed input graph. Then we show that the matrix associated with this dual certificate is PSD (positive semi-definite) with high probability over the choice of the input graph.This requires the use of certain tools. One is the theory of association schemes, and in particular the eigenspaces and eigenvalues of the Johnson scheme. Another is a combinatorial method we develop to compute (via traces) norm bounds for certain random matrices whose entries are highly dependent; we hope this method will be useful elsewhere.

NeurIPS Conference 2015 Conference Paper

Sum-of-Squares Lower Bounds for Sparse PCA

• Tengyu Ma
• Avi Wigderson

This paper establishes a statistical versus computational trade-offfor solving a basic high-dimensional machine learning problem via a basic convex relaxation method. Specifically, we consider the {\em Sparse Principal Component Analysis} (Sparse PCA) problem, and the family of {\em Sum-of-Squares} (SoS, aka Lasserre/Parillo) convex relaxations. It was well known that in large dimension $p$, a planted $k$-sparse unit vector can be {\em in principle} detected using only $n \approx k\log p$ (Gaussian or Bernoulli) samples, but all {\em efficient} (polynomial time) algorithms known require $n \approx k^2 $ samples. It was also known that this quadratic gap cannot be improved by the the most basic {\em semi-definite} (SDP, aka spectral) relaxation, equivalent to a degree-2 SoS algorithms. Here we prove that also degree-4 SoS algorithms cannot improve this quadratic gap. This average-case lower bound adds to the small collection of hardness results in machine learning for this powerful family of convex relaxation algorithms. Moreover, our design of moments (or ``pseudo-expectations'') for this lower bound is quite different than previous lower bounds. Establishing lower bounds for higher degree SoS algorithms for remains a challenging problem.

STOC Conference 2014 Conference Paper

Breaking the quadratic barrier for 3-LCC's over the reals

• Zeev Dvir
• Shubhangi Saraf
• Avi Wigderson

We prove that 3-query linear locally correctable codes over the Reals of dimension d require block length n > d 2+ λ for some fixed, positive λ > 0. Geometrically, this means that if n vectors in R d are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that n > d 2+ λ . This improves the known quadratic lower bounds (e.g. [20, 28]). While a modest improvement, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries. At a high level, our proof has two parts, clustering and random restriction . The clustering step uses a powerful geometric theorem of Barthe which finds a basis change (and rescaling) putting the code in nearly isotropic position. This together with the fact that any LCC must have many 'correlated' pairs of points, lets us deduce that the vectors must have a surprisingly strong geometric clustering, and hence also combinatorial clustering with respect to the spanning triples. In the restriction step, we devise a new variant of the dimension reduction technique used in previous lower bounds, which is able to take advantage of the combinatorial clustering structure above. The analysis of our random projection method reduces to a simple (weakly) random graph process, and works over any field.

STOC Conference 2014 Conference Paper

On derandomizing algorithms that err extremely rarely

• Oded Goldreich 0001
• Avi Wigderson

Does derandomization of probabilistic algorithms become easier when the number of "bad" random inputs is extremely small? In relation to the above question, we put forward the following quantified derandomization challenge: For a class of circuits C (e.g., P /poly or AC 0 , AC 0 [2]) and a bounding function B : N → N (e.g., B ( n ) = n log n or B ( n ) = exp( n 0.99 ))), given an n -input circuit C from C that evaluates to 1 on all but at most B ( n ) of its inputs, find (in deterministic polynomial-time) an input x such that C ( x ) = 1. Indeed, the standard derandomization challenge for the class C corresponds to the case of B ( n ) = 2 n /2 (or to B ( n ) = 2 n /3 for the two-sided version case). Our main results regarding the new quantified challenge are: 1. Solving the quantified derandomization challenge for the class AC 0 and every sub-exponential bounding function (e.g., B ( n ) = exp( n 0.999 )). 2. Showing that solving the quantified derandomization challenge for the class AC 0 [2] and any sub-exponential bounding function (e.g., B ( n ) = exp( n 0.001 )), implies solving the standard derandomization challenge for the class AC 0 [2] (i.e., for B ( n ) = 2 n /2). Analogous results are obtained also for stronger (Black-box) forms of efficient derandomization like hitting-set generators. We also obtain results for other classes of computational devices including log-space algorithms and Arithmetic circuits. For the latter we present a deterministic polynomial-time hitting set generator for the class of n -variate polynomials of degree d over GF(2) that evaluate to 0 on at most an O (2 - d ) fraction of their inputs. In general, the quantified derandomization problem raises a variety of seemingly unexplored questions about many randomized complexity classes, and may offer a tractable approach to unconditional derandomization for some of them.

STOC Conference 2014 Conference Paper

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

• Dmitry Gavinsky
• Or Meir
• Omri Weinstein
• Avi Wigderson

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P ⊈ NC 1 ). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds. Karchmer, Raz, and Wigderson [21] suggested to approach this problem by proving the following conjecture: given two boolean functions f and g , the depth complexity of the composed function g o f is roughly the sum of the depth complexities of f and g . They showed that the validity of this conjecture would imply that P ⊈ NC 1 . As a starting point for studying the composition of functions, they introduced a relation called "the universal relation", and suggested to study the composition of universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [12]. An alternative proof was given later by Håstad and Wigderson [18]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open. In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it. Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations -- communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

STOC Conference 2013 Conference Paper

Interactive proofs of proximity: delegating computation in sublinear time

• Guy N. Rothblum
• Salil P. Vadhan
• Avi Wigderson

FOCS Conference 2012 Conference Paper

Population Recovery and Partial Identification

• Avi Wigderson
• Amir Yehudayoff

We study several problems in which an unknown distribution over an unknown population of vectors needs to be recovered from partial or noisy samples, each of which nearly completely erases or obliterates the original vector. For example, consider a distribution p over a population V ⊆ {0, 1} n. A noisy sample v' is obtained by choosing v according to p and flipping each coordinate of v with probability say 0. 49 independently. The problem is to recover V, p as efficiently as possible from noisy samples. Such problems naturally arise in a variety of contexts in learning, clustering, statistics, computational biology, data mining and database privacy, where loss and error may be introduced by nature, inaccurate measurements, or on purpose. We give fairly efficient algorithms to recover the data under fairly general assumptions. Underlying our algorithms is a new structure we call a partial identification (PID) graph for an arbitrary finite set of vectors over any alphabet. This graph captures the extent to which certain subsets of coordinates in each vector distinguish it from other vectors. PID graphs yield strategies for dimension reductions and re-assembly of statistical information. The quality of our algorithms (sequential and parallel runtime, as well as numerical stability) critically depends on three parameters of PID graphs: width, depth and cost. The combinatorial heart of this work is showing that every set of vectors posses a PID graph in which all three parameters are small (we prove some limitations on their trade-offs as well). We further give an efficient algorithm to find such near-optimal PID graphs for any set of vectors. Our efficient PID graphs imply general algorithms for these recovery problems, even when loss or noise are just below the information-theoretic limit! In the learning/clustering context this gives a new algorithm for learning mixtures of binomial distributions (with known marginals) whose running time depends only quasi-polynomially on the number of clusters. We discuss implications to privacy and coding as well.

STOC Conference 2011 Conference Paper

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

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

STOC Conference 2010 Conference Paper

Non-commutative circuits and the sum-of-squares problem

• Pavel Hrubes
• Avi Wigderson
• Amir Yehudayoff

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree four polynomials, the classical sum-of-squares problem: find the smallest n such that there exists an identity (x 1 2 +x 2 2 +•• + x k 2 )• (y 1 ^2+y 2 2 +•• + y k 2 )= f 1 2 +f 2 2 + ... +f n 2 , where each f i = f i (X,Y) is bilinear in X={x 1 ,... ,x k } and Y={y 1 ,..., y k }. Over the complex numbers, we show that a sufficiently strong super-linear lower bound on n in, namely, n ≥ k 1+ε with ε >0, implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.

STOC Conference 2010 Conference Paper

Public-key cryptography from different assumptions

• Benny Applebaum
• Boaz Barak
• Avi Wigderson

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

FOCS Conference 2009 Conference Paper

Linear Systems over Composite Moduli

• Arkadev Chattopadhyay
• Avi Wigderson

We study solution sets to systems of 'generalized' linear equations of the form: ¿ i (x 1, x 2, ···, x n ) in ¿ A i (mod m) where ¿ 1, .. ., ¿ t are linear forms in n Boolean variables, each A i is an arbitrary subset of Z m, and m is a composite integer that is a product of two distinct primes, like 6. Our main technical result is that such solution sets have exponentially small correlation, i. e. with the boolean function MOD q, when m and q are relatively prime. This bound is independent of the number t of equations. This yields progress on limiting the power of constant-depth circuits with modular gates. We derive the first exponential lower bound on the size of depth-three circuits of type MAJ o AND o MOD A m (i. e having a MAJORITY gate at the top, AND/OR gates at the middle layer and generalized MOD m gates at the base) computing the function MOD q. This settles an open problem of Beigel and Maciel (Complexity'97) for the case of such modulus m. Our technique makes use of the work of Bourgain on estimating exponential sums involving a low-degree polynomial and ideas involving matrix rigidity from the work of Grigoriev and Razborov on arithmetic circuits over finite fields.

STOC Conference 2009 Conference Paper

New direct-product testers and 2-query PCPs

• Russell Impagliazzo
• Valentine Kabanets
• Avi Wigderson

The "direct product code" of a function f gives its values on all k-tuples (f(x 1 ),...,f(x k )). This basic construct underlies "hardness amplification" in cryptography, circuit complexity and PCPs. Goldreich and Safra [12] pioneered its local testing and its PCP application. A recent result by Dinur and Goldenberg [5] enabled for the first time testing proximity to this important code in the "list-decoding" regime. In particular, they give a 2-query test which works for polynomially small success probability 1/k α , and show that no such test works below success probability 1/k. Our main result is a 3-query test which works for exponentially small success probability exp(-k α ). Our techniques (based on recent simplified decoding algorithms for the same code [15]) also allow us to considerably simplify the analysis of the 2-query test of [5]. We then show how to derandomize their test, achieving a code of polynomial rate, independent of k, and success probability 1/k α . Finally we show the applicability of the new tests to PCPs. Starting with a 2-query PCP over an alphabet Σ and with soundness error 1-δ, Rao [19] (building on Raz's (k-fold) parallel repetition theorem [20] and Holenstein's proof [13]) obtains a new 2-query PCP over the alphabet Σ k with soundness error exp(-δ 2 k). Our techniques yield a 2-query PCP with soundness error exp(-δ √k). Our PCP construction turns out to be essentially the same as the miss-match proof system defined and analyzed by Feige and Kilian [8], but with simpler analysis and exponentially better soundness error.

STOC Conference 2009 Conference Paper

The work of Leslie Valiant

• Avi Wigderson

On Saturday, May 30, one day before the start of the regular STOC 2009 program, a workshop was held in celebration of Leslie Valiant's 60th birthday. Talks were given by Jin-Yi Cai, Stephen Cook, Vitaly Feldman, Mark Jerrum, Michael Kearns, Mike Paterson, Michael Rabin, Rocco Servedio, Paul Valiant, Vijay Vazirani, and Avi Wigderson. The workshop was organized by Michael Kearns, Rocco Servedio, and Salil Vadhan, with support from the STOC local arrangements team and program committee. To accompany the workshop, here we briefly survey Valiant's many fundamental contributions to the theory of computing.

STOC Conference 2008 Conference Paper

Algebrization: a new barrier in complexity theory

• Scott Aaronson
• Avi Wigderson

Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory. In this paper we present such a barrier, which we call algebraic relativization or algebrization. The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to a low-degree extension of A over a finite field or ring. We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. First, we show that all known non-relativizing results based on arithmetization -- both inclusions such as IP=PSPACE and MIP=NEXP, and separations such as MAEXP not in P/poly -- do indeed algebrize. Second, we show that almost all of the major open problems -- including P versus NP, P versus RP, and NEXP versus P/poly -- will require non-algebrizing techniques. In some cases algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP. Our second set of results follows from lower bounds in a new model of algebraic query complexity, which we introduce in this paper and which is interesting in its own right. Some of our lower bounds use direct combinatorial and algebraic arguments, while others stem from a surprising connection between our model and communication complexity. Using this connection, we are also able to give an MA-protocol for the Inner Product function with O(sqrt(n) log n) communication (essentially matching a lower bound of Klauck).

FOCS Conference 2008 Conference Paper

Kakeya Sets, New Mergers and Old Extractors

• Zeev Dvir
• Avi Wigderson

A merger is a probabilistic procedure which extracts the randomness out of any (arbitrarily correlated) set of random variables, as long as one of them is uniform. Our main result is an efficient, simple, optimal (to constant factors) merger, which, for k random vairables on n bits each, uses a O(log(nk)) seed, and whose error is 1/nk. Our merger can be viewed as a derandomized version of the merger of Lu, Reingold, Vadhan and Wigderson (2003). Its analysis generalizes the recent resolutionof the Kakeya problem in finite fields of Dvir (2008). Following the plan set forth by Ta-Shma (1996), who defined mergers as part of this plan, our merger provides the last "missing link" to a simple and modular construction of extractors for all entropies, which is optimal to constant factorsin all parameters. This complements the elegant construction of optimal extractor by Guruswami, Vadhan and Umans (2007). We also give simple extensions of our merger in two directions. First, we generalize it to handle the case where no source is uniform - in that case the merger will extract the entropy present in the most random of the given sources. Second, we observe that the merger works just as well in the computational setting, when the sources are efficiently samplable, and computational notions of entropy replace the information theoretic ones.

FOCS Conference 2008 Conference Paper

Spherical Cubes and Rounding in High Dimensions

• Guy Kindler
• Ryan O'Donnell
• Anup Rao 0001
• Avi Wigderson

What is the least surface area of a shape that tiles Ropf d under translations by Zopf d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Omega(radicd). Our main result is a construction with surface area O(radicd), matching the lower bound up to a constant factor of 2radic2pi/eap3. The best previous tile known was only slightly better than the cube, having surface area on the order of d. We generalize this to give a construction that tiles Ropf d by translations of any full rank discrete lattice Lambda with surface area 2piparV -1 par fb, where V is the matrix of basis vectors of Lambda, and par. par fb denotes the Frobenius norm. We show that our bounds are optimal within constant factors for rectangular lattices. Our proof is via a random tessellation process, following recent ideas of Raz in the discrete setting. Our construction gives an almost optimal noise-resistant rounding scheme to round points in Ropf d to rectangular lattice points.

STOC Conference 2008 Conference Paper

Uniform direct product theorems: simplified, optimized, and derandomized

• Russell Impagliazzo
• Ragesh Jaiswal
• Valentine Kabanets
• Avi Wigderson

The classical Direct-Product Theorem for circuits says that if a Boolean function f: {0,1} n -> {0,1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function f k (x 1 ,...,x k )=(f(x 1 ),...,f(x k )) (where each x i -> {0,1} n ) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the Direct-Product Theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and ε, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes f k on at least ε fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of O(1/ε) circuits such that at least one of the circuits on the list computes f on more than 1-δ fraction of inputs, for δ = O((log 1/ε)/k). Moreover, each output circuit is an AC 0 circuit (of size poly(n,k,log 1/δ,1/ε)), with oracle access to the circuit C. Using the Goldreich-Levin decoding algorithm [5], we also get a fully uniform version of Yao's XOR Lemma [18] with optimal parameters, up to constant factors. Our results simplify and improve those in [10]. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of "derandomized" direct-product codes, which we call intersection codes , where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.

FOCS Conference 2007 Conference Paper

Extractors and Rank Extractors for Polynomial Sources

• Zeev Dvir
• Ariel Gabizon
• Avi Wigderson

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources. A direct consequence is a deterministic extractor for distributions sampled by polynomial size arithmetic circuits over exponentially large fields. The first step towards extraction is a construction o/rank extractors, which are polynomial mappings that "extract" the algebraic rank from any system of low degree polynomials. More precisely, for any n polynomials, k of which are algebraically independent, a rank extractor outputs k algebraically independent polynomials of slightly higher degree. A result of Wooley allows us to relate algebraic rank and min-entropy and to show that a rank extractor is also a high quality condenser for polynomial sources over polynomially large fields. Finally, to turn this condenser into an extractor, we employ a theorem of Bombieri, giving a character sum estimate for polynomials defined over curves. It allows extracting all the randomness (up to a multiplicative constant) from polynomial sources over exponentially large fields.

FOCS Conference 2007 Conference Paper

One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications

• Emanuele Viola
• Avi Wigderson

In this paper we study the one-way multi-party communication model, in which even party speaks exactly once in its turn. For every fixed k, we prove a tight lower hound of Omega (n 1/(k-1) ) on the probabilistic communication complexity of pointer jumping in a k-layered tree, where the pointers of the i-lh layer reside on the forehead of the i-th party to speak. The lower bound remains nontrivial even for k = (log n) 1/2-Omega(1) parties. Previous to our work a lower bound was known only for k = 3, and in very restricted models for k > 3. Our results have the following consequences to other models and problems, extending previous work in several directions. The one-way model is strong enough to capture general (non one-wav) multi-party protocols of bounded rounds. Thus we generalize to this multi-party model results on two directions studied in the classical 2-party model. The first is a mund hierarchy: We give an exponential separation between the power of r and 2r rounds in general probabilistic k-party protocols, for any fixed k and r. The second is the relative power of determinism and nondeterminism: We prove an exponential separation between nondeterministic and deterministic communication complexity for general k-party protocols with r rounds, for anvfixed k, r. The pointer jumping function is weak enough to be a special case of the well-studied disjointness function. Thus we obtain a lower bound of Omega (n 1/(k-1) ) on the probabilistic complexity of k-set disjointness in the oneway model, which was known only for k = 3 parties. Our result also extends a similar lower bound for the weaker simultaneous model, in which parties simultaneously send one message to a referee. Finally, we infer an exponential separation between the power of different orders in which parties send messages in the one-way model, for every fixed k. Previous to our work such a separation was only known for k = 3. Our lower bound technique, which handles functions of high discrepancy, may be of independent interest. It provides a "party-elimination " induction, based on a restricted form of a direct-product result, specific to the pointer jumping function.

STOC Conference 2006 Conference Paper

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

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

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

FOCS Conference 2005 Conference Paper

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

• Avi Wigderson
• David Xiao

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter [2002], in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is a generalization of Gillman's and Lezaud's analyses of the Ajtai-Komlos-Szemeredi sampler for real-valued functions [Gillman, 1993]. Derandomizing our sampler gives a few applications, yielding deterministic polynomial time algorithms for problems in which derandomizing independent sampling gives only quasi-polynomial time deterministic algorithms. The first (which was our original motivation) is to a polynomial-time derandomization of the Alon-Roichman theorem [Alon and Roichman, 1994]: given a group of size n, find O(log n) elements which generate it as an expander. This implies a second application - efficiently constructing a randomness-optimal homo-morphism tester, significantly improving the previous result of Shpilka and Wigderson [2004]. A third application, which derandomizes a generalization of the set cover problem, is deferred to the full version of this paper.

STOC Conference 2005 Conference Paper

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

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

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

STOC Conference 2004 Conference Paper

A new family of Cayley expanders (?)

• Eyal Rozenman
• Aner Shalev
• Avi Wigderson

We assume that for some fixed large enough integer d, the symmetric group S d can be generated as an expander using d 1/30 generators. Under this assumption, we explicitly construct an infinite family of groups G n , and explicit sets of generators Y n ⊂ G n , such that all generating sets have bounded size (at most d 1/7 ), and the associated Cayley graphs are all expanders. The groups G n above are very simple, and completely different from previous known examples of expanding groups. Indeed, G n is (essentially) all symmetries of the d-regular tree of depth n. The proof is completely elementary, using only simple combinatorics and linear algebra. The recursive structure of the groups G n (iterated wreath products of the alternating group A d ) allows for an inductive proof of expansion, using the group theoretic analogue [4] of the zig-zag graph product of [38]. The explicit construction of the generating sets Y n uses an efficient algorithm for solving certain equations over these groups, which relies on the work of [33] on the commutator width of perfect groups.We stress that our assumption above on weak expansion in the symmetric group is an open problem. We conjecture that it holds for all d. We discuss known results related to its likelihood in the paper.

STOC Conference 2004 Conference Paper

Depth through breadth, or why should we attend talks in other areas?

• Avi Wigderson

Given that the two other invited lectures in this conference are on such remote areas as "Quantum Computation" and "Algorithmic Game Theory," and given the diversity of other topics represented in the program, it makes sense to ask if the STOC/FOCS community is still one.Indeed, the program chair has asked me to respond to this question.In the talk I'll try to illustrate, with a few (of many) examples, how the presence of such diversity in our community and conferences was actually responsible for important progress in specific areas of research, why I find these a natural and expected phenomena, and why I expect this trend to continue.

STOC Conference 2004 Conference Paper

Derandomizing homomorphism testing in general groups

• Amir Shpilka
• Avi Wigderson

The main result of this paper is a near-optimal derandomization of the affine homomorphism test of Blum, Luby and Rubinfeld [11]. We show that for any groups G and Γ, and any expanding generating set S of G, the natural deramdomized version of the BLR test in which we pick an element x randomly from G and y randomly from S and test whether f(x) · f(y)=f(x · y), performs nearly as well (depending of course on the expansion) as the original test. Moreover we show that the underlying homomorphism can be found by the natural local "belief propagation decoding". We note that the original BLR test uses 2 log 2 |G| random bits, whereas the derandomized test uses only (1+o(1)) log 2 |G| random bits. This factor of 2 savings in the randomness complexity translates to a near quadratic savings in the length of the tables in the related locally testable codes (and possibly probabilistically checkable proofs which may use them). Our result is a significant generalization of the recent result of [12], who proved such a result only for the groups G=Z p m and Γ=Z p . It is also an explicit version of the nonconstructive result of [18]. We use a simple combinatorial arguments and the transitivity of Cayley graphs (and this analysis gives optimal results up to constant factors). Previous techniques used the Fourier transform, a method which seems unextendable to general groups (and furthermore gives suboptimal bounds). Finally, we provide a polynomial time (in |G|) construction of a (somewhat) small (|G| ε ) set of expanding generators for every group G, which yield efficient testers of randomness (1+ε) log |G| for G. This follows a simple derandomization of the probabilistic construction of [5], who showed that almost all logarithmic-size sets are expanding. Our work motivates further study of similar derandomizations of other natural property testing procedures, especially those more relevant to the local testing of better codes and to PCPs.

FOCS Conference 2004 Conference Paper

Extracting Randomness Using Few Independent Sources

• Boaz Barak
• Russell Impagliazzo
• Avi Wigderson

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

STOC Conference 2003 Conference Paper

Extractors: optimal up to constant factors

• Chi-Jen Lu
• Omer Reingold
• Salil P. Vadhan
• Avi Wigderson

STOC Conference 2003 Conference Paper

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets

• Eli Ben-Sasson
• Madhu Sudan 0001
• Salil P. Vadhan
• Avi Wigderson

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

STOC Conference 2002 Conference Paper

Expanders from symmetric codes

• Roy Meshulam
• Avi Wigderson

(MATH) A set S in the vector space FF p n is "good" if it satisfies the following (almost) equivalent conditions: S is an expanding generating set of Abelian group FF p n .

STOC Conference 2002 Conference Paper

Randomness conductors and constant-degree lossless expanders

• Michael R. Capalbo
• Omer Reingold
• Salil P. Vadhan
• Avi Wigderson

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.

FOCS Conference 2001 Conference Paper

Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications

• Noga Alon
• Alexander Lubotzky
• Avi Wigderson

We consider the standard semi-direct product A/spl times/B of finite groups A, B. We show that with certain choices of generators for these three groups, the Cayley graph of A/spl times/B is (essentially) the zigzag product of the Cayley graphs of A and B. Thus, using the results of O. Reingold et al. (2000), the new Cayley graph is an expander if and only if its two components are. We develop some general ways of using this construction to obtain large constant-degree expanding Cayley graphs from small ones. A. Lubotzky and B. Weiss (1993) asked whether expansion is a group property; namely, is being an expander for (a Cayley graph of) a group G depend solely on G and not on the choice of generators. We use the above construction to answer the question in the negative, by showing an infinite family of groups A/sub i//spl times/B/sub i/ which are expanders with one choice of a (constant-size) set of generators and are not with another such choice. It is interesting to note that this problem is still open, though for "natural" families of groups like the symmetric groups S/sub n/ or the simple groups PSL(2, p).

FOCS Conference 2000 Conference Paper

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

• Omer Reingold
• Salil P. Vadhan
• Avi Wigderson

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

FOCS Conference 2000 Conference Paper

Extracting Randomness via Repeated Condensing

• Omer Reingold
• Ronen Shaltiel
• Avi Wigderson

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.

STOC Conference 2000 Conference Paper

Extractors and pseudo-random generators with optimal seed length

• Russell Impagliazzo
• Ronen Shaltiel
• Avi Wigderson

FOCS Conference 2000 Conference Paper

Pseudorandom Generators in Propositional Proof Complexity

• Michael Alekhnovich
• Eli Ben-Sasson
• Alexander A. Razborov
• Avi Wigderson

We call a pseudorandom generator G/sub n/: {0, 1}/sup n//spl rarr/{0, 1}/sup m/ hard for a propositional proof system P if P can not efficiently prove the (properly encoded) statement G/sub n/(x/sub 1/, .. ., x/sub n/)/spl ne/b for any string b/spl epsiv/{0, 1}/sup m/. We consider a variety of "combinatorial" pseudorandom generators inspired by the Nisan-Wigderson generator on one hand, and by the construction of Tseitin tautologies on the other. We prove that under certain circumstances these generators are hard for such proof systems as resolution, polynomial calculus and polynomial calculus with resolution (PCR).

STOC Conference 2000 Conference Paper

Space complexity in propositional calculus

• Michael Alekhnovich
• Eli Ben-Sasson
• Alexander A. Razborov
• Avi Wigderson

FOCS Conference 1999 Conference Paper

Near-Optimal Conversion of Hardness into Pseudo-Randomness

• Russell Impagliazzo
• Ronen Shaltiel
• Avi Wigderson

Various efforts have been made to derandomize probabilistic algorithms using the assumption that there exists a problem in E=dtime(2/sup O(n)/) that requires circuits of size s(n) (for some function s). These results are based on the NW (Nisan & Wigderson, 1997) generator. For the strong lower bound s(n)=2/sup ϵn/, the optimal derandomization is P=BPP. However, for weaker lower bound functions s(n), these constructions fall short of the natural conjecture for optimal derandomization that bptime(t)⊆ dtime(2O[s/sup -1/(t)]). The gap is due to an inherent efficiency limitation in NW-style pseudorandom generators. We are able to obtain derandomization in almost optimal time using any lower bound s(n). We do this by using the NW-generator in a more sophisticated way. We view any failure of the generator as a reduction from the given hard function to its restrictions on smaller input sizes. Thus, either the original construction works optimally or one of the restricted functions is as hard as the original. Any such restriction can then be plugged into the NW-generator recursively. This process generates many candidate generators, and at least one is guaranteed to be good. To perform the approximation of the acceptance probability of the given circuit, we run a tournament between the candidate generators which yields an accurate estimate. We explore information theoretic analogs of our new construction. The inherent limitation of the NW-generator makes the extra randomness required by that extractor suboptimal. However, applying our construction, we get an almost optimal disperser.

STOC Conference 1999 Conference Paper

Short Proofs are Narrow - Resolution Made Simple

• Eli Ben-Sasson
• Avi Wigderson

STOC Conference 1998 Conference Paper

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents

• Nati Linial
• Alex Samorodnitsky
• Avi Wigderson

STOC Conference 1998 Conference Paper

Quantum vs. Classical Communication and Computation

• Harry Buhrman
• Richard Cleve
• Avi Wigderson

FOCS Conference 1998 Conference Paper

Randomness vs. Time: De-Randomization under a Uniform Assumption

• Russell Impagliazzo
• Avi Wigderson

We prove that if BPP/spl ne/EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every samplable ensemble for infinitely many input sizes). This is the first derandomization result for BPP based on uniform, noncryptographic hardness assumptions. It implies the following gap in the average-instance complexities of problems in BPP: either these complexities are always sub-exponential or they contain arbitrarily large exponential functions. We use a construction of a small "pseudorandom" set of strings from a "hard function" in EXP which is identical to that used in the analogous non-uniform results described previously. However, previous proofs of correctness assume the "hard function" is not in P/poly. They give a non-constructive argument that a circuit distinguishing the pseudo-random strings from truly random strings implies that a similarly-sized circuit exists computing the "hard function". Our main technical contribution is to show that, if the "hard function" has certain properties, then this argument can be made constructive. We then show that, assuming ESP/spl sube/P/poly, there are EXP-complete functions with these properties.

FOCS Conference 1998 Conference Paper

The Quantum Communication Complexity of Sampling

• Andris Ambainis
• Leonard J. Schulman
• Amnon Ta-Shma
• Umesh V. Vazirani
• Avi Wigderson

Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f: X/spl times/Y/spl rarr/{0, 1} and a probability distribution D over X/spl times/Y, we define the sampling complexity of (f, D) as the minimum number of bits Alice and Bob must communicate for Alice to pick x/spl isin/X and Bob to pick y/spl isin/Y as well as a valve z s. t. the resulting distribution of (x, y, z) is close to the distribution (D, f(D)). In this paper we initiate the study of sampling complexity, in both the classical and quantum model. We give several variants of the definition. We completely characterize some of these tasks, and give upper and lower bounds on others. In particular this allows us to establish an exponential gap between quantum and classical sampling complexity, for the set disjointness function. This is the first exponential gap for any task where the classical probabilistic algorithm is allowed to err.

STOC Conference 1997 Conference Paper

Direct Product Results and the GCD Problem, in Old and New Communication Models

• Itzhak Parnafes
• Ran Raz
• Avi Wigderson

STOC Conference 1997 Conference Paper

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma

• Russell Impagliazzo
• Avi Wigderson

STOC Conference 1997 Conference Paper

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus

• Alexander A. Razborov
• Avi Wigderson
• Andrew Chi-Chih Yao

STOC Conference 1997 Conference Paper

SL <= L 4/3

• Roy Armoni
• Amnon Ta-Shma
• Avi Wigderson
• Shiyu Zhou

FOCS Conference 1996 Conference Paper

Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles

• Roy Armoni
• Michael E. Saks
• Avi Wigderson
• Shiyu Zhou

A common subproblem of DNF approximate counting and derandomizing RL is the discrepancy problem for combinatorial rectangles. We explicitly construct a poly(n)-size sample space that approximates the volume of any combinatorial rectangle in [n]/sup n/ to within o(1) error. The construction extends the previous techniques for the analogous hitting set problem, most notably via discrepancy preserving reductions.

STOC Conference 1996 Conference Paper

Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs

• László Babai
• Anna Gál
• János Kollár
• Lajos Rónyai
• Tibor Szabó
• Avi Wigderson

FOCS Conference 1995 Conference Paper

Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version)

• Noam Nisan
• Avi Wigderson

We describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials and iterated matrix products.

STOC Conference 1995 Conference Paper

On data structures and asymmetric communication complexity

• Peter Bro Miltersen
• Noam Nisan
• Muli Safra
• Avi Wigderson

STOC Conference 1995 Conference Paper

On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern

• Noam Nisan
• Avi Wigderson

FOCS Conference 1994 Conference Paper

On Rank vs. Communication Complexity

• Noam Nisan
• Avi Wigderson

This paper concerns the open problem of Lovasz and Saks (1988) regarding the relationship between the communication complexity of a Boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems. >

STOC Conference 1994 Conference Paper

On the power of finite automata with both nondeterministic and probabilistic states (preliminary version)

• Anne Condon
• Lisa Hellerstein
• Samuel Pottle
• Avi Wigderson

STOC Conference 1994 Conference Paper

Pseudorandomness for network algorithms

• Russell Impagliazzo
• Noam Nisan
• Avi Wigderson

STOC Conference 1994 Conference Paper

The amazing power of pairwise independence (abstract)

• Avi Wigderson

STOC Conference 1994 Conference Paper

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing

• Oded Goldreich 0001
• Avi Wigderson

STOC Conference 1993 Conference Paper

Characterizing non-deterministic circuit size

• Mauricio Karchmer
• Avi Wigderson

STOC Conference 1993 Conference Paper

Expanders that beat the eigenvalue bound: explicit construction and applications

• Avi Wigderson
• David Zuckerman

TCS Journal 1993 Journal Article

On read-once threshold formulae and their randomized decision tree complexity

• Rafi Heiman
• Ilan Newman
• Avi Wigderson

TC0 is the class functions computable by polynomial-size, constant-depth formulae with threshold gates. Read-once TC 0 (RO-TC 0) is the subclass of TC0 which restricts every variable to occur exactly once in the formula. Our main result is a (tight) linear lower bound on the randomized decision tree complexity of any function in RO-TC0. This relationship between threshold circuits and decision trees bears significance on both models of computation. Regarding decision trees, this is the first class of functions for which such a strong bound is known. Regarding threshold circuits, it may be considered as a possible first step towards proving TC 0 ≠ NC 1; generalizing our lower bound to all functions in TC0 would establish this separation. Another structural result we obtain is that a read-once threshold formula uniquely represents the function it computes.

FOCS Conference 1992 Conference Paper

Quadratic Dynamical Systems (Preliminary Version)

• Yuri Rabinovich
• Alistair Sinclair
• Avi Wigderson

The paper promotes the study of computational aspects, primarily the convergence rate, of nonlinear dynamical systems from a combinatorial perspective. The authors identify the class of symmetric quadratic systems. Such systems have been widely used to model phenomena in the natural sciences, and also provide an appropriate framework for the study of genetic algorithms in combinatorial optimisation. They prove several fundamental general properties of these systems, notably that every trajectory converges to a fixed point. They go on to give a detailed analysis of a quadratic system defined in a natural way on probability distributions over the set of matchings in a graph. In particular, they prove that convergence to the limit requires only polynomial time when the graph is a tree. This result demonstrates that such systems, though nonlinear, are amenable to quantitative analysis. >

MFCS Conference 1992 Invited Paper

The Complexity of Graph Connectivity

• Avi Wigderson

Abstract In this paper we survey the major developments in understanding the complexity of the graph connectivity problem in several computational models, and highlight some challenging open problems.

FOCS Conference 1992 Conference Paper

Undirected Connectivity in O(log ^1. 5 n) Space

• Noam Nisan
• Endre Szemerédi
• Avi Wigderson

The authors present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log/sup 1. 5/n) space. Thus, the recursive doubling technique of Savich (1970) which requires Theta (log/sup 2/n) space is not optimal for this problem. >

STOC Conference 1991 Conference Paper

Rounds in Communication Complexity Revisited

• Noam Nisan
• Avi Wigderson

FOCS Conference 1991 Conference Paper

Search Problems in the Decision Tree Model (Preliminary Version)

• László Lovász 0001
• Moni Naor
• Ilan Newman
• Avi Wigderson

The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the CNF search problem is complete for all the variants of decision trees. It is then shown that the gaps between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. The special case of nondeterministic complexity is discussed. >

STOC Conference 1991 Conference Paper

Self-Testing/Correcting for Polynomials and for Approximate Functions

• Peter Gemmell
• Richard J. Lipton
• Ronitt Rubinfeld
• Madhu Sudan 0001
• Avi Wigderson

STOC Conference 1990 Conference Paper

Monotone Circuits for Matching Require Linear Depth

• Ran Raz
• Avi Wigderson

STOC Conference 1990 Conference Paper

Not All Keys Can Be Hashed in Constant Time (Preliminary Version)

• Joseph Gil
• Friedhelm Meyer auf der Heide
• Avi Wigderson

STOC Conference 1990 Conference Paper

On the Power of Randomization in Online Algorithms (Extended Abstract)

• Shai Ben-David
• Allan Borodin
• Richard M. Karp
• Gábor Tardos
• Avi Wigderson

FOCS Conference 1989 Conference Paper

Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract)

• Aviad Cohen 0001
• Avi Wigderson

The use of highly expanding bipartite multigraphs (called dispersers) to reduce greatly the error of probabilistic algorithms at the cost of few additional random bits is treated. Explicit constructions of such graphs are generalized and used to obtain the following results: (1) The error probability of any RP (BPP) algorithm can be made exponentially small at the cost of only a constant factor increase in the number of random bits. (2) RP (BPP) algorithms with some weak bit fixing sources are simulated. >

FOCS Conference 1989 Conference Paper

Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)

• Ran Raz
• Avi Wigderson

The authors demonstrate an exponential gap between deterministic and probabilistic complexity and between the probabilistic complexity of monotonic and nonmonotonic relations. They then prove, as their main result, an Omega ((log n)/sup 2/) bound on the probabilistic communication complexity of monotonic st-connectivity. From this they deduce that every nonmonotonic NC/sup 1/ circuit for st-connectivity requires a constant fraction of negated input variables. >

TCS Journal 1988 Journal Article

A tradeoff between search and update time for the implicit dictionary problem

• Allan Borodin
• Faith E. Fich
• Friedhelm Meyer auf der Heide
• Eli Upfal
• Avi Wigderson

This paper proves a tradeoff between the time it takes to search for elements in an implicit dictionary and the time it takes to update the value of elements in specified locations of the dictionary. It essentially shows that if the update time is constant, then the search time is Ω(nε) for some constant ε>0.

STOC Conference 1988 Conference Paper

Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)

• Michael Ben-Or
• Shafi Goldwasser
• Avi Wigderson

FOCS Conference 1988 Conference Paper

Hardness vs. Randomness (Extended Abstract)

• Noam Nisan
• Avi Wigderson

A simple construction for a pseudorandom bit generator is presented. It stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C (e. g. P, NC, PSPACE, etc.), using an arbitrary function that is hard for C. This generator reveals an equivalence between the problems of proving lower bounds and the problem of generating good pseudorandom sequences. Combining this construction with other arguments, a number of consequences are obtained. >

STOC Conference 1988 Conference Paper

Monotone Circuits for Connectivity Require Super-logarithmic Depth

• Mauricio Karchmer
• Avi Wigderson

We prove that every monotone circuit which tests st -connectivity of an undirected graph on n nodes has depth Ω(log 2 n ). This implies a superpolynomial ( n Ω(log n) ) lower bound on the size of any monotone formula for st -connectivity. The proof draws intuition from a new characterization of circuit depth in terms of communication complexity. It uses counting arguments and Extremal Set Theory. Within the same framework, we also give a very simple and intuitive proof of a depth analogue of a theorem of Krapchenko concerning formula size lower bounds.

STOC Conference 1988 Conference Paper

Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions

• Michael Ben-Or
• Shafi Goldwasser
• Joe Kilian
• Avi Wigderson

Quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. It is important at this time to find alternative foundations to the design of secure cryptography. We introduce a new model of generalized interactive proofs as a step in this direction. We prove that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions. The generalized interactive-proof model consists of two computationally unbounded and untrusted provers, rather than one, who jointly agree on a strategy to convince the verifier of the truth of an assertion and then engage in a polynomial number of message exchanges with the verifier in their attempt to do so. To believe the validity of the assertion, the verifier must make sure that the two provers can not communicate with each other during the course of the proof process. Thus, the complexity assumptions made in previous work, have been traded for a physical separation between the two provers. We call this new model the multi-prover interactive-proof model, and examine its properties and applicability to cryptography.

STOC Conference 1987 Conference Paper

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority

• Oded Goldreich 0001
• Silvio Micali
• Avi Wigderson

FOCS Conference 1986 Conference Paper

A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications

• Nati Linial
• László Lovász 0001
• Avi Wigderson

FOCS Conference 1986 Conference Paper

On a Search Problem Related to Branch-and-Bound Procedures

• Richard M. Karp
• Michael E. Saks
• Avi Wigderson

TARK Conference 1986 Conference Paper

On Play by Means of Computing Machines

• Nimrod Megiddo
• Avi Wigderson

FOCS Conference 1986 Conference Paper

Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees

• Michael E. Saks
• Avi Wigderson

The Boolean Decision tree model is perhaps the simplest model that computes Boolean functions; it charges only for reading an input variable. We study the power of randomness (vs. both determinism and non-determinism) in this model, and prove separation results between the three complexity measures. These results are obtained via general and efficient methods for computing upper and lower bounds on the probabilistic complexity of evaluating Boolean formulae in which every variable appears exactly once (AND/OR tree with distinct leaves). These bounds are shown to be exactly tight for interesting families of such tree functions. We then apply our results to the complexity of evaluating game trees, which is a central problem in AI. These trees are similar to Boolean tree functions, except that input variables (leaves) may take values from a large set (of valuations to game positions) and the AND/OR nodes are replaced by MIN/MAX nodes. Here the cost is the number of positions (leaves) probed by the algorithm. The best known algorithm for this problem is the alpha-beta pruning method. As a deterministic algorithm, it will in the worst case have to examine all positions. Many papers studied the expected behavior of alpha-beta pruning (on uniform trees) under the unreasonable assumption that position values are drawn independently from some distribution. We analyze a randomized variant of alphabeta pruning, show that it is considerably faster than the deterministic one in worst case, and prove it optimal for uniform trees.

MFCS Conference 1986 Conference Paper

Proofs that Release Minimum Knowledge

• Oded Goldreich 0001
• Silvio Micali
• Avi Wigderson

FOCS Conference 1986 Conference Paper

Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)

• Oded Goldreich 0001
• Silvio Micali
• Avi Wigderson

In this paper we demonstrate the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff. These are probabilistic and interactive proofs that, for the members x of a language L, efficiently demonstrate membership in the language without conveying any additional knowledge. So far, zero-knowledge proofs were known only for some number theoretic languages in NP ∩ Co-NP.

STOC Conference 1985 Conference Paper

Are Search and Decision Problems Computationally Equivalent?

• Richard M. Karp
• Eli Upfal
• Avi Wigderson

STOC Conference 1985 Conference Paper

Constructing a Perfect Matching is in Random NC

• Richard M. Karp
• Eli Upfal
• Avi Wigderson

FOCS Conference 1985 Conference Paper

Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)

• Miklós Ajtai
• Avi Wigderson

We explicitly construct, for every integer n and ε ≫ 0, a family of functions (psuedo-random bit generators) fn, ε: {0, 1}nε → {0, 1}n with the following property: for a random seed, the pseudorandom output "looks random" to any polynomial size, constant depth, unbounded fan-in circuit. Moreover, the functions fn, ε themselves can be computed by uniform polynomial size, constant depth circuits. Some (interrelated) consequences of this result are given below. 1) Deterministic simulation of probabilistic algorithms. The constant depth analogues of the probabilistic complexity classes RP and BPP are contained in the deterministic complexity classes DSPACE(nε) and DTIME(2nε) for any ε ≫ 0. 2) Making probabilistic constructions deterministic. Some probablistic constructions of structures that elude explicit constructions can be simulated in the above complexity classes. 3) Approximate counting. The number of satisfying assignments to a (CNF or DNF) formula, if not too small, can be arbitrarily approximated in DSPACE(nε) and DTIME(2nε), for any ε ≫ 0. We also present two results for the special case of depth 2 circuits. They deal, respectively, with finding a satisfying assignment and approximately counting the number of assignments. For example, for 3-CNF formulas with a fixed fraction of satisfying assignmemts, both tasks can be performed in polynomial time!

FOCS Conference 1985 Conference Paper

Multi-Layer Grid Embeddings

• Alok Aggarwal
• Maria M. Klawe
• David Lichtenstein
• Nati Linial
• Avi Wigderson

In this paper we propose two new multi-layer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes "exist" only on one layer, we prove a tight area x (number of contact cuts) = Θ(n2) trade-off for embedding any degree 4 n-node planar graph in two layers. For the second model in which nodes "exist" simultaneously on all layers, we prove a number of bounds on the area needed to embed graphs using no contact cuts. For example we prove that any n-node graph which is the union of two planar subgraphs can be embedded on two layers in O(n2) area without contact cuts. This bound is tight even if more layers and an unbounded number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers in O(n1. 6) area without contact cuts. These results use some interesting new results on embedding graphs in a single layer. In particular we give an O(n2) area embedding of planar graphs such that each edge makes a constant number of turns, and each exterior vertex has a path to the perimeter of the grid making a constant number of turns. We also prove a tight Ω(n3) lower bound on the area of grid n-permutation networks.

STOC Conference 1985 Conference Paper

One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation

• Faith Ellen
• Friedhelm Meyer auf der Heide
• Prabhakar Ragde
• Avi Wigderson

In this paper we compare the power of the two most commonly used concurrent-write models of parallel computation, the COMMON PRAM and the PRIORITY PRAM. These models differ in the way they resolve write conflicts. If several processors want to write into the same shared memory cell at the same time, in the COMMON model they have to write the same value. In the PRIORITY model, they may attempt to write different values; the processor with smallest index succeeds.

FOCS Conference 1985 Conference Paper

The Complexity of Parallel Computation on Matroids

• Richard M. Karp
• Eli Upfal
• Avi Wigderson

In [KUW1] we have proposed the setting of independence systems to study the relation between the computational complexity of search and decision problems. The universal problem that captures this relation, which we termed the S-search problem, is: "Given an oracle for the input system, find a maximal independent subset in it". Many interesting and important search problems can be described by a special class of independence systems, called matroids. This paper is devoted to die complexity of the S- search problem for matroids. Our main result is a lower bound on any probabilistic algorithm for the S-search problem that acquires information about the input system by interrogating an independence oracle. We prove that the expected time of any such probabilistic algorithm that uses a sub-exponential number of processors is Ω(n1/3-ε). This is one of the first nontrivial, super-logarithmic lower bounds on a randomized parallel computation. It implies that in our model of computation Random-NC is strictly contained in P. Another consequence of the lower bound is that the O(√n) time probabilistic upper bound for arbitrary independence systems, presented in [KUW1], is close to optimal and cannot be significantly improved, even for matroids. However, fills O(√n) upper bound can be improved in a different sense for matroids -it can be made deterministic, still with polynomially many processors. Finally, we show that the lower bound can be beaten for the special case of graphic matroids. Here, the S-search problem is simply to find a spanning forest of a graph, when the algorithm cannot see the graph, but can only ask whether subsets of edges are forests or not. We give an O(logn) time deterministic parallel algoritlun that uses nO(logn) processors. From the upper bounds on parallel time above we deduce similar bounds (up to a poly-log factor) on thc sequential space required by a deterministic Turing machine with an independence oracle to solve the S-search problem.

FOCS Conference 1985 Conference Paper

The Complexity of Parallel Sorting

• Friedhelm Meyer auf der Heide
• Avi Wigderson

We consider PRAM's with arbitrary computational power for individual processors, infinitely large shared memory and "priority" writeconflict resolution. The main result is that sorting n integers with n processors requires Ω(√log n) steps in this strong model. We also show that computing any symmetric polynomial (e. g. the sum or product) of n integers requires exactly log2n steps, for any finite number of processors.

STOC Conference 1984 Conference Paper

A Fast Parallel Algorithm for the Maximal Independent Set Problem

• Richard M. Karp
• Avi Wigderson

A parallel algorithm is presented which accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n) 4 ) time and uses O((n/log n) 3 ) processors, where n is the number of vertices in G. The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.

FOCS Conference 1984 Conference Paper

How to Share Memory in a Distributed System (A Preliminary Version)

• Eli Upfal
• Avi Wigderson

We study the power of shared-memory in models of parallel computation. We describe a novel distributed data structure that eliminates the need for shared mernory without significantly increasing the run time of the parallel computation. We also show how a complete network of processors can deterministicly simulate one PRAM step in O(log n(loglog n) 2 ) time, when both models use n processors, and ttie size of the PRAM'S shared memory is polynomial in n. (The best previously known upper bound was the trivial O(n)). We also establish that this upper bound is nearly optimal. We prove that an online simulation of T PRAM steps by a complete network of processors requires Ω(Tlog n/loglog n) time.

STOC Conference 1983 Conference Paper

How Discreet is the Discrete Log?

• Douglas L. Long
• Avi Wigderson

Blum and Micali [4] showed how to hide one bit using the discrete logarithm function. In this paper we show how to hide c •loglog p bits for any constant c , where p is the modulus.

STOC Conference 1983 Conference Paper

Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)

• Danny Dolev
• Cynthia Dwork
• Nicholas Pippenger
• Avi Wigderson

FOCS Conference 1983 Conference Paper

Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version)

• Uzi Vishkin
• Avi Wigderson

A new technique for proving lower bounds for parallel computation is introduced. This technique enables us to obtain, for the first time. non-trivial tight lower bounds for shared-memory models of parallel computation that allow simultaneous read/write access to the same memory location. The size m of the common memory is called communication width or width in short. For a wide variety of problems (including parity and majority) we show that the time complexity T (depth) and the communication width m are related by the trade-off curve mT2 = Ω(n) (where n is the size of the input). This bound is tight lot every m ≤n/log2n We extend our technique to prove mT3 = Ω(n) trade-off for a class of "simpler" functions (includind Boolean Or) on a weaker model that forbids simultaneous write access. This result improves the lower bound of Cook and Dwork [CD-82] when communication is limited.

STOC Conference 1982 Conference Paper

A New Approximate Graph Coloring Algorithm

• Avi Wigderson

Let A be a graph coloring algorithm. Denote by À (G) the ratio between the maximum number of colors A will use to color the graph G, and the chromatic number of G, x (G) . For most existing polynomial coloring algorithms, À(G) can be as bad as O (n), where n is the number of vertices in G . The best currently known algorithm guarantees À (G)=O(n/ log n ). In this paper we present a simple and efficient coloring algorithm which guarantees À(G)≤x(G)n (equation), a considerable improvemėnt over the current bounds.