All reports by Author Avi Wigderson:

__
TR23-004
| 13th January 2023
__

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang#### On linear-algebraic notions of expansion

__
TR21-012
| 9th February 2021
__

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson#### On the Power and Limitations of Branch and Cut

Revisions: 2

__
TR20-192
| 27th December 2020
__

Oded Goldreich, Avi Wigderson#### Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network

__
TR20-160
| 2nd November 2020
__

Oded Goldreich, Avi Wigderson#### Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

Revisions: 3

__
TR20-149
| 29th September 2020
__

Oded Goldreich, Avi Wigderson#### Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2

__
TR19-140
| 7th October 2019
__

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson#### Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings.

Revisions: 1

__
TR19-114
| 2nd September 2019
__

Visu Makam, Avi Wigderson#### Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)

__
TR18-072
| 19th April 2018
__

Avi Wigderson#### On the nature of the Theory of Computation (ToC)

__
TR17-162
| 26th October 2017
__

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson#### Barriers for Rank Methods in Arithmetic Complexity

__
TR17-149
| 7th October 2017
__

Or Meir, Avi Wigderson#### Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Revisions: 5

__
TR16-129
| 16th August 2016
__

Emanuele Viola, Avi Wigderson#### Local Expanders

Revisions: 1

__
TR16-098
| 16th June 2016
__

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson#### Proof Complexity Lower Bounds from Algebraic Circuit Complexity

__
TR16-069
| 25th April 2016
__

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson#### Degree and Sensitivity: tails of two distributions

__
TR15-165
| 14th October 2015
__

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson#### Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

__
TR15-131
| 10th August 2015
__

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson#### Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

__
TR15-025
| 22nd February 2015
__

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff#### Teaching and compressing for low VC-dimension

__
TR15-003
| 3rd January 2015
__

Oded Goldreich, Emanuele Viola, Avi Wigderson#### On Randomness Extraction in AC0

__
TR13-190
| 28th December 2013
__

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson#### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

__
TR13-160
| 20th November 2013
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Breaking the quadratic barrier for 3-LCCs over the Reals

__
TR13-152
| 7th November 2013
__

Oded Goldreich, Avi Wigderson#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

__
TR13-105
| 29th July 2013
__

Raghu Meka, Avi Wigderson#### Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique

Revisions: 1

__
TR13-043
| 25th March 2013
__

Oded Goldreich, Avi Wigderson#### On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

__
TR12-139
| 2nd November 2012
__

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Sylvester-Gallai type theorems for approximate collinearity

__
TR12-138
| 2nd November 2012
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Improved rank bounds for design matrices and a new proof of Kelly's theorem

__
TR12-118
| 18th September 2012
__

Avi Wigderson, Amir Yehudayoff#### Population Recovery and Partial Identification

__
TR11-160
| 1st December 2011
__

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff#### Restriction Access

__
TR10-149
| 22nd September 2010
__

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff#### Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Revisions: 1

__
TR10-040
| 10th March 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Relationless completeness and separations

__
TR10-037
| 8th March 2010
__

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson#### Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

__
TR10-021
| 21st February 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Non-commutative circuits and the sum-of-squares problem

__
TR09-135
| 10th December 2009
__

Zeev Dvir, Avi Wigderson#### Monotone expanders - constructions and applications

__
TR09-090
| 6th October 2009
__

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson#### New Direct-Product Testers and 2-Query PCPs

__
TR09-084
| 24th September 2009
__

Arkadev Chattopadhyay, Avi Wigderson#### Linear systems over composite moduli

__
TR08-079
| 31st August 2008
__

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson#### Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

__
TR08-058
| 1st June 2008
__

Zeev Dvir, Avi Wigderson#### Kakeya sets, new mergers and old extractors

__
TR08-005
| 15th January 2008
__

Scott Aaronson, Avi Wigderson#### Algebrization: A New Barrier in Complexity Theory

__
TR07-079
| 11th August 2007
__

Emanuele Viola, Avi Wigderson#### One-way multi-party communication lower bound for pointer jumping with applications

__
TR07-056
| 10th July 2007
__

Zeev Dvir, Ariel Gabizon, Avi Wigderson#### Extractors and Rank Extractors for Polynomial Sources

__
TR06-118
| 2nd September 2006
__

Irit Dinur, Madhu Sudan, Avi Wigderson#### Robust Local Testability of Tensor Products of LDPC Codes

__
TR06-105
| 23rd August 2006
__

Avi Wigderson, David Xiao#### Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

__
TR05-107
| 28th September 2005
__

Avi Wigderson, David Xiao#### A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Revisions: 1

__
TR02-039
| 30th June 2002
__

Oded Goldreich, Avi Wigderson#### Derandomization that is rarely wrong from short advice that is typically good

Comments: 1

__
TR01-046
| 2nd July 2001
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### On Interactive Proofs with a Laconic Prover

__
TR01-018
| 23rd February 2001
__

