Spherical Cubes and Rounding in High Dimensions (2009)
Guy Kindler, Anup Rao, Avi Wigderson
What is the least surface area of a shape that tiles R d under translations by Z d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Ω ( √ d)....
Iterative construction of cayley expander graphs (2009)
Eyal Rozenman, Aner Shalev, Avi Wigderson
We construct a sequence of groups Gn, and explicit sets of generators Yn ⊂ Gn, such that all generating sets have bounded size, and the associated Cayley graphs are all expanders. The group G1 is...
Iterative construction of cayley expander graphs (2009)
Eyal Rozenman, Aner Shalev, Avi Wigderson
Abstract We construct a sequence of groups Gn, and explicit sets of generators Yn ae Gn, such that allgenerating sets have bounded size, and the associated Cayley graphs are all expanders. The group...
ABSTRACT Extractors: Optimal up to Constant Factors (2008)
Chi-jen Lu, Salil Vadhan, Omer Reingold, Avi Wigderson
This paper provides the first explicit construction of extractors which are simultaneously optimal up to constant factors in both seed length and output length. More precisely, for every n, k, our...
Michael Luby, Avi Wigderson, Trends R In
Published, sold and distributed by: now Publishers Inc.
P, NP and mathematics – a computational complexity (2008)
Avi Wigderson, Steve Smale, Avi Wigderson
perspective
A new N C Algorithm for Perfect Matchingin Bipartite Cubic Graphs (2008)
Abstract The purpose of this paper is to introduce a new approachto the problem of computing perfect matchings in fast deterministic parallel time. In particular, this approach yieldsa new algorithm...
Oded Goldreich, Siltnb Micali, Avi Wigderson
We present a polynomial-time algorithm that, given ss a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that ‘leaks...
Russell Impagliazzo, Avi Wigderson
We prove that if BPP � = 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)....
Irit Dinur, Madhu Sudan, Avi Wigderson
Abstract. Given two binary linear codes R and C, their tensor product R⊗C consists of all matrices with rows in R and columns in C. We analyze the “robustness ” of the following test for this...
Abstract P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma (2008)
Russell Impagliazzo, Avi Wigderson
Yao showed that the XOR of independent random instances of a somewhat hard Boolean problem becomes almost completely unpredictable. In this paper we show that, in non-uniform settings, total...
Computational Complexity Propositional Complexity Algorithms (2008)
Avi Wigderson, Alexander A. Razborov, Toniann Pitassi, Host Prof, Avi Wigderson
Professional Experience
References Computational Pseudo-Randomness (2008)
One of the most important and fundamental discover-ies of Theoretical Computer Science is the surprising connection between the computational power of ran-domness, and computational lower bounds on...
ON PLAY BY MEANS OF COMPUTING MACHINES (preliminary version) (2008)
Nimrod Megiddo T, Avi Wigderson
Abstract. This paper examines the "bounded rationality " inherent in play by means of computing machines. The main example is the finitely repcated prisoners ' dilemma game...
Abstract Pseudorandomness for Network Algorithms (2008)
Russell Impagliazzo, Noam Nisan, Avi Wigderson
We define pseudorandom generators for Yao’s twoparty communication complexity model and exhibit a simple construction, based on expanders, for it. We then use a recursive composition of such...
General Terms " Algorithms, Theory (2008)
Abstract. The performance guarantee of a graph coloring algorithm is the worst case ratio between the number of colors it uses on the input graph and the chromauc number of this graph. The previous...
NP and Mathematics - a computational complexity perspective (2008)
“P versus N P – a gift to mathematics from Computer Science”
Mauricio Karchmer, Ran Raz, Avi Wigderson
Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach...
NP and Mathematics - a computational complexity perspective (2008)
“P versus N P – a gift to mathematics from computer science”
Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
Abstract. We prove that two-party randomized communication complexity satisfies a strong direct product property, so long as the communication lower bound is proved by a “corruption ” or...
Boaz Barak, Guy Kindler, Benny Sudakov, Avi Wigderson
A distribution X over binary strings of length n has minentropy k if every string has probability at most 2 −k in X. 1 We say that X is a δ-source if its rate k/n is at least δ. We give the...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2008)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Public Key Cryptography from Different Assumptions (2008)
We construct a new public key encryption based on two assumptions: 1. One can obtain a pseudorandom generator with small locality by connecting the outputs to the inputs using any sufficiently good...
Spherical Cubes and Rounding in High Dimensions (2008)
Guy Kindler, Anup Rao, Avi Wigderson
What is the least surface area of a shape that tiles R d under translations by Z d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Ω ( √ d)....
Mauricio Karchmer, Mike Saks, Avi Wigderson, Ilan Newman, Ilan Newman
Proposed running title: Nondet communication comp. Mailing address:
Roy Armoni, Amnon Ta-shma, Avi Wigderson, Shiyu Zhou
We present a deterministic algorithm that computes st-connectivity in undirected graphs using O(log 4=3 n) space. This improves the previous O(log 3=2 n) bound of Nisan, Szemer'edi and Wigderson...
Undirected Connectivity in (2007)
Log Space Noam, Noam Nisan, Endre Szemeredi, Avi Wigderson
We present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log 1:5 n) space. Thus, the recursive doubling technique of Savich which requires O(log 2 n)...
Undirected Connectivity in O(log^1.5 n) Space (2007)
Noam Nisan, Endre Szemeredi, Avi Wigderson
We present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log^1.5 n) space. Thus, the recursive doubling technique of Savich which requires...
Theory of Computing: A Scientific Perspective (2007)
Preliminary Version, Oded Goldreich, Avi Wigderson
We are gravely concerned with the contents, spirit and recommendations in the Aho et. al. Report on the Theory of Computing (TOC). This report "assesses the current goals and directions of the...
Oded Goldreich, Avi Wigderson, Givat Ram
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
Eli Ben-sasson, Russell Impagliazzo, Avi Wigderson
We present the best known separation between tree-like and general resolution, improving on the recent exp(n) separation of [BEGJ98]. This is done by constructing a natural family of contradictions,...
Chi-jen Lu, Omer Reingold, Salil Vadhan, Avi Wigderson
This paper provides the first explicit construction of extractors which are simultaneously optimal up to constant factors in both seed length and output length. More precisely, for every n, k, our...
Peter Bro Miltersen, Noam Nisan, Avi Wigderson
In this paper we consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication...
Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets (2007)
Eli Ben-sasson, Madhu Sudan, Cambridge Ma, Salil 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 almostlinear (= n ) size. Such...
Roy Armoni, Amnon Ta-shma, Avi Wigderson, Shiyu Zhou
Abstract. We present a deterministic algorithm that computes st-connectivity in undirected graphs using O(log
The Randomized Communication Complexity of Set Disjointness (2007)
Abstract: We study the communication complexity of the disjointness function, in which each of two players holds a k-subset of a universe of size n and the goal is to determine whether the sets are...
Algebrization: A new barrier in complexity theory (2007)
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...
Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols (2007)
This paper presents a unified and simple treatment of basic questions concerning two computational models: multiparty communication complexity and GF (2) polynomials. The key is the use of (known)...
Extractors and rank extractors for polynomial sources (2007)
Zeev Dvir, Ariel Gabizon, Avi Wigderson
In this paper we construct explicit deterministic extractors from polynomial sources, which are distributions sampled by low degree multivariate polynomials over finite fields. This naturally...
Uniform direct product theorems: Simplified, unified and derandomized (2007)
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...
Algebrization: A new barrier in complexity theory (2007)
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...
One-way multi-party communication lower bound for pointer jumping with applications (2007)
with applications
Computational Hardness and Explicit Constructions of Error Correcting Codes (2006)
Cheraghchi, Mahdi, Shokrollahi, Amin, Wigderson, Avi
We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a polynomial time...
Ahlswede and Winter [AW02] introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We...
Paul Beame, Nathan Segerlind, Toniann Pitassi, Avi Wigderson
We prove that two-party randomized communication complexity satisfies a strong direct product property, so long as the communication lower bound is proved by a “corruption ” or “one-sided...
Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson, Startup Grant
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 × N...
Boaz Barak, Ronen Shaltiel, Anup Rao, 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 × N...
DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- (2006)
Shlomo Hoory, Nathan Linial, Avi Wigderson, An Overview
A major consideration we had in writing this survey was to make it accessible to mathematicians as well as computer scientists, since expander graphs, the protagonists of our story come up in...
Expander graphs and their applications (2006)
Shlomo Hoory, Nathan Linial, Avi Wigderson, An Overview
A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, come up in...
DRAFT-- DRAFT-- DRAFT-- DRAFT-- DRAFT-- (2006)
Shlomo Hoory, Nathan Linial, Avi Wigderson, An Overview
A major consideration we had in writing this survey was to make it accessible to mathematicians as well as computer scientists, since expander graphs, the protagonists of our story come up in...
Computational Hardness and Explicit Constructions of Error Correcting Codes (2006)
Mahdi Cheraghchi, Amin Shokrollahi, Avi Wigderson
Abstract — We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a...
Russell Impagliazzo, Avi Wigderson, Ronen Shaltiel
The Nisan-Wigderson pseudo-random generator [NW94] was constructed to derandomize probabilistic algorithms under the assumption that there exist explicit functions which are hard for small circuits....
Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson
The main result of this paper is an explicit disperser for two independent sources on n bits, each of min-entropy k = 2 log1−α 0 n, for some small absolute constant α0> 0). Put differently,...
Thoughts on noise and quantum computing (2005)
Gil Kalai, Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
A randomness-efficient sampler for matrix-valued functions and applications (2005)
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...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2005)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
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. 1 X is called a δ-source if its rate k/n is at least δ. We give the following...
A randomness-efficient sampler for matrix-valued functions and applications (2005)
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...
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
We present new explicit constructions of deterministic randomness extractors, dispersers and related objects. More precisely, a distribution X over binary strings of length n is called a δ-source if...
Entropy waves, the zig-zag graph product, and new constant-degree (2004)
Reingold, Omer, Vadhan, Salil, Wigderson, Avi
The main contribution of this work is a new type of graph product, which we call the {\it zig-zag product}. Taking a product of a large graph with a small graph, the resulting graph inherits...
Derandomizing Homomorphism Testing in General Groups (2004)
1993). We show that for any groups G and \Gamma, and any expanding generating set S of G, the naturalderamdomized version of the BLR test in which we pick an element x randomly from G and y ran-domly...
Extracting randomness using few independent sources (2004)
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 δ> 0 we give an explicit construction...
Extracting randomness using few independent sources (2004)
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 δ> 0 we give an explicit construction...
Derandomizing Homomorphism Testing in General Groups (2004)
The main result of this paper is a near-optimal derandomization of the affine homomorphism test of Blum, Luby and Rubinfeld (Journal of Computer and System Sciences, 1993). We show that for any...
The quantum communication complexity of sampling (2003)
Ambainis, Andris, Schulman, Leonard J., Ta-Shma, Amnon, Vazirani, Umesh, Wigderson, Avi
Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f : X × Y → {0, 1} and a probability distribution D over X...
Computational analogues of entropy (2003)
Boaz Barak, Ronen Shaltiel, Avi Wigderson
Abstract. Min-entropy is a statistical measure of the amount of randomness that a particular distribution contains. In this paper we investigate the notion of computational min-entropy which is the...
Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets (2003)
Eli Ben-sasson, Madhu Sudan, Cambridge Ma, Salil 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 almostlinear (= n ) size. Such...
vices. Monotone Circuits for Matching Require Linear Depth (2003)
We prove that monotone circuits computing the perfect match-ing function on n-vertex graphs require Ω(n) depth. This implies an exponential gap between the depth of monotone and nonmonotone...
Computational analogues of entropy (2003)
Boaz Barak, Ronen Shaltiel, Avi Wigderson
Min-entropy is a statistical measure of the amount of randomness that a particular distribution contains. In this paper we investigate the notion of computational min-entropy which is the...
Entropy waves, the zig-zag graph product, and new constant-degree expanders (2002)
Reingold, Omer, Vadhan, Salil, Wigderson, Avi
The main contribution of this work 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...
Russell Impagliazzo, Avi Wigderson, Valentine Kabanets
Restricting the search space {0, 1} n to the set of truth tables of “easy ” Boolean functions on log n variables, as well as using some known hardness-randomness tradeoffs, we establish a number...
Derandomization That is Rarely Wrong From Short Advice That is Typically Good (2002)
For every ffl ? 0, we present a deterministic log-space algorithm that correctly decides undirected graph connectivity on all but at most 2 of the n-vertex graphs. The same holds for every problem in...
Pseudorandom Generators in Propositional Proof Complexity (2002)
Michael Alekhnovich, Eli Ben-sasson, Alexander A. Razborov, Avi Wigderson
We call a pseudorandom generator G n : f0; 1g hard for a propositional proof system P if P can not eciently prove the (properly encoded) statement G n (x 1 ; : : : ; x n ) 6= b for any string b 2 f0;...
One-Way Functions are Essential for Non-Trivial Zero-Knowledge (Extended Abstract) (2002)
Rafail Ostrovsky, Avi Wigderson
Rafail Ostrovsky # Avi Wigderson + April 25, 2002 Abstract It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in . We prove that unless very weak...
Computing Graph Properties By Randomized Subcube Partitions (2002)
Ehud Friedgut, Jeff Kahn, Avi Wigderson
We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of...
Computing Graph Properties by Randomized Subcube Partitions (2002)
Ehud Friedgut, Jeff Kahn, Avi Wigderson
We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of...
Simple Analysis of Graph Tests for Linearity and PCP (2001)
We give a simple analysis of the PCP with low amortized query complexity of Samorodnitsky and Trevisan [16]. The analysis also applies to the linearity testing over nite elds, giving a better...
Depth-3 Arithmetic Circuits Over Fields of Characteristic Zero (2001)
In this paper we prove quadratic lower bounds for depth-3 arithmetic circuits over elds of characteristic zero. Such bounds are obtained for the elementary symmetric functions, the (trace of)...
Short Proofs are Narrow - Resolution made Simple (2001)
The width of a Resolution proof is de ned to be the maximal number of literals in any clause of the proof. In this paper we relate proof width to proof length (=size), in both general Resolution, and...
Simple Analysis of Graph Tests for Linearity and PCP (2001)
Abstract We give a simple analysis of the PCP with low amortized query complexity of Samorodnitsky and Trevisan [16]. The analysis also applies to the linearity testing over finite fields, giving a...
Michael Capalbo, Omer Reingold, Salil 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:...
Near-optimal separation of treelike and general resolution (2000)
Eli Ben-sasson, Russell Impagliazzo, Avi Wigderson
We present the best known separation between tree-like and general resolution, improving on the recent exp(n) separation of [BEGJ98]. This is done by constructing a natural family of contradictions,...
Simplified derandomization of BPP using a hitting set generator (2000)
Oded Goldreich, Salil Vadhan, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
Simplified derandomization of BPP using a hitting set generator (2000)
Oded Goldreich, Salil Vadhan, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors (2000)
Omer Reingold, Salil Vadhan, Avi Wigderson
The main contribution of this work 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...
Pseudorandom Generators in Propositional Proof Complexity (2000)
Michael Alekhnovich, Eli Ben-sasson, Alexander A. Razborov, Avi Wigderson
We call a pseudorandom generator Gn : {0, 1}^n → {0, 1}^m hard for a propositional proof system P if P can not efficiently prove the (properly encoded) statement G(x1, ..., xn) ≠ b...
Extracting Randomness via Repeated Condensing (2000)
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...
Simplified derandomization of BPP using a hitting set generator (2000)
Oded Goldreich Salil, Oded Goldreich, Salil Vadhan, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
Space Complexity in Propositional Calculus (2000)
Michael Alekhnovich, Eli Ben-sasson, Alexander A. Razborov, Avi Wigderson
We study space complexity in the framework of propositional proofs. We consider a natural model analogous to Turing machines with a read-only input tape, and such popular propositional proof systems...
Near-Optimal Separation of Treelike and General Resolution (2000)
Eli Ben-sasson, Russell Impagliazzo, Avi Wigderson
We present the best known separation between tree-like and general resolution, improving on the recent exp(n ) separation of [BEGJ98]. This is done by constructing a natural family of contradictions,...
On Pseudorandomness with respect to Deterministic Observers (2000)
Oded Goldreich, Rehovot Israel, Avi Wigderson
In the theory of pseudorandomness, potential (uniform) observers are modeled as probabilistic polynomial-time machines. In fact many of the central results in that theory are proven via probabilistic...
Pseudorandom Generators in Propositional Proof Complexity (2000)
Michael Alekhnovich, Eli Ben-sasson, Alexander A. Razborov, Avi Wigderson
We call a pseudorandom generator G n : f0; 1g n ! f0; 1g m hard for a propositional proof system P if P can not efficiently prove the (properly encoded) statement G n (x 1 ; : : : ; x n ) 6= b for...
Extracting randomness via repeated condensing (2000)
Omer Reingold, Ronen Shaltiel, Avi Wigderson
Extractors (defined by Nisan and Zuckerman) are procedures that use a small number of truly random bits (called the seed) to extract many (almost) truly random bits from arbitrary distributions as...
Near-optimal conversion of hardness into pseudo-randomness (1999)
Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
Various efforts ([3, 5, 6, 9]) have been made in recent years to derandomize probabilistic algorithms using the complexity theoretic assumption that there exists a problem in E = dtime(2 O(n)), that...
Improved derandomization of BPP using a hitting set generator (1999)
Oded Goldreich, Rehovot Israel, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
Short proofs are narrow - resolution made simple (1999)
The width of a Resolution proof is dened to be the maximal number of literals in any clause of the proof. In this paper we relate proof width to proof length (=size), in both general Resolution, and...
Expanders that beat the eigenvalue bound: Explicit construction and applications (1999)
Avi Wigderson, David Zuckerman
For every n and 0! ffi! 1, we construct graphs on n nodes such that every two sets of size n ffi share an edge, having essentially optimal maximum degree n 1\Gammaffi+o(1). Using known and new...
Space Complexity in Propositional Calculus (1999)
Michael Alekhnovich Eli, Eli Ben-sasson, Alexander A. Razborov, Avi Wigderson
We study space complexity in the framework of propositional proofs. We consider a natural model analogous to Turing machines with a read-only input tape, and such popular propositional proof systems...
Optimal seperation of Treelike and General Resolution (1999)
Eli Ben-sasson, Russell Impagliazzo, Avi Wigderson
We present the best known separation between tree-like and general resolution, improving on the recent exp(n ffl ) separation of [BEGJ98]. This is done by constructing a natural family of...
Near-Optimal conversion of Hardness into Pseudo-Randomness (1999)
Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
Various efforts ([3, 5, 6, 9]) have been made in recent years to derandomize probabilistic algorithms using the complexity theoretic assumption that there exists a problem in E = dtime(2 O(n) ), that...
Deterministic Amplification of Space-Bounded Probabilistic Algorithms (1999)
Ziv Bar-yossef, Oded Goldreich, Avi Wigderson
This paper initiates the study of deterministic amplification of space-bounded probabilistic algorithms. The straightforward implementations of known amplification methods cannot be used for such...
Depth-3 arithmetic formulae over fields of characteristic zero (1999)
In this paper we prove near quadratic lower bounds for depth-3 arithmetic formulae over fields of characteristic zero. Such bounds are obtained for the elementary symmetric functions, the (trace of)...
Quantum vs. Classical Communication and Computation (1998)
Buhrman, Harry, Cleve, Richard, Wigderson, Avi
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
On data structures and asymmetric communication complexity (1998)
Peter Bro Miltersen, Peter Bro Miltersen, Noam Nisan, Noam Nisan, Avi Wigderson, Avi Wigderson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
The quantum communication complexity of sampling (1998)
Andris Ambainis, Leonard J. Schulman, Amnon Ta-shma, Umesh Vazirani, Avi Wigderson, Over X
Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f: X
The quantum communication complexity of sampling (1998)
Andris Ambainis, Leonard J. Schulman, Amnon Ta-shma, Umesh Vazirani, Avi Wigderson
Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f: X \Theta Y! f0; 1g and a probability distribution D over X...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Quantum vs. Classical Communication and Computation (1998)
Harry Buhrman, Richard Cleve, Avi Wigderson
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
Randomness vs. Time: De-randomization under a uniform assumption (1998)
Russell Impagliazzo, Avi Wigderson
We prove that if BPP 6= 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)....
Quantum vs. Classical Communication and Computation (1998)
Harry Buhrman, Richard Cleve, Avi Wigderson
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
The Quantum Communication Complexity of Sampling (1998)
Andris Ambainis, Leonard J. Schulman, Amnon Ta-shma, Umesh Vazirani, Avi Wigderson
Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f : X \Theta Y ! f0; 1g and a probability distribution D over X...
On the Circuit Complexity of Perfect Hashing (1998)
Oded Goldreich, Rehovot Israel, Avi Wigderson, Givat Ram
We consider the size of circuits which perfectly hash an arbitrary subset S ae f0; 1g n of cardinality 2 k into f0; 1g m . We observe that, in general, the size of such circuits is exponential in 2k...
On data structures and asymmetric communication complexity (1998)
Peter Bro Miltersen, Noam Nisan, Peter Bro, Miltersen Noam, Nisan Shmuel Safra, Avi Wigderson, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
How to Share Memory in a Distributed System. (1997)
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 memory without significantly increasing the...
Direct Product Results and the GCD Problem, in Old and New Communication Models (1997)
Itzhak Parnafes Ran, Ran Raz, Avi Wigderson
This paper contains several results regarding the communication complexity model and the 2-prover games model, which are based on interaction between the two models: 1. We show how to improve the...
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1997)
Oded Goldreich, Avi Wigderson, Givat Ram
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
Composition of the Universal Relation (1997)
We prove that the communication complexity of the k-fold composition of the universal relation on n bits is (1 \Gamma o(1))kn when k = o( p n= log n). Warning: Essentially this paper has been...
P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma (1997)
Russell Impagliazzo, Avi Wigderson
Yao showed that the XOR of independent random instances of a somewhat hard Boolean problem becomes almost completely unpredictable. In this paper we show that, in non-uniform settings, total...
Alexander Razborov, Avi Wigderson, Andrew Yao
We investigate read-once branching programs for the following search problem: given a Boolean m \Theta n matrix with m ? n, find either an all-zero row, or two 1's in some column. Our primary...
Alexander Razborov, Avi Wigderson, Andrew Yao
We investigate read-once branching programs for the following search problem: given a Boolean m \Theta n matrix with m ? n, find either an all-zero row, or two 1's in some column. Our primary...
Direct Product Results and the GCD Problem, in Old and New Communication Models (1997)
Itzhak Parnafes, Ran Raz, Avi Wigderson
This paper contains several results regarding the communication complexity model and the 2-prover games model, which are based on interaction between the two models: 1. We show how to improve the...
Lower Bounds on Arithmetic Circuits Via Partial Derivatives (1996)
Noam Nisan, Noam Nisan, Avi Wigderson, Avi Wigderson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Russell Impagliazzo, Avi Wigderson
Yao showed that the XOR of independent random instances of a somewhat hard Boolean function becomes almost completely unpredictable. In this paper we show that, in non-uniform settings, total...
Theory of Computing: A Scientific Perspective (1996)
We are gravely concerned with the contents, spirit and recommendations in the Aho et. al. Report on the Theory of Computing (TOC). This report "assesses the current goals and directions of the...
Lower Bounds on Formula Size of Boolean Functions using Hypergraph-Entropy (1996)
Korner [7] defined the notion of graph-entropy. He used it in [8] to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information...
Derandomized Graph Products (1996)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
Berman and Schnitger [10] gave a randomized reduction from approximating MAXSNP problems [24] within constant factors arbitrarily close to 1 to approximating clique within a factor of n^ε...
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles (1996)
Roy Armoni, Michael 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...
Superpolynomial Lower Bounds for Monotone Span Programs (1996)
László Babai, Anna Gál, Avi Wigderson
In this paper we obtain the first superpolynomial lower bounds for monotone span programs computing explicit functions. The best previous lower bound was \Omega\Gamma n 5=2 ) by Beimel, G'al,...
Monotone Circuits for Matching Require Linear Depth (1996)
We prove that monotone circuits computing the perfect matching function on n-vertex graphs require\Omega\Gamma n) depth. This implies an exponential gap between the depth of monotone and nonmonotone...
Lower Bounds on Arithmetic Circuits Via Partial Derivatives (1996)
In this paper we describe a new technique for obtaining lower bounds on restricted classes of nonmonotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate...
Discrepancy sets and pseudorandom generators for combinatorial rectangles (1996)
Roy Armoni, Michael 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...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Information Theory versus Complexity Theory: Another Test Case (1995)
Ivan Damgård, Oded Goldreich, Avi Wigderson
A few cases are known where the computational analogue of some basic information theoretical results is much harder to prove or even not known to hold. A notable example is Yao's XOR Lemma....
Pairwise Independence and Derandomization (1995)
This set of notes gives several applications of the following paradigm. The paradigm consists of two complementary parts. The first part is to design a probabilistic algorithm described by a sequence...
Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version) (1995)
In this paper we describe a new technique for obtaining lower bounds on restriced classes of nonmonotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate...
Lower Bounds on Formula Size of Boolean Functions using Hypergraph-Entropy (1995)
Korner [7] defined the notion of graph-entropy. He used it in [8] to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information...
Boolean Complexity Classes Vs. Their Arithmetic Analogs (1995)
This paper provides logspace and small circuit depth analogs of the result of Valiant-Vazirani, which is a randomized (or nonuniform) reduction from NP to its arithmetic analog \PhiP . We show a...
Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs (1995)
Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson
This paper presents two transformations of public-coin/Arthur-Merlin proof systemswhich are zero-knowledge with respect to the honest verifier into (public-coin/ArthurMerlin) proof systems which are...
Pairwise Independence and Derandomization (1995)
This set of notes gives several applications of the following paradigm. The paradigm consists of two complementary parts. The first part is to design a probabilistic algorithm described by a sequence...
Derandomized Graph Products (1995)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
. Berman and Schnitger gave a randomized reduction from approximating MAX-SNP problems within constant factors arbitrarily close to 1 to approximating clique within a factor of n ffl (for some ffl)....
Abstract This set of notes gives several applications of the following paradigm. The paradigm consists of two complementary parts. The first part is to design a probabilistic algorithm described by a...
Honest verifier vs. dishonest verifier in public coin zeroknowledge proofs (1995)
Tatsuaki Okamoto ¢ This paper presents two transformations of public-coin/Arthur-Merlin proof systems which are zero-knowledge with respect to the honest verifier into (public-coin/Arthur-Merlin)...
Lower bounds on formula size of Boolean functions using hypergraph entropy (1995)
Körner [7] defined the notion of graph-entropy. He used it in [8] to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information...
Derandomized Graph Products (1995)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
Berman and Schnitger [10] gave a randomized reduction from approximating MAX-SNP problems [24] within constant factors arbitrarily close to 1 to approximating clique within a factor of n ɛ (for some...
Hashing functions can simplify zero-knowledge protocol design (too (1994)
Ivan Damg Ard, Ivan Damgard, Oded Goldreich, Oded Goldreich, Avi Wigderson, Avi Wigderson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Hashing functions can simplify zero-knowledge protocol design (too (1994)
Ivan Damgard, Oded Goldreich, Avi Wigderson
In Crypto93, Damgard showed that any constant-round protocol in which the verifier sends only independent, random bits and which is zero-knowledge against the honest verifier can be transformed into...
On Read-Once Threshold Formulae and their Randomized Decision Tree Complexity (1994)
Rafi Heiman, Ilan Newman, Avi Wigderson
TC 0 is the class of functions computable by polynomial-size, constant- depth formulae with threshold gates. Read-Once TC 0 (RO-TC 0 ) is the subclass of TC 0 which restricts every variable to occur...
Search Problems in the Decision Tree Model (1994)
Laszlo Lovasz, Moni Naor, Ilan Newman, Avi Wigderson
We study the relative power of determinism, randomness and nondeterminism for search problems in the Boolean decision tree model. We show that the gaps between the nondeterministic, the randomized...
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
On the Complexity of Bilinear Forms (Extended Abstract) (1994)
) Noam Nisan y Institute of Computer Science, Hebrew University of Jerusalem, Israel. Avi Wigderson z Institute of Computer Science, Hebrew University of Jerusalem, Israel. November 29, 1994 Abstract...
On Rank vs. Communication Complexity (1994)
. This paper concerns the open problem of Lovasz and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an...
Pseudorandomness for Network Algorithms (1994)
Russell Impagliazzo, Noam Nisan, Avi Wigderson
We define pseudorandom generators for Yao's twoparty communication complexity model and exhibit a simple construction, based on expanders, for it. We then use a recursive composition of such...
On the Power of Finite Automata with both Nondeterministic and Probabilistic States (1994)
Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson
We study finite automata with both nondeterministic and random states (npfa's). We restrict our attention to those npfa's that accept their languages with a small probability of error and...
Pseudorandomness for Network Algorithms (1994)
Russell Impagliazzo, Noam Nisan, Avi Wigderson
We define pseudorandom generators for Yao's twoparty communication complexity model and exhibit a simple construction, based on expanders, for it. We then use a recursive composition of such...
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1994)
Oded Goldreich, Avi Wigderson, Givat Ram
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1994)
.We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
On the Power of Finite Automata with both Nondeterministic and Probabilistic States (1994)
Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson
We study finite automata with both nondeterministic and random states (npfa's). We restrict our attention to those npfa's that accept their languages with a small probability of error and...
Non-deterministic communication complexity with few witnesses (1994)
Mauricio Karchmer, Ilan Newman, Mike Saks, Avi Wigderson
We study non-deterministic communication protocols in which no input has too many witnesses. Define nk(f) to be the minimum complexity of a non-deterministic protocol for the function f in which each...
Hashing functions can simplify zero-knowledge protocol design (too (1994)
Oded Goldreich, Oded Goldreich, Avi Wigderson, Avi Wigderson
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Universal traversal sequences for expander graphs (1993)
connectivity, computational complexity, expander graphs.
Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications (1993)
Avi Wigderson, David Zuckerman
For every n and 0 ! ffi ! 1, we construct graphs on n nodes such that every two sets of size n ffi share an edge, having essentially optimal maximum degree n 1\Gammaffi+o(1) . We use them to...
One-Way Functions are Essential for Non-Trivial Zero-Knowledge (1993)
Exte Nd Ed, Rafail Ostrovsky, Avi Wigderson
) Rafail Ostrovsky y Avi Wigderson z TR-93-073 Novemeber, 1993 Abstract It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. We prove that...
Deterministic Approximate Counting of Depth-2 Circuits (1993)
Michael Luby, Boban Velickovic, Avi Wigderson
We describe deterministic algorithms which for a given depth-2 circuit F approximate the probability that on a random input F outputs a specific value α. Our approach gives an algorithm...
BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs (1993)
László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson, Ma P
. We show that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time ffi collapses to the second level of the polynomial-time hierarchy, ffi has...
One-Way Functions are Essential for Non-Trivial Zero-Knowledge (Extended Abstract) (1993)
R. Ostrovsky, Rafail Ostrovsky, Avi Wigderson
) Rafail Ostrovsky y Avi Wigderson z Abstract It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE . We prove that unless very weak one-way...
Lower Bounds on the Size of Depth 3 (1993)
Threshold Circuits With, Alexander Razborov, Avi Wigderson
We present a function in ACC such that any depth 3 threshold circuit which computes this function and has AND gates at the bottom must have size n 607 .
The Fusion Method for Lower Bounds in Circuit Complexity (1993)
This paper coins the term "The Fusion Method" to a recent approach for proving circuit lower bounds. It describes the method, and surveys its achievements, potential and challenges. 1...
Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom (1993)
Alexander Razborov, Avi Wigderson
We present a function in ACC 0 such that any depth 3 threshold circuit which computes this function and has AND gates at the bottom must have size n\Omega\Gamma607 n) . Key words. computational...
Laszlo Babai, Noam Nissan, Lance Fortnow, Avi Wigderson
) L'aszl'o Babai Noam Nisan y Lance Fortnow z Avi Wigderson University of Chicago Hebrew University Abstract We show that BPP can be simulated in subexponential time for infinitely many...
One-way Functions are Essential for Non-Trivial Zero-Knowledge (1993)
Rafail Ostrovsky, Avi Wigderson
It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. We prove that unless very weak one-way functions exist, Zero-Knowledge proofs can be...
Quadratic Dynamical Systems (Preliminary Version) (1992)
Yuri Rabinovich, Alistair Sinclair, Avi Wigderson
The main purpose of this paper is to promote the study of computational aspects, primarily the convergence rate, of nonlinear dynamical systems from a combinatorial perspective. We identify the class...
Quadratic Dynamical Systems (Preliminary Version) (1992)
Yuri Rabinovich, Alistair Sinclair, Avi Wigderson
The main purpose of this paper is to promote the study of computational aspects, primarily the convergence rate, of nonlinear dynamical systems from a combinatorial perspective. We identify the class...
The complexity of graph connectivity (1992)
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. 1
Super-Logarithmic Depth Lower Bounds Via The Direct Sum In Communication Complexity (1991)
Mauricio Karchmer, Ran Raz, Avi Wigderson, From Monotone P
. Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an...
Mauricio Karchmer, Ran Raz, Avi Wigderson
Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach...
Self-Testing/Correcting for Polynomials and for Approximate Functions (1991)
Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson
The study of self-testing/correcting programs was introduced in [8] in order to allow one to use program P to compute function f without trusting that P works correctly. A self-tester for f estimates...
Self-Testing/Correcting for Polynomials and for Approximate Functions (1991)
Peter Gemmell, Ronitt Rubinfeld, Avi Wigderson
The study of self-testing/correcting programs was introduced in [8] in order to allow one to use program P to compute function f without trusting that P works correctly. A self-tester for f estimates...
An Analysis of a Simple Genetic Algorithm (1991)
Yuri Rabinovich, Avi Wigderson
The rate of convergence and the structure of stable populations are studied for a simple, and yet nontrivial, family of genetic algorithms. 1 INTRODUCTION This paper originates in an attempt to use...
Monotone Circuits for Matching Require Linear Depth (1990)
We prove that monotone circuits computing the perfect matching function on n-vertex graphs require\Omega\Gamma n) depth. This implies an exponential gap between the depth of monotone and nonmonotone...
Monotone Circuits for Matching Require Linear Depth (1990)
We prove that monotone circuits computing the perfect matching function on n-vertex graphs require\Omega\Gamma n) depth. This implies an exponential gap between the depth of monotone and nonmonotone...
Dispersers, Deterministic Amplification, and Weak Random Sources. (1989)
We use a certain type of expanding bipartite graphs, called disperser graphs, to design procedures for picking highly correlated samples from a finite set, with the property that the probability of...
Probabilistic Communication Complexity of Boolean Relations (1989)
In [KW] it was prooved that for every boolean function f there exist a communication complexity game R f such that the minimal circuit-depth of f exactly equals to the communication complexity of R f...
In this section we will first define the second eigenvalue of 3-uniform hypergraph, and then discuss the general notion, as it applies to other uniform hypergraphs and graphs. To motivate our...
How to Solve any Protocol Problem (1987)
Goldreich Silvio, Oded Goldreich, Silvio Micali, Avi Wigderson
: This extended abstract present a general theorem in the field of fault tolerant distributed computing. Following is a simplified description of a special case of this theorem. Loosely speaking, a...
On play by means of computing machines (1986)
J. Y. Halpern, Morgan Kaufmann Publishers, Nimrod Megiddo, Nimrod Megiddo, Nimrod Megiddo, Avi Wigderson, ...
This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its...
Studies in computational complexity. (1983)
Thesis (Ph.D.)--Princeton University, 1983.
Introduction to Reference (1978)
J. Bourgain, N. Katz, T. Tao, Avi Wigderson, A. Wigderson
Applications of the sum-product theorem in finite fields About two years ago Bourgain, Katz and Tao [1] proved the following theorem, essentially stating that in every finite field, a set which does...
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents
Nathan Linial, Alex Samorodnitsky, Avi Wigderson
We present a deterministic strongly polynomial algorithm that computes the permanent of a nonnegative n n matrix to within a multiplicative factor of e .