On the Security of Multi-Party Protocols in Distributed Systems. - Danny Dolev; Avi Wigderson (CRYPTO, 1982)

A New Approximate Graph Coloring Algorithm - Avi Wigderson (STOC, 1982)

Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version) - Uzi Vishkin; Avi Wigderson (FOCS, 1983)

Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version) - Danny Dolev; Cynthia Dwork; Nicholas Pippenger; Avi Wigderson (STOC, 1983)

How Discreet is the Discrete Log? - Douglas L. Long; Avi Wigderson (STOC, 1983)

Succinct Representations of Graphs - Hana Galperin; Avi Wigderson (Inf. Control., 1983)

Dynamic Parallel Memories - Uzi Vishkin; Avi Wigderson (Inf. Control., 1983)

Improving the Performance Guarantee for Approximate Graph Coloring - Avi Wigderson (J. ACM, 1983)

How to Share Memory in a Distributed System (A Preliminary Version) - Eli Upfal; Avi Wigderson (FOCS, 1984)

Multi-Layer Grid Embeddings - Alok Aggarwal; Maria M. Klawe; David Lichtenstein; Nathan Linial; Avi Wigderson (FOCS, 1985)

Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) - Miklós Ajtai; Avi Wigderson (FOCS, 1985)

The Complexity of Parallel Computation on Matroids - Richard M. Karp; Eli Upfal; Avi Wigderson (FOCS, 1985)

One, Two, Three dots Infinity: Lower Bounds for Parallel Computation - Faith E. Fich; Friedhelm Meyer auf der Heide; Prabhakar Ragde; Avi Wigderson (STOC, 1985)

Are Search and Decision Problems Computationally Equivalent? - Richard M. Karp; Eli Upfal; Avi Wigderson (STOC, 1985)

Rectilinear Graphs and their Embeddings. - Gopalakrishnan Vijayan; Avi Wigderson (SIAM J. Comput., 1985)

Trade-Offs Between Depth and Width in Parallel Computation. - Uzi Vishkin; Avi Wigderson (SIAM J. Comput., 1985)

A Fast Parallel Algorithm for the Maximal Independent Set Problem - Richard M. Karp; Avi Wigderson (J. ACM, 1985)

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. - Oded Goldreich 001; Silvio Micali; Avi Wigderson (CRYPTO, 1986)

Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract) - Oded Goldreich 001; Silvio Micali; Avi Wigderson (FOCS, 1986)

On a Search Problem Related to Branch-and-Bound Procedures - Richard M. Karp; Michael E. Saks; Avi Wigderson (FOCS, 1986)

A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications - Nathan Linial; László Lovász 001; Avi Wigderson (FOCS, 1986)

Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees - Michael E. Saks; Avi Wigderson (FOCS, 1986)

Proofs that Release Minimum Knowledge. - Oded Goldreich 001; Silvio Micali; Avi Wigderson (MFCS, 1986)

On Play by Means of Computing Machines. - Nimrod Megiddo; Avi Wigderson (TARK, 1986)

Constructing a perfect matching is in random NC. - Richard M. Karp; Eli Upfal; Avi Wigderson (Comb., 1986)

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority - Oded Goldreich 001; Silvio Micali; Avi Wigderson (STOC, 1987)

How to share memory in a distributed system. - Eli Upfal; Avi Wigderson (J. ACM, 1987)

A Time-Space Tradeoff for Element Distinctness. - Allan Borodin; Faith E. Fich; Friedhelm Meyer auf der Heide; Eli Upfal; Avi Wigderson (SIAM J. Comput., 1987)

The Complexity of Parallel Sorting. - Friedhelm Meyer auf der Heide; Avi Wigderson (SIAM J. Comput., 1987)

Hardness vs. Randomness (Extended Abstract) - Noam Nisan; Avi Wigderson (FOCS, 1988)

Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions - Michael Ben-Or; Shafi Goldwasser; Joe Kilian; Avi Wigderson (STOC, 1988)

Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract) - Michael Ben-Or; Shafi Goldwasser; Avi Wigderson (STOC, 1988)

Simulations Among Concurrent-Write PRAMs. - Faith E. Fich; Prabhakar Ragde; Avi Wigderson (Algorithmica, 1988)

Rubber bands, convex embeddings and graph connectivity. - Nathan Linial; László Lovász 001; Avi Wigderson (Comb., 1988)

The Complexity of Parallel Search. - Richard M. Karp; Eli Upfal; Avi Wigderson (J. Comput. Syst. Sci., 1988)

Relations Between Concurrent-Write Models of Parallel Computation. - Faith E. Fich; Prabhakar Ragde; Avi Wigderson (SIAM J. Comput., 1988)

The Discrete Logarithm Hides O(log n) Bits. - Douglas L. Long; Avi Wigderson (SIAM J. Comput., 1988)