Omer Reingold, Salil Vadhan, Avi Wigderson#### Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

__
TR00-059
| 11th August 2000
__

Omer Reingold, Ronen Shaltiel, Avi Wigderson#### Extracting Randomness via Repeated Condensing

__
TR00-056
| 20th July 2000
__

Oded Goldreich, Avi Wigderson#### On Pseudorandomness with respect to Deterministic Observers.

__
TR00-023
| 11th May 2000
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Pseudorandom Generators in Propositional Proof Complexity

__
TR00-009
| 21st February 2000
__

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson#### Extractors and pseudo-random generators with optimal seed length

__
TR00-005
| 17th January 2000
__

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson#### Near-Optimal Separation of Treelike and General Resolution

__
TR00-004
| 14th January 2000
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### Simplified derandomization of BPP using a hitting set generator.

__
TR99-040
| 20th October 1999
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Space Complexity in Propositional Calculus

__
TR99-023
| 16th June 1999
__

Amir Shpilka, Avi Wigderson#### Depth-3 Arithmetic Formulae over Fields of Characteristic Zero

__
TR99-022
| 14th June 1999
__

Eli Ben-Sasson, Avi Wigderson#### Short Proofs are Narrow - Resolution made Simple

__
TR98-072
| 14th December 1998
__

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson#### Deterministic Amplification of Space Bounded Probabilistic Algorithms.

__
TR96-041
| 24th July 1996
__

Oded Goldreich, Avi Wigderson#### On the Circuit Complexity of Perfect Hashing

Revisions: 1
,
Comments: 2

__
TR95-050
| 15th October 1995
__

Oded Goldreich, Noam Nisan, Avi Wigderson#### On Yao's XOR-Lemma

Revisions: 2
,
Comments: 1

__
TR95-049
| 19th October 1995
__

Anna Gal, Avi Wigderson#### Boolean complexity classes vs. their arithmetic analogs

__
TR94-002
| 12th December 1994
__

Oded Goldreich, Avi Wigderson#### Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing

Revisions: 2

__
TR94-001
| 12th December 1994
__

Noam Nisan, Avi Wigderson#### On Rank vs. Communication Complexity

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang

A fundamental fact about bounded-degree graph expanders is that three notions of expansion---vertex expansion, edge expansion, and spectral expansion---are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion.

There are two well-studied notions of linear-algebraic expansion, namely dimension expansion ... more >>>

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

Oded Goldreich, Avi Wigderson

We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs).

Specifically, for every $n\in\N$, we present a collection of $N=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and ...
more >>>

Oded Goldreich, 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 ...
more >>>

Oded Goldreich, Avi Wigderson

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.

Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.

We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ...
more >>>

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).

more >>>Visu Makam, Avi Wigderson

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: ${\rm SING}_{n,m}$, consisting of all $m$-tuples of $n\times n$ complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in ${\rm SING}_{n,m}$ will imply super-polynomial circuit lower bounds, ... more >>>

Avi Wigderson

