List of works - Avi Wigderson

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities

scientific article published in 1996

Algebrization

BPP has subexponential time simulations unlessEXPTIME has publishable proofs

Combinatorial characterization of read-once formulae

scholarly article

Completeness theorems for non-cryptographic fault-tolerant distributed computation

scientific article published on 09 October 2019

Computing Graph Properties by Randomized Subcube Partitions

Easy Or Hard? Basic Questions in Computational Complexity Theory

scholarly article

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

scientific article (publication date: 2002)

Expander graphs and their applications

scientific article (publication date: 7 August 2006)

Fractional Sylvester–Gallai theorems.

scientific article published on 17 September 2012

Hardness vs randomness

How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design ⬇️

Extended Abstract

How to play ANY mental game

How to play any mental game, or a completeness theorem for protocols with honest majority

scientific article published on 09 October 2019

Improving the performance guarantee for approximate graph coloring

scientific article (publication date: October 1983)

Non-commutative Optimization - Where Algebra, Analysis and Computational Complexity Meet

scientific article published on 05 July 2022

On the power of randomization in on-line algorithms

scientific article (publication date: 1994)

P = BPP if E requires exponential circuits

Probabilistic Boolean decision trees and the complexity of evaluating game trees

Proofs that Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems

scientific article

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Public-key cryptography from different assumptions

scientific article published on 08 June 2010

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

scientific article published in 2002

Reed-Muller Codes for Random Erasures and Errors

scientific article published on 03 June 2015

Rubber bands, convex embeddings and graph connectivity

SL ⊆L4/3

Simple analysis of graph tests for linearity and PCP

scholarly article by Johan Håstad & Avi Wigderson published 6 January 2003 in Random Structures and Algorithms

Sum-of-Squares Lower Bounds for Sparse PCA ⬇️

Sum-of-squares Lower Bounds for Planted Clique

article

The Quantum Communication Complexity of Sampling

article by Andris Ambainis et al published January 2003 in SIAM Journal on Computing

The work of Leslie Valiant

scientific article (publication date: 2009)

List of works by Avi Wigderson

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities

Algebrization

BPP has subexponential time simulations unlessEXPTIME has publishable proofs

Combinatorial characterization of read-once formulae

Completeness theorems for non-cryptographic fault-tolerant distributed computation

Completeness theorems for non-cryptographic fault-tolerant distributed computation

Computing Graph Properties by Randomized Subcube Partitions

Easy Or Hard? Basic Questions in Computational Complexity Theory

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

Expander graphs and their applications

Fractional Sylvester–Gallai theorems.

Hardness vs randomness

How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design ⬇️

How to play ANY mental game

How to play any mental game, or a completeness theorem for protocols with honest majority

Improving the performance guarantee for approximate graph coloring

Non-commutative Optimization - Where Algebra, Analysis and Computational Complexity Meet

On the power of randomization in on-line algorithms

P = BPP if E requires exponential circuits

Probabilistic Boolean decision trees and the complexity of evaluating game trees

Proofs that Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Public-key cryptography from different assumptions

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

Reed-Muller Codes for Random Erasures and Errors

Rubber bands, convex embeddings and graph connectivity

SL ⊆L4/3

Simple analysis of graph tests for linearity and PCP

Sum-of-Squares Lower Bounds for Sparse PCA ⬇️

Sum-of-squares Lower Bounds for Planted Clique

The Quantum Communication Complexity of Sampling

The work of Leslie Valiant

Undirected connectivity in O(log/sup 1.5/n) space