The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)). - Prabhakar Ragde; William L. Steiger; Endre Szemerédi; Avi Wigderson (SIAM J. Discret. Math., 1988)

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 (Theor. Comput. Sci., 1988)

Hardness vs. Randomness - A Survey (abstract). - Noam Nisan; Avi Wigderson (SCT, 1989)

Efficient Identification Schemes Using Two Prover Interactive Proofs. - Michael Ben-Or; Shafi Goldwasser; Joe Kilian; Avi Wigderson (CRYPTO, 1989)

Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract) - Aviad Cohen 001; Avi Wigderson (FOCS, 1989)

Probabilistic Communication Complexity of Boolean Relations (Extended Abstract) - Ran Raz; Avi Wigderson (FOCS, 1989)

Towards Understanding Exclusive Read. - Faith E. Fich; Avi Wigderson (SPAA, 1989)

Deterministic Simulation of Probabilistic Constant Depth Circuits. - Miklós Ajtai; Avi Wigderson (Adv. Comput. Res., 1989)

On Computations with Integer Division. - Bettina Just; Friedhelm Meyer auf der Heide; Avi Wigderson (RAIRO Theor. Informatics Appl., 1989)

Perfect Hashing, Graph Entropy, and Circuit Complexity. - Ilan Newman; Prabhakar Ragde; Avi Wigderson (SCT, 1990)

Composition of the Universal Relation. - Johan Håstad; Avi Wigderson (Advances In Computational Complexity Theory, 1990)

On the Power of Randomization in Online Algorithms (Extended Abstract) - Shai Ben-David; Allan Borodin; Richard M. Karp; Gábor Tardos; Avi Wigderson (STOC, 1990)

Not All Keys Can Be Hashed in Constant Time (Preliminary Version) - Joseph Gil; Friedhelm Meyer auf der Heide; Avi Wigderson (STOC, 1990)

Linear Circuits over GF(2). - Noga Alon; Mauricio Karchmer; Avi Wigderson (SIAM J. Comput., 1990)

Toward Understanding Exclusive Read. - Faith E. Fich; Avi Wigderson (SIAM J. Comput., 1990)

Monotone Circuits for Connectivity Require Super-Logarithmic Depth. - Mauricio Karchmer; Avi Wigderson (SIAM J. Discret. Math., 1990)

Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions. - Rafi Heiman; Avi Wigderson (SCT, 1991)

Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity. - Mauricio Karchmer; Ran Raz; Avi Wigderson (SCT, 1991)

Search Problems in the Decision Tree Model (Preliminary Version) - László Lovász 001; Moni Naor; Ilan Newman; Avi Wigderson (FOCS, 1991)

An Analysis of a Simple Genetic Algorithm. - Yuri Rabinovich; Avi Wigderson (ICGA, 1991)

Self-Testing/Correcting for Polynomials and for Approximate Functions - Peter Gemmell; Richard J. Lipton; Ronitt Rubinfeld; Madhu Sudan 001; Avi Wigderson (STOC, 1991)

A Lower Bound on the Area of Permutation Layouts. - Alok Aggarwal; Maria M. Klawe; David Lichtenstein; Nathan Linial; Avi Wigderson (Algorithmica, 1991)

Randomized VS. Deterministic Decision Tree Complexity for Read-Once Boolean Functions. - Rafi Heiman; Avi Wigderson (Comput. Complex., 1991)

Linear-Size Constant-Depth Polylog-Treshold Circuits. - Prabhakar Ragde; Avi Wigderson (Inf. Process. Lett., 1991)

Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems. - Oded Goldreich 001; Silvio Micali; Avi Wigderson (J. ACM, 1991)

Non-deterministic Communication Complexity with Few Witness. - Mauricio Karchmer; Ilan Newman; Michael E. Saks; Avi Wigderson (SCT, 1992)

Undirected Connectivity in O(log ^1.5 n) Space - Noam Nisan; Endre Szemerédi; Avi Wigderson (FOCS, 1992)

Quadratic Dynamical Systems (Preliminary Version) - Yuri Rabinovich; Alistair Sinclair; Avi Wigderson (FOCS, 1992)

The Complexity of Graph Connectivity. - Avi Wigderson (MFCS, 1992)

Geometric medians. - Joseph Gil; William L. Steiger; Avi Wigderson (Discret. Math., 1992)

Monotone Circuits for Matching Require Linear Depth. - Ran Raz; Avi Wigderson (J. ACM, 1992)

On Span Programs. - Mauricio Karchmer; Avi Wigderson (SCT, 1993)

Deterministic Approximate Counting of Depth-2 Circuits. - Michael Luby; Boban Velickovic; Avi Wigderson (ISTCS, 1993)

One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge. - Rafail Ostrovsky; Avi Wigderson (ISTCS, 1993)

Characterizing non-deterministic circuit size. - Mauricio Karchmer; Avi Wigderson (STOC, 1993)

BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. - László Babai; Lance Fortnow; Noam Nisan; Avi Wigderson (Comput. Complex., 1993)

Constructing Small Sets that are Uniform in Arithmetic Progressions. - Alexander A. Razborov; Endre Szemerédi; Avi Wigderson (Comb. Probab. Comput., 1993)

Combinatorial characterization of read-once formulae. - Mauricio Karchmer; Nathan Linial; Ilan Newman; Michael E. Saks; Avi Wigderson (Discret. Math., 1993)

Universal Traversal Sequences for Expander Graphs. - Shlomo Hoory; Avi Wigderson (Inf. Process. Lett., 1993)

n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom. - Alexander A. Razborov; Avi Wigderson (Inf. Process. Lett., 1993)

Rounds in Communication Complexity Revisited. - Noam Nisan; Avi Wigderson (SIAM J. Comput., 1993)

On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity. - Rafi Heiman; Ilan Newman; Avi Wigderson (Theor. Comput. Sci., 1993)

A Direct Product Theorem. - Russell Impagliazzo; Ran Raz; Avi Wigderson (SCT, 1994)

NL/poly <= +/poly (Preliminary Version). - Avi Wigderson (SCT, 1994)

The Wonders of the Digital Envelope - A Crash Course in Modern Cryptography. - Avi Wigderson (IFIP Congress (1), 1994)

On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). - Anne Condon; Lisa Hellerstein; Samuel Pottle; Avi Wigderson (STOC, 1994)

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. - Oded Goldreich 001; Avi Wigderson (STOC, 1994)

Pseudorandomness for network algorithms. - Russell Impagliazzo; Noam Nisan; Avi Wigderson (STOC, 1994)

The amazing power of pairwise independence (abstract). - Avi Wigderson (STOC, 1994)

On the Power of Randomization in On-Line Algorithms. - Shai Ben-David; Allan Borodin; Richard M. Karp; Gábor Tardos; Avi Wigderson (Algorithmica, 1994)

On Rank vs. Communication Complexity - Noam Nisan; Avi Wigderson (Electron. Colloquium Comput. Complex., 1994)

Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 1994)

Non-Deterministic Communication Complexity with Few Witnesses. - Mauricio Karchmer; Ilan Newman; Michael E. Saks; Avi Wigderson (J. Comput. Syst. Sci., 1994)

Hardness vs Randomness. - Noam Nisan; Avi Wigderson (J. Comput. Syst. Sci., 1994)

Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs. - Ivan Damgård; Oded Goldreich 001; Tatsuaki Okamoto; Avi Wigderson (CRYPTO, 1995)

Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version). - Noam Nisan; Avi Wigderson (FOCS, 1995)

Computational Pseudo-Randomness. - Avi Wigderson (ISTCS, 1995)

On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern. - Noam Nisan; Avi Wigderson (STOC, 1995)

Derandomized Graph Products. - Noga Alon; Uriel Feige; Avi Wigderson; David Zuckerman (Comput. Complex., 1995)

Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. - Mauricio Karchmer; Ran Raz; Avi Wigderson (Comput. Complex., 1995)

On the Second Eigenvalue of Hypergraphs. - Joel Friedman; Avi Wigderson (Comb., 1995)

Boolean Complexity Classes vs. Their Arithmetic Analogs - Anna Gál; Avi Wigderson (Electron. Colloquium Comput. Complex., 1995)

On Yao's XOR-Lemma - Oded Goldreich 001; Noam Nisan; Avi Wigderson (Electron. Colloquium Comput. Complex., 1995)

Search Problems in the Decision Tree Model. - László Lovász 001; Moni Naor; Ilan Newman; Avi Wigderson (SIAM J. Discret. Math., 1995)

Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. - Ilan Newman; Avi Wigderson (SIAM J. Discret. Math., 1995)

Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. - Roy Armoni; Michael E. Saks; Avi Wigderson; Shiyu Zhou (FOCS, 1996)

A New NCAlgorithm for Perfect Matching in Bipartite Cubic Graphs. - Roded Sharan; Avi Wigderson (ISTCS, 1996)

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 (STOC, 1996)

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities. - Helmut Alt; Leonidas J. Guibas; Kurt Mehlhorn; Richard M. Karp; Avi Wigderson (Algorithmica, 1996)

Theory of Computing: A Scientific Perspective. - Oded Goldreich 001; Avi Wigderson (ACM Comput. Surv., 1996)

On the Circuit Complexity of Perfect Hashing - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 1996)

The Tree Model for Hashing: Lower and Upper Bounds. - Joseph Gil; Friedhelm Meyer auf der Heide; Avi Wigderson (SIAM J. Comput., 1996)

The future of computational complexity theory: part I. - Christos H. Papadimitriou; Oded Goldreich 001; Avi Wigderson; Alexander A. Razborov; Michael Sipser (SIGACT News, 1996)