[ This paper is a (self contained) chapter in a new book on computational complexity theory, called Mathematics and Computation, available at https://www.math.ias.edu/avi/book ].

I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, ... more >>>

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

Or Meir, Avi Wigderson

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

Emanuele Viola, Avi Wigderson

Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of ... more >>>

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ...
more >>>

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

The sensitivity of a Boolean function $f$ is the maximum, over all inputs $x$, of the number of sensitive coordinates of $x$ (namely the number of Hamming neighbors of $x$ with different $f$-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-$s$ Boolean function ... more >>>

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

We study \emph{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~$\epsilon<1/2$, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and ... more >>>

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>>

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. We present relatively efficient constructions of {\em sample compression schemes} and

for classes of low VC-dimension. Let $C$ be a finite boolean concept class of VC-dimension $d$. Set $k ...
more >>>

Oded Goldreich, Emanuele Viola, Avi Wigderson

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>>

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{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 ... more >>>

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+\lambda}$ for some fixed, positive $\lambda >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 ... more >>>

Oded Goldreich, Avi Wigderson

{\em 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 {\em quantified derandomization challenge}:

For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ...
more >>>

Raghu Meka, Avi Wigderson

Finding cliques in random graphs and the closely related ``planted'' clique variant, where a clique of size t 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 t = ... more >>>

Oded Goldreich, Avi Wigderson

We propose that multi-linear functions of relatively low degree

over GF(2) may be good candidates for obtaining exponential

lower bounds on the size of constant-depth Boolean circuits

(computing explicit functions).

Specifically, we propose to move gradually from linear functions

to multilinear ones, and conjecture that, for any $t\geq2$,

more >>>

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study questions in incidence geometry where the precise position of points is `blurry' (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of ... more >>>

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus of a recent work by Barak et. al. (BDWY11) in which they were used to answer questions regarding point configurations. In ... more >>>

Avi Wigderson, Amir Yehudayoff

We study several problems in which an {\em unknown} distribution over an {\em 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 \subseteq \{0,1\}^n$. A ... more >>>

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>>

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

A $(q,k,t)$-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most $q$ non-zeros, each column has at least $k$ non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds.

We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent ...
more >>>

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

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a

distribution $X$ on binary strings of length $n$ is a

$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$

to any string of length $n$. For every $\delta>0$ we construct the

following poly($n$)-time ...
more >>>

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 \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

Zeev Dvir, Avi Wigderson

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:

(1) Constant degree dimension expanders in finite ...
more >>>

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).

This basic construct underlies “hardness amplification” in cryptography, circuit complexity and

PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent

result by Dinur and ...
more >>>

Arkadev Chattopadhyay, Avi Wigderson

We study solution sets to systems of generalized linear equations of the following form:

$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,

where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ...
more >>>

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\to\{0,1\}$ is somewhat hard

to compute on average by small circuits, then the corresponding

$k$-wise direct product function

$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each

$x_i\in\{0,1\}^n$) is significantly harder to compute on average by

slightly smaller ...
more >>>

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

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

Emanuele Viola, Avi Wigderson

In this paper we study the one-way multi-party communication model,

in which every party speaks exactly once in its turn. For every

fixed $k$, we prove a tight lower bound 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$-th ...
more >>>

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 (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

Irit Dinur, Madhu Sudan, Avi Wigderson

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

Avi Wigderson, David Xiao

Ahlswede and Winter 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 present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

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, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>

Oded Goldreich, Avi Wigderson

For every $\epsilon>0$,

we present a {\em deterministic}\/ log-space algorithm

that correctly decides undirected graph connectivity

on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs.

The same holds for every problem in Symmetric Log-space (i.e., $\SL$).

Making no assumptions (and in particular not assuming the ... more >>>

Oded Goldreich, Salil Vadhan, Avi Wigderson

We continue the investigation of interactive proofs with bounded

communication, as initiated by Goldreich and Hastad (IPL 1998).

Let $L$ be a language that has an interactive proof in which the prover

sends few (say $b$) bits to the verifier.

We prove that the complement $\bar L$ has ...
more >>>

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 size from the large one, its degree from the small one, and ...
more >>>

Omer Reingold, Ronen Shaltiel, Avi Wigderson

On an input probability distribution with some (min-)entropy

an {\em 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 ...
more >>>

Oded Goldreich, 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 polynomial-time reductions.

In this paper we show that analogous deterministic reductions

are unlikely to hold. We conclude that randomness ...
more >>>

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em

hard} for a propositional proof system $P$ if $P$ can not efficiently

prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for

{\em any} string $b\in\{0,1\}^m$. We consider a variety of

``combinatorial'' pseudorandom generators inspired by the

Nisan-Wigderson generator on the one hand, and ...
more >>>

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

We give the first construction of a pseudo-random generator with

optimal seed length that uses (essentially) arbitrary hardness.

It builds on the novel recursive use of the NW-generator in

a previous paper by the same authors, which produced many optimal

generators one of which was pseudo-random. This is achieved ...
more >>>

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^\epsilon)$ separation of \cite{BEGJ98}.

This is done by constructing a natural family of contradictions, of

size $n$, that have $O(n)$-size resolution

refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.

This result ...
more >>>

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 implies $RP=P$.

Andreev \etal\/ (ICALP'96, and JACM 1998)

showed that if polynomial-time hitting-set

generator in fact implies ...
more >>>

Michael Alekhnovich, Eli Ben-Sasson, Alexander 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 as Resolution, Polynomial

Calculus and Frege systems. We propose two different space measures,

corresponding to the maximal number of bits, ...
more >>>

Amir Shpilka, Avi Wigderson

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) iterated matrix multiplication, and the

determinant. As corollaries we get the first nontrivial lower

bounds for ...
more >>>

Eli Ben-Sasson, Avi Wigderson

The width of a Resolution proof is defined 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 its tree-like

variant. The following consequences of these relations reveal width as ...
more >>>

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 algorithms, since they

consume too much space. We present a new implementation of the

Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ ...
more >>>

Oded Goldreich, Avi Wigderson

We consider the size of circuits which perfectly hash

an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$

into $\bitset^m$.

We observe that, in general, the size of such circuits is

exponential in $2k-m$,

and provide a matching upper bound.

Oded Goldreich, Noam Nisan, Avi Wigderson

Anna Gal, Avi Wigderson

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

We show a similar randomized reduction between the

Boolean classes NL and semi-unbounded fan-in Boolean circuits and

their arithmetic counterparts. These ...
more >>>

Oded Goldreich, Avi Wigderson

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

and the quality (or error parameter) of the pseudo-random property it

achieves. Unlike previous constructions, ...
more >>>

Noam Nisan, Avi Wigderson

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 example exhibiting the largest gap known. We then

prove two related theorems.