SL <= L4/3. - Roy Armoni; Amnon Ta-Shma; Avi Wigderson; Shiyu Zhou (STOC, 1997)

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. - Russell Impagliazzo; Avi Wigderson (STOC, 1997)

Direct Product Results and the GCD Problem, in Old and New Communication Models. - Itzhak Parnafes; Ran Raz; Avi Wigderson (STOC, 1997)

Lower Bounds on Arithmetic Circuits Via Partial Derivatives. - Noam Nisan; Avi Wigderson (Comput. Complex., 1997)

Theory of computing: a scientific perspective (extended abstract). - Oded Goldreich 001; Avi Wigderson (SIGACT News, 1997)

Randomness vs. Time: De-Randomization under a Uniform Assumption. - Russell Impagliazzo; Avi Wigderson (FOCS, 1998)

Do Probabilistic Algorithms Outperform Deterministic Ones? - Avi Wigderson (ICALP, 1998)

Quantum vs. Classical Communication and Computation. - Harry Buhrman; Richard Cleve; Avi Wigderson (STOC, 1998)

Deterministic Amplification of Space Bounded Probabilistic Algorithms. - Ziv Bar-Yossef; Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 1998)

On Data Structures and Asymmetric Communication Complexity. - Peter Bro Miltersen; Noam Nisan; Shmuel Safra; Avi Wigderson (J. Comput. Syst. Sci., 1998)

On the Power of Finite Automata with Both Nondeterministic and Probabilistic States. - Anne Condon; Lisa Hellerstein; Samuel Pottle; Avi Wigderson (SIAM J. Comput., 1998)

Short Proofs Are Narrow - Resolution Made Simple (Abstract). - Eli Ben-Sasson; Avi Wigderson (CCC, 1999)

De-Randomizing BPP: The State of the Art. - Avi Wigderson (CCC, 1999)

Near-Optimal Conversion of Hardness into Pseudo-Randomness. - Russell Impagliazzo; Ronen Shaltiel; Avi Wigderson (FOCS, 1999)

Improved Derandomization of BPP Using a Hitting Set Generator. - Oded Goldreich 001; Avi Wigderson (RANDOM-APPROX, 1999)

Probabilistic and Deterministic Approximations of the Permanent (abstract). - Avi Wigderson (RANDOM-APPROX, 1999)

Superpolynomial Lower Bounds for Monotone Span Programs. - László Babai; Anna Gál; Avi Wigderson (Comb., 1999)

Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. - Avi Wigderson; David Zuckerman (Comb., 1999)

Short Proofs are Narrow - Resolution made Simple - Eli Ben-Sasson; Avi Wigderson (Electron. Colloquium Comput. Complex., 1999)

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero - Amir Shpilka; Avi Wigderson (Electron. Colloquium Comput. Complex., 1999)

Techniques for bounding the convergence rate of genetic algorithms. - Yuri Rabinovich; Avi Wigderson (Random Struct. Algorithms, 1999)

On Pseudorandomness with respect to Deterministic Observes. - Oded Goldreich 001; Avi Wigderson (ICALP Satellite Workshops, 2000)

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. - Nathan Linial; Alex Samorodnitsky; Avi Wigderson (Comb., 2000)

Simplified derandomization of BPP using a hitting set generator. - Oded Goldreich 001; Salil P. Vadhan; Avi Wigderson (Electron. Colloquium Comput. Complex., 2000)

Near-Optimal Separation of Treelike and General Resolution - Eli Ben-Sasson; Russell Impagliazzo; Avi Wigderson (Electron. Colloquium Comput. Complex., 2000)

Extractors and pseudo-random generators with optimal seed length - Russell Impagliazzo; Ronen Shaltiel; Avi Wigderson (Electron. Colloquium Comput. Complex., 2000)

On Pseudorandomness with respect to Deterministic Observers. - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2000)

An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs. - Roy Armoni; Amnon Ta-Shma; Avi Wigderson; Shiyu Zhou (J. ACM, 2000)

Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. - Noga Alon; Alexander Lubotzky; Avi Wigderson (FOCS, 2001)

Depth-3 arithmetic circuits over fields of characteristic zero. - Amir Shpilka; Avi Wigderson (Comput. Complex., 2001)

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors - Omer Reingold; Salil P. Vadhan; Avi Wigderson (Electron. Colloquium Comput. Complex., 2001)

Randomness vs Time: Derandomization under a Uniform Assumption. - Russell Impagliazzo; Avi Wigderson (J. Comput. Syst. Sci., 2001)

Computing Graph Properties by Randomized Subcube Partitions. - Ehud Friedgut; Jeff Kahn 001; Avi Wigderson (RANDOM, 2002)

Randomness conductors and constant-degree lossless expanders. - Michael R. Capalbo; Omer Reingold; Salil P. Vadhan; Avi Wigderson (STOC, 2002)

Expanders from symmetric codes. - Roy Meshulam; Avi Wigderson (STOC, 2002)

On interactive proofs with a laconic prover. - Oded Goldreich 001; Salil P. Vadhan; Avi Wigderson (Comput. Complex., 2002)

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. - Alexander A. Razborov; Avi Wigderson; Andrew Chi-Chih Yao (Comb., 2002)

Derandomization that is rarely wrong from short advice that is typically good - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2002)

In search of an easy witness: exponential time vs. probabilistic polynomial time. - Russell Impagliazzo; Valentine Kabanets; Avi Wigderson (J. Comput. Syst. Sci., 2002)

Space Complexity in Propositional Calculus. - Michael Alekhnovich; Eli Ben-Sasson; Alexander A. Razborov; Avi Wigderson (SIAM J. Comput., 2002)

Zigzag Products, Expander Constructions, Connections, and Applications. - Avi Wigderson (FSTTCS, 2003)

Computational Analogues of Entropy. - Boaz Barak; Ronen Shaltiel; Avi Wigderson (RANDOM-APPROX, 2003)

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. - Eli Ben-Sasson; Madhu Sudan 001; Salil P. Vadhan; Avi Wigderson (STOC, 2003)

Extractors: optimal up to constant factors. - Chi-Jen Lu; Omer Reingold; Salil P. Vadhan; Avi Wigderson (STOC, 2003)

Simple analysis of graph tests for linearity and PCP. - Johan Håstad; Avi Wigderson (Random Struct. Algorithms, 2003)

The Quantum Communication Complexity of Sampling. - Andris Ambainis; Leonard J. Schulman; Amnon Ta-Shma; Umesh V. Vazirani; Avi Wigderson (SIAM J. Comput., 2003)

Average case complexity. - Avi Wigderson (Computational Complexity Theory, 2004)

A new family of Cayley expanders (?). - Eyal Rozenman; Aner Shalev; Avi Wigderson (STOC, 2004)

Depth through breadth, or why should we attend talks in other areas? - Avi Wigderson (STOC, 2004)

Near Optimal Separation Of Tree-Like And General Resolution. - Eli Ben-Sasson; Russell Impagliazzo; Avi Wigderson (Comb., 2004)

Expanders In Group Algebras. - Roy Meshulam; Avi Wigderson (Comb., 2004)

Pseudorandom Generators in Propositional Proof Complexity. - Michael Alekhnovich; Eli Ben-Sasson; Alexander A. Razborov; Avi Wigderson (SIAM J. Comput., 2004)

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. - Paul Beame; Toniann Pitassi; Nathan Segerlind; Avi Wigderson (CCC, 2005)

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications - Avi Wigderson; David Xiao (Electron. Colloquium Comput. Complex., 2005)

Pairwise Independence and Derandomization. - Michael Luby; Avi Wigderson (Found. Trends Theor. Comput. Sci., 2005)

Applications of the Sum-Product Theorem in Finite Fields. - Avi Wigderson (CCC, 2006)

The Power and Weakness of Randomness in Computation. - Avi Wigderson (LATIN, 2006)

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. - Boaz Barak; Anup Rao 001; Ronen Shaltiel; Avi Wigderson (STOC, 2006)

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. - Paul Beame; Toniann Pitassi; Nathan Segerlind; Avi Wigderson (Comput. Complex., 2006)

Reducing The Seed Length In The Nisan-Wigderson Generator. - Russell Impagliazzo; Ronen Shaltiel; Avi Wigderson (Comb., 2006)

Robust Local Testability of Tensor Products of LDPC Codes. - Irit Dinur; Madhu Sudan 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2006)

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications. - Avi Wigderson; David Xiao (Electron. Colloquium Comput. Complex., 2006)

Extracting Randomness Using Few Independent Sources. - Boaz Barak; Russell Impagliazzo; Avi Wigderson (SIAM J. Comput., 2006)

Extracting Randomness via Repeated Condensing. - Omer Reingold; Ronen Shaltiel; Avi Wigderson (SIAM J. Comput., 2006)

Derandomizing Homomorphism Testing in General Groups. - Amir Shpilka; Avi Wigderson (SIAM J. Comput., 2006)

Iterative Construction of Cayley Expander Graphs. - Eyal Rozenman; Aner Shalev; Avi Wigderson (Theory Comput., 2006)

Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. - Emanuele Viola; Avi Wigderson (CCC, 2007)

One-way multi-party communication lower bound for pointer jumping with applications. - Emanuele Viola; Avi Wigderson (Electron. Colloquium Comput. Complex., 2007)

The Randomized Communication Complexity of Set Disjointness. - Johan Håstad; Avi Wigderson (Theory Comput., 2007)

Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. - Venkatesan Guruswami; James R. Lee; Avi Wigderson (APPROX-RANDOM, 2008)

Randomness - A Computational Complexity Perspective. - Avi Wigderson (CSR, 2008)

Spherical Cubes and Rounding in High Dimensions. - Guy Kindler; Ryan O'Donnell; Anup Rao 001; Avi Wigderson (FOCS, 2008)

Neighborly Embedded Manifolds. - Gil Kalai; Avi Wigderson (Discret. Comput. Geom., 2008)

Algebrization: A New Barrier in Complexity Theory. - Scott Aaronson; Avi Wigderson (Electron. Colloquium Comput. Complex., 2008)

Public Key Cryptography from Different Assumptions. - Boaz Barak; Avi Wigderson (IACR Cryptol. ePrint Arch., 2008)

Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. - Emanuele Viola; Avi Wigderson (Theory Comput., 2008)

Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. - Avi Wigderson; David Xiao (Theory Comput., 2008)

Expander codes over reals, Euclidean sections, and compressed sensing. - Venkatesan Guruswami; James R. Lee; Avi Wigderson (Allerton, 2009)

Randomness extractors – applications and constructions. - Avi Wigderson (FSTTCS, 2009)

Towards a Study of Low-Complexity Graphs. - Sanjeev Arora; David Steurer; Avi Wigderson (ICALP (1), 2009)

The work of Leslie Valiant. - Avi Wigderson (STOC, 2009)

Extractors And Rank Extractors For Polynomial Sources. - Zeev Dvir; Ariel Gabizon; Avi Wigderson (Comput. Complex., 2009)

One-way multiparty communication lower bound for pointer jumping with applications. - Emanuele Viola; Avi Wigderson (Comb., 2009)

Linear systems over composite moduli. - Arkadev Chattopadhyay; Avi Wigderson (Electron. Colloquium Comput. Complex., 2009)

Monotone expanders - constructions and applications. - Zeev Dvir; Avi Wigderson (Electron. Colloquium Comput. Complex., 2009)

Symmetric LDPC Codes and Local Testing. - Tali Kaufman; Avi Wigderson (Property Testing, 2010)

Public-key cryptography from different assumptions. - Benny Applebaum; Boaz Barak; Avi Wigderson (STOC, 2010)

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. - Boaz Barak; Zeev Dvir; Avi Wigderson; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2010)

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. - Boaz Barak; Guy Kindler; Ronen Shaltiel; Benny Sudakov; Avi Wigderson (Electron. Colloquium Comput. Complex., 2010)

Non-commutative circuits and the sum-of-squares problem. - Pavel Hrubes; Avi Wigderson; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2010)

Relationless completeness and separations. - Pavel Hrubes; Avi Wigderson; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2010)

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. - Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets; Avi Wigderson (SIAM J. Comput., 2010)

On Yao's XOR-Lemma. - Oded Goldreich 001; Noam Nisan; Avi Wigderson (Studies in Complexity and Cryptography, 2011)

Simplified Derandomization of BPP Using a Hitting Set Generator. - Oded Goldreich 001; Salil P. Vadhan; Avi Wigderson (Studies in Complexity and Cryptography, 2011)

On the Circuit Complexity of Perfect Hashing. - Oded Goldreich 001; Avi Wigderson (Studies in Complexity and Cryptography, 2011)

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. - Boaz Barak; Zeev Dvir; Amir Yehudayoff; Avi Wigderson (STOC, 2011)

Restriction Access. - Zeev Dvir; Anup Rao 001; Avi Wigderson; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2011)

Partial Derivatives in Arithmetic Complexity and Beyond. - Xi Chen 001; Neeraj Kayal; Avi Wigderson (Found. Trends Theor. Comput. Sci., 2011)

Kakeya Sets, New Mergers, and Old Extractors. - Zeev Dvir; Avi Wigderson (SIAM J. Comput., 2011)

Spherical cubes: optimal foams from computational hardness amplification. - Guy Kindler; Anup Rao 001; Ryan O'Donnell; Avi Wigderson (Commun. ACM, 2012)

Sylvester-Gallai type theorems for approximate collinearity. - Albert Ai; Zeev Dvir; Shubhangi Saraf; Avi Wigderson (Electron. Colloquium Comput. Complex., 2012)

Improved rank bounds for design matrices and a new proof of Kelly's theorem. - Zeev Dvir; Shubhangi Saraf; Avi Wigderson (Electron. Colloquium Comput. Complex., 2012)

New Direct-Product Testers and 2-Query PCPs. - Russell Impagliazzo; Valentine Kabanets; Avi Wigderson (SIAM J. Comput., 2012)

Interactive proofs of proximity: delegating computation in sublinear time. - Guy N. Rothblum; Salil P. Vadhan; Avi Wigderson (STOC, 2013)

Breaking the quadratic barrier for 3-LCCs over the Reals. - Zeev Dvir; Shubhangi Saraf; Avi Wigderson (Electron. Colloquium Comput. Complex., 2013)

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. - Dmitry Gavinsky; Or Meir; Omri Weinstein; Avi Wigderson (Electron. Colloquium Comput. Complex., 2013)

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2013)

On Derandomizing Algorithms that Err Extremely Rarely. - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2013)

Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique. - Raghu Meka; Avi Wigderson (Electron. Colloquium Comput. Complex., 2013)

Breaking the quadratic barrier for 3-LCC's over the reals. - Zeev Dvir; Shubhangi Saraf; Avi Wigderson (STOC, 2014)

Compressing and Teaching for Low VC-Dimension. - Shay Moran; Amir Shpilka; Avi Wigderson; Amir Yehudayoff (FOCS, 2015)

Sum-of-Squares Lower Bounds for Sparse PCA. - Tengyu Ma 001; Avi Wigderson (NIPS, 2015)

Sum-of-squares Lower Bounds for Planted Clique. - Raghu Meka; Aaron Potechin; Avi Wigderson (STOC, 2015)

Towards Optimal Deterministic Coding for Interactive Communication. - Ran Gelles; Bernhard Haeupler; Gillat Kol; Noga Ron-Zewi; Avi Wigderson (Electron. Colloquium Comput. Complex., 2015)

On Randomness Extraction in AC0. - Oded Goldreich 001; Emanuele Viola; Avi Wigderson (Electron. Colloquium Comput. Complex., 2015)

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. - Parikshit Gopalan; Noam Nisan; Rocco A. Servedio; Kunal Talwar; Avi Wigderson (Electron. Colloquium Comput. Complex., 2015)

Teaching and compressing for low VC-dimension. - Shay Moran; Amir Shpilka; Avi Wigderson; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2015)

Invited Articles Foreword. - Avi Wigderson; Phokion G. Kolaitis (J. ACM, 2015)

Reed-Muller Codes for Random Erasures and Errors. - Emmanuel Abbe; Amir Shpilka; Avi Wigderson (IEEE Trans. Inf. Theory, 2015)

Non-Commutative Arithmetic Circuits with Division. - Pavel Hrubes; Avi Wigderson (Theory Comput., 2015)

Degree and Sensitivity: Tails of Two Distributions. - Parikshit Gopalan; Rocco A. Servedio; Avi Wigderson (CCC, 2016)

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. - Ankit Garg; Leonid Gurvits; Rafael Mendes de Oliveira; Avi Wigderson (FOCS, 2016)

Symmetric LDPC codes and local testing. - Tali Kaufman; Avi Wigderson (Comb., 2016)

Algorithmic aspects of Brascamp-Lieb inequalities. - Ankit Garg; Leonid Gurvits; Rafael Mendes de Oliveira; Avi Wigderson (CoRR, 2016)

Proof Complexity Lower Bounds from Algebraic Circuit Complexity. - Michael A. Forbes 001; Amir Shpilka; Iddo Tzameret; Avi Wigderson (Electron. Colloquium Comput. Complex., 2016)

Degree and Sensitivity: tails of two distributions. - Parikshit Gopalan; Rocco A. Servedio; Avishay Tal; Avi Wigderson (Electron. Colloquium Comput. Complex., 2016)

Population recovery and partial identification. - Avi Wigderson; Amir Yehudayoff (Mach. Learn., 2016)

Much Faster Algorithms for Matrix Scaling. - Zeyuan Allen-Zhu; Yuanzhi Li; Rafael Mendes de Oliveira; Avi Wigderson (FOCS, 2017)

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. - Ankit Garg; Leonid Gurvits; Rafael Mendes de Oliveira; Avi Wigderson (STOC, 2017)

Technical Perspective: Low-depth arithmetic circuits. - Avi Wigderson (Commun. ACM, 2017)

Interactions of Computational Complexity Theory and Mathematics. - Avi Wigderson (CoRR, 2017)

Barriers for Rank Methods in Arithmetic Complexity. - Klim Efremenko; Ankit Garg; Rafael Mendes de Oliveira; Avi Wigderson (Electron. Colloquium Comput. Complex., 2017)

Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. - Dmitry Gavinsky; Or Meir; Omri Weinstein; Avi Wigderson (SIAM J. Comput., 2017)

Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. - Zeev Dvir; Shubhangi Saraf; Avi Wigderson (Theory Comput., 2017)

Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes. - Peter Bürgisser; Cole Franks; Ankit Garg; Rafael Mendes de Oliveira; Michael Walter 005; Avi Wigderson (FOCS, 2018)

Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. - Peter Bürgisser; Ankit Garg; Rafael Mendes de Oliveira; Michael Walter 005; Avi Wigderson (ITCS, 2018)

Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. - Zeyuan Allen-Zhu; Ankit Garg; Yuanzhi Li; Rafael Mendes de Oliveira; Avi Wigderson (STOC, 2018)

Local Expanders. - Emanuele Viola; Avi Wigderson (Comput. Complex., 2018)

Spanoids - an abstraction of spanning structures, and a barrier for LCCs. - Zeev Dvir; Sivakanth Gopi; Avi Wigderson (CoRR, 2018)

On the nature of the Theory of Computation (ToC). - Avi Wigderson (Electron. Colloquium Comput. Complex., 2018)

Explicit Capacity Approaching Coding for Interactive Communication. - Ran Gelles; Bernhard Haeupler; Gillat Kol; Noga Ron-Zewi; Avi Wigderson (IEEE Trans. Inf. Theory, 2018)

Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. - Oded Goldreich 001; Silvio Micali; Avi Wigderson (Providing Sound Foundations for Cryptography, 2019)

How to play any mental game, or a completeness theorem for protocols with honest majority. - Oded Goldreich 001; Silvio Micali; Avi Wigderson (Providing Sound Foundations for Cryptography, 2019)

Multi-prover interactive proofs: how to remove intractability assumptions. - Michael Ben-Or; Shafi Goldwasser; Joe Kilian; Avi Wigderson (Providing Sound Foundations for Cryptography, 2019)

Completeness theorems for non-cryptographic fault-tolerant distributed computation. - Michael Ben-Or; Shafi Goldwasser; Avi Wigderson (Providing Sound Foundations for Cryptography, 2019)

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; Rafael Mendes de Oliveira; Michael Walter 005; Avi Wigderson (FOCS, 2019)

More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer. - Ankit Garg; Visu Makam; Rafael Mendes de Oliveira; Avi Wigderson (FOCS, 2019)

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. - Or Meir; Avi Wigderson (Comput. Complex., 2019)

Subspace arrangements, graph rigidity and derandomization through submodular optimization. - Orit E. Raz; Avi Wigderson (CoRR, 2019)

Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. - Peter Bürgisser; Cole Franks; Ankit Garg; Rafael Mendes de Oliveira; Michael Walter 005; Avi Wigderson (CoRR, 2019)

Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. - Ankit Garg; Visu Makam; Rafael Mendes de Oliveira; Avi Wigderson (Electron. Colloquium Comput. Complex., 2019)

Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). - Visu Makam; Avi Wigderson (Electron. Colloquium Comput. Complex., 2019)

Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. - Ankit Garg; Christian Ikenmeyer; Visu Makam; Rafael Mendes de Oliveira; Michael Walter 005; Avi Wigderson (CCC, 2020)

Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties. - Visu Makam; Avi Wigderson (FOCS, 2020)

The uncertainty principle: variations on a theme. - Avi Wigderson; Yuval Wigderson (CoRR, 2020)

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2020)

Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2020)

Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network. - Oded Goldreich 001; Avi Wigderson (Electron. Colloquium Comput. Complex., 2020)

Operator Scaling: Theory and Applications. - Ankit Garg; Leonid Gurvits; Rafael Mendes de Oliveira; Avi Wigderson (Found. Comput. Math., 2020)

Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. - Zeev Dvir; Sivakanth Gopi; Yuzhou Gu; Avi Wigderson (SIAM J. Comput., 2020)

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. - Oded Goldreich 001; Avi Wigderson (Computational Complexity and Property Testing, 2020)

Polynomial Time Algorithms in Invariant Theory for Torus Actions. - Peter Bürgisser; M. Levent Dogan; Visu Makam; Michael Walter 005; Avi Wigderson (CCC, 2021)

On the Power and Limitations of Branch and Cut. - Noah Fleming; Mika Göös; Russell Impagliazzo; Toniann Pitassi; Robert Robere; Li-Yang Tan; Avi Wigderson (Electron. Colloquium Comput. Complex., 2021)

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. - Fernando Granha Jeronimo; Tushant Mittal; Sourya Roy; Avi Wigderson (FOCS, 2022)

Non-commutative Optimization - Where Algebra, Analysis and Computational Complexity Meet. - Avi Wigderson (ISSAC, 2022)

Connections between graphs and matrix spaces. - Yinan Li; Youming Qiao; Avi Wigderson; Yuval Wigderson; Chuanqi Zhang (CoRR, 2022)

An Optimal "It Ain't Over Till It's Over" Theorem. - Ronen Eldan; Avi Wigderson; Pei Wu (STOC, 2023)

On linear-algebraic notions of expansion. - Yinan Li; Youming Qiao; Avi Wigderson; Yuval Wigderson; Chuanqi Zhang (Electron. Colloquium Comput. Complex., 2023)

Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. - Peter Bürgisser; Mahmut Levent Dogan; Visu Makam; Michael Walter 005; Avi Wigderson (CCC, 2024)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems. - Robert Andrews 003; Avi Wigderson (Electron. Colloquium Comput. Complex., 2024)

Sparser Abelian High Dimensional Expanders. - Yotam Dikstein; Siqi Liu 005; Avi Wigderson (CCC, 2025)