Avi Wigderson | Academic Influence

Why Is Avi Wigderson Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Avi Wigderson is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural networks. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science.

(See a Problem?)

Avi Wigderson's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Papers

How to play ANY mental game (1987) (3218)
Completeness theorems for non-cryptographic fault-tolerant distributed computation (1988) (2390)
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems (1991) (1399)
How to play any mental game, or a completeness theorem for protocols with honest majority (2019) (941)
Hardness vs Randomness (1994) (727)
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (1986) (611)
Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract) (1988) (560)
P = BPP if E requires exponential circuits: derandomizing the XOR lemma (1997) (560)
Short proofs are narrow-resolution made simple (1999) (537)
Multi-prover interactive proofs: how to remove intractability assumptions (2019) (519)
On span programs (1993) (498)
Monotone circuits for connectivity require super-logarithmic depth (1990) (488)
Quantum vs. classical communication and computation (1998) (412)
Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors (2000) (400)
On data structures and asymmetric communication complexity (1994) (326)
Constructing a perfect matching is in random NC (1985) (316)
Succinct Representations of Graphs (1984) (237)
Algebrization: A New Barrier in Complexity Theory (2009) (231)
Hardness vs. randomness (1988) (222)
In search of an easy witness: exponential time vs. probabilistic polynomial time (2001) (219)
Rounds in communication complexity revisited (1991) (216)
Improving the performance guarantee for approximate graph coloring (1983) (212)
Randomness conductors and constant-degree lossless expanders (2002) (212)
Lower bounds on arithmetic circuits via partial derivatives (1995) (211)
On the power of randomization in online algorithms (1990) (211)
Self-testing/correcting for polynomials and for approximate functions (1991) (211)
Probabilistic Boolean decision trees and the complexity of evaluating game trees (1986) (206)
A fast parallel algorithm for the maximal independent set problem (1984) (203)
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents (1998) (201)
Pseudorandomness for network algorithms (1994) (199)
Extracting randomness using few independent sources (2004) (196)
On the power of randomization in on-line algorithms (2005) (195)
On Yao's XOR-Lemma (1995) (186)
Relations between concurrent-write models of parallel computation (1984) (177)
Dispersers, deterministic amplification, and weak random sources (1989) (176)
How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design (1986) (173)
A fast parallel algorithm for the maximal independent set problem (1985) (169)
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors (2005) (168)
How to share memory in a distributed system (1987) (167)
One-way functions are essential for non-trivial zero-knowledge (1993) (164)
Space complexity in propositional calculus (2000) (156)
On rank vs. communication complexity (1994) (153)
Near Optimal Separation Of Tree-Like And General Resolution (2004) (153)
Extractors: optimal up to constant factors (2003) (149)
Monotone circuits for matching require linear depth (1990) (145)
Public-key cryptography from different assumptions (2010) (140)
Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications (1993) (135)
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets (2003) (132)
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1997) (128)
ENTROPY WAVES, THE ZIG-ZAG GRAPH PRODUCT, AND NEW CONSTANT-DEGREE (2004) (117)
Computational Analogues of Entropy (2003) (115)
Monotone circuits for matching require linear depth (1992) (115)
Derandomized graph products (1995) (115)
Pairwise Independence and Derandomization (2006) (114)
Depth-3 arithmetic circuits over fields of characteristic zero (2002) (113)
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction (2006) (113)
On interactive proofs with a laconic prover (2001) (112)
Pseudorandom generators in propositional proof complexity (2000) (111)
Deterministic simulation of probabilistic constant depth circuits (1985) (107)
Randomness vs Time: Derandomization under a Uniform Assumption (2001) (106)
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing (2015) (104)
The quantum communication complexity of sampling (1998) (104)
Much Faster Algorithms for Matrix Scaling (2017) (100)
Randomness vs. time: de-randomization under a uniform assumption (1998) (100)
Sum-of-squares Lower Bounds for Planted Clique (2013) (100)
Extracting randomness via repeated condensing (2000) (100)
The Randomized Communication Complexity of Set Disjointness (2007) (98)
Rubber bands, convex embeddings and graph connectivity (1988) (98)
P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma (2002) (95)
The Complexity of Parallel Search (1988) (94)
Super-logarithmic depth lower bounds via direct sum in communication complexity (1991) (92)
The Complexity of Graph Connectivity (1992) (88)
Simple analysis of graph tests for linearity and PCP (2001) (87)
Uniform direct product theorems: simplified, optimized, and derandomized (2008) (81)
On the second eigenvalue of hypergraphs (1995) (80)
Deterministic approximate counting of depth-2 circuits (1993) (80)
Superconcentrators, generalizers and generalized connectors with limited depth (1983) (80)
Quadratic dynamical systems (1992) (78)
Theory of computing (1997) (78)
Superpolynomial Lower Bounds for Monotone Span Programs (1996) (77)
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols (2008) (76)
Semi-direct product in groups and zig-zag product in graphs: connections and applications (2001) (76)
Extractors And Rank Extractors For Polynomial Sources (2007) (73)
Partial Derivatives in Arithmetic Complexity and Beyond (2011) (73)
BPP has subexponential time simulations unlessEXPTIME has publishable proofs (1993) (73)
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling (2016) (73)
P, NP and mathematics a computational complexity perspective (2006) (73)
Kakeya Sets, New Mergers and Old Extractors (2008) (71)
2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction (2012) (68)
Super-logarithmic depth lower bounds via the direct sum in communication complexity (1995) (68)
Search problems in the decision tree model (1991) (67)
Extractors and pseudo-random generators with optimal seed length (2000) (67)
On Play by Means of Computing Machines (1986) (66)
Sum-of-Squares Lower Bounds for Sparse PCA (2015) (63)
Undirected Connectivity in O(log ^1.5 n) Space (1992) (63)
Theory of computing: a scientific perspective (1996) (63)
Interactive proofs of proximity: delegating computation in sublinear time (2013) (62)
Reed–Muller Codes for Random Erasures and Errors (2014) (60)
Undirected connectivity in O(log/sup 1.5/n) space (1992) (60)
Rectilinear Graphs and their Embeddings (1985) (59)
Trade-offs between depth and width in parallel computation (1985) (59)
Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing (1992) (58)
Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing (2018) (57)
The Discrete Logarithm Hides O(log n) Bits (1988) (57)
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes (2010) (56)
Direct product results and the GCD problem, in old and new communication models (1997) (56)
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications (2008) (55)
Depth-3 arithmetic formulae over fields of characteristic zero (1999) (55)
An Analysis of a Simple Genetic Algorithm (1991) (55)
Robust Local Testability of Tensor Products of LDPC Codes (2006) (54)
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols (2007) (54)
Geometric medians (1992) (54)
The complexity of parallel sorting (1985) (53)
Non-commutative circuits and the sum-of-squares problem (2010) (53)
Randomness conductors and constant-degree lossless expanders (2002) (53)
New direct-product testers and 2-query PCPs (2009) (53)
Operator Scaling: Theory and Applications (2015) (53)
Combinatorial characterization of read-once formulae (1993) (52)
Composition of the Universal Relation (1990) (52)
Undirected Connectivity in O(l~gl*~ n) Space* (1992) (51)
Near-optimal conversion of hardness into pseudo-randomness (1999) (51)
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness (2006) (51)
Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs (1995) (51)
One, two, three . . . infinity: lower bounds for parallel computation (1985) (50)
Derandomization that is rarely wrong from short advice that is typically good (2002) (49)
A Time-Space Tradeoff for Element Distinctness (1987) (48)
IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM (2012) (48)
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory (2017) (47)
Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes (2019) (47)
n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom (1993) (47)
Are search and decision programs computationally equivalent? (1985) (46)
An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs (2000) (46)
Discrepancy sets and pseudorandom generators for combinatorial rectangles (1996) (44)
Probabilistic communication complexity of Boolean relations (1989) (43)
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus (1997) (43)
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture (2014) (42)
Derandomizing homomorphism testing in general groups (2004) (39)
Non-commutative arithmetic circuits with division (2014) (39)
Degree and Sensitivity: tails of two distributions (2016) (38)
Short proofs are narrow—resolution made simple (1999) (38)
Interactive proofs of proximity: delegating computation in sublinear time (2013) (37)
Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs (1996) (36)
Barriers for Rank Methods in Arithmetic Complexity (2017) (36)
Computational Complexity Theory (2004) (36)
Randomized vs. deterministic decision tree complexity for read-once Boolean functions (1991) (34)
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals (2008) (34)
One-way multiparty communication lower bound for pointer jumping with applications (2007) (34)
Restriction access (2012) (33)
Invited Articles Foreword (2015) (33)
Constructing Small Sets that are Uniform in Arithmetic Progressions (1993) (33)
Population recovery and partial identification (2012) (33)
Linear Circuits over GF(2) (1990) (32)
Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes (2018) (32)
Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract) (1989) (32)
Hashing Functions can Simplify Zero-Knowledge Protocol Design (too) (1994) (32)
Perfect hashing, graph entropy, and circuit complexity (1990) (32)
On the Power of Finite Automata with Both Nondeterministic and Probabilistic States (1998) (31)
Techniques for bounding the convergence rate of genetic algorithms (1999) (31)
On Play by Means of Computing Machines (Preliminary Version).@@@A Theory of Higher Order Probabilities.@@@Knowledge and Efficient Computation.@@@Realizability Semantics for Error-Tolerant Logics (Preliminary Version). (1988) (31)
Universal Traversal Sequences for Expander Graphs (1993) (30)
Towards Optimal Deterministic Coding for Interactive Communication (2016) (30)
Boolean complexity classes vs. their arithmetic analogs (1996) (30)
Fractional Sylvester–Gallai theorems (2012) (29)
Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy (1995) (28)
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem (1986) (28)
Improved Derandomization of BPP Using a Hitting Set Generator (1999) (28)
Linear-Size Constant-Depth Polylog-Treshold Circuits (1991) (27)
Proof Complexity Lower Bounds from Algebraic Circuit Complexity (2016) (27)
Expanders In Group Algebras (2004) (27)
NL/poly /spl sube/ /spl oplus/L/poly (1994) (26)
Simplified Derandomization of BPP Using a Hitting Set Generator (2000) (26)
On a search problem related to branch-and-bound procedures (1986) (26)
A randomness-efficient sampler for matrix-valued functions and applications (2005) (26)
A method for obtaining randomized algorithms with small tail probabilities (1996) (26)
A direct sum theorem for corruption and the multiparty NOF communication complexity of set disjointness (2005) (26)
On derandomizing algorithms that err extremely rarely (2014) (25)
Breaking the quadratic barrier for 3-LCC's over the reals (2013) (25)
How discreet is the discrete log? (1983) (24)
Efficient Identification Schemes Using Two Prover Interactive Proofs (1989) (24)
Partial Derivatives in Arithmetic Complexity and Beyond (Foundations and Trends(R) in Theoretical Computer Science) (2011) (24)
Symmetric LDPC codes and local testing (2016) (23)
Non-deterministic communication complexity with few witnesses (1992) (23)
SL ⊆L4/3 (1997) (23)
A direct product theorem (1994) (23)
Search in a Known Pattern (1986) (22)
On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity (1993) (22)
The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)) (1988) (21)
Reducing The Seed Length In The Nisan-Wigderson Generator* (2006) (21)
Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version). (1995) (21)
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions (2013) (21)
How to Share Memory in a Distributed System (A Preliminary Version) (1984) (21)
A new approximate graph coloring algorithm (1982) (21)
Relationless Completeness and Separations (2010) (21)
Monotone Expanders: Constructions and Applications (2010) (21)
The uncertainty principle: variations on a theme (2020) (20)
Spherical Cubes and Rounding in High Dimensions (2008) (20)
Algebrization: a new barrier in complexity theory (2008) (20)
Computing Graph Properties by Randomized Subcube Partitions (2002) (19)
Iterative Construction of Cayley Expander Graphs (2006) (19)
On read-once threshold formulae and their randomized decision tree complexity (1990) (19)
Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions (2015) (19)
Multi-layer grid embeddings (1985) (19)
Mathematics and Computation: A Theory Revolutionizing Technology and Science (2019) (19)
Compressing and Teaching for Low VC-Dimension (2015) (18)
Algorithmic aspects of Brascamp-Lieb inequalities (2016) (18)
The amazing power of pairwise independence (abstract) (1994) (18)
NL/poly <= +/poly (Preliminary Version) (1994) (17)
A physical interpretation of graph connectivity, and its algorithmic applications (1986) (17)
A new family of Cayley expanders (?) (2004) (17)
The Fusion Method for Lower Bounds in Circuit Complexity (2003) (16)
Subexponential Circuits : Derandomizing the XOR Lemma (2003) (16)
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation (2017) (16)
A note on ex-tracting randomness from Santha-Vazirani sources (2004) (16)
Teaching and compressing for low VC-dimension (2015) (16)
Linear Systems over Composite Moduli (2009) (16)
On Randomness Extraction in AC0 (2015) (15)
Expanders from symmetric codes (2002) (15)
Not all keys can be hashed in constant time (1990) (14)
Explicit Capacity Approaching Coding for Interactive Communication (2018) (14)
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) (1985) (14)
On Pseudorandomness with respect to Deterministic Observes (2000) (14)
Pairwise Independence and Derandomization (Foundations and Trends(R) in Theoretical Computer Science) (2006) (14)
Towards a Study of Low-Complexity Graphs (2009) (14)
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications (2006) (13)
Undirected connectivity in o(\log1 (1989) (13)
Dynamic Parallel Memories (2018) (13)
Dispersers , Deterministic Ampli cation , and Weak RandomSources (1989) (13)
Deterministic amplification of space-bounded probabilistic algorithms (1999) (12)
The complexity of parallel computation on matroids (1985) (12)
On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern (1995) (12)
Quadratic Dynamical Systems (Preliminary Version) (1992) (12)
On the Complexity of Bilinear Forms (2002) (12)
On Computations with Integer Division (1988) (12)
Simulations among concurrent-write PRAMs (1988) (12)
Neighborly Embedded Manifolds (2008) (11)
Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing (1994) (11)
Search problems in algebraic complexity, GCT, and hardness of generators for invariant rings (2019) (11)
Probabilistic Communication Complexity of Boolean Relations (Extended Abstract) (1989) (11)
Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) (2019) (10)
On rank versus communication complexity (1995) (10)
Characterizing non-deterministic circuit size (1993) (10)
More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer (2019) (9)
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals (2017) (9)
On the power and limitations of branch and cut (2021) (8)
Spherical cubes (2012) (8)
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds (2019) (8)
Hardness vs. Randomness (Extended Abstract) (1988) (8)
Local Expanders (2017) (7)
Towards understanding exclusive read (1989) (7)
The Tree Model for Hashing: Lower and Upper Bounds (1996) (7)
The future of computational complexity theory: part I (1996) (7)
A lower bound on the area of permutation layouts (1991) (7)
Lecture Notes for the 22nd Mcgill Invitational Workshop on Computational Complexity (2010) (7)
Toward Understanding Exclusive Read (1990) (7)
Short Proofs are Narrow { Resolution made (2000) (6)
THE PARALLEL COMPLEXITY OF ELEMENT DISTINCTNESS IS f ( x / logn ) * (1988) (6)
EXPANDERS, EIGENVALUES, AND ALL THAT (2004) (6)
Computational Hardness and Explicit Constructions of Error Correcting Codes (2006) (6)
A New NCAlgorithm for Perfect Matching in Bipartite Cubic Graphs (1996) (6)
Expander Graphs and their Applications Draft-not for distribution (2006) (6)
Knowledge, Creativity and P versus NP (2009) (6)
On the power of finite automata with both nondeterministic and probabilistic states (preliminary version) (1994) (6)
How to Solve any Protocol (1987) (5)
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus (2002) (5)
Robustly self-ordered graphs: constructions and applications to property testing (2021) (5)
SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY (2012) (5)
Retraction of Wigderson-Xiao , “ A Randomness-Efficient Sampler for Matrix-valued Functions and Applications ” , ECCC TR 05-107 (2006) (4)
Superpolynomial Lower Bounds for Monotone Span Programs 1 (1996) (4)
Interactions of Computational Complexity Theory and Mathematics (2017) (4)
Spanoids - an abstraction of spanning structures, and a barrier for LCCs (2018) (4)
Subspace arrangements, graph rigidity and derandomization through submodular optimization (2019) (4)
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model (2022) (4)
On the Circuit Complexity of Perfect Hashing (1996) (4)
Mathematics and Computation (2019) (4)
NL/poly c @L/POlY (Preliminary Version) (1994) (4)
On the Security of Multi-Party Protocols in Distributed Systems (1982) (4)
Randomness extractors -- applications and constructions (2009) (4)
Proofs that Release Minimum Knowledge (1986) (3)
An Asymptotic Bound on the Composition Number of Integer Sums of Squares Formulas (2013) (3)
The Gödel Phenomena in Mathematics : A Modern View (2010) (3)
Technical Perspective: Low-depth arithmetic circuits (2017) (3)
Information Theoretic Reasons for Computational Difficulty (1990) (3)
Information Theory versus Complexity Theory: Another Test Case (1995) (3)
Depth through breadth, or why should we attend talks in other areas? (2004) (2)
Short Proofs Are Narrow - Resolution Made Simple (Abstract). (1999) (2)
Kurt Gödel and the Foundations of Mathematics: The Gödel Phenomenon in Mathematics: A Modern View (2011) (2)
De-randomizing BPP: the state of the art (1999) (2)
The Power and Weakness of Randomness in Computation (2006) (2)
Black Boxes , Incorporated (2009) (2)
O ct 2 01 7 Interactions of Computational Complexity Theory and Mathematics (2018) (2)
Public-Key Cryptography from Different Assumptions (Extended Abstract) (2010) (2)
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling (2018) (1)
On the Work of Madhu Sudan (2003) (1)
An Optimal "It Ain't Over Till It's Over" Theorem (2022) (1)
Do Probabilistic Algorithms Outperform Deterministic Ones? (1998) (1)
On Play by Means of Computing Machines .A Theory of Higher Order Probabilities.Knowledge and Efficient Computation.Realizability Semantics for Error-Tolerant Logics (1988) (1)
Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties (2020) (1)
C C ] 2 6 O ct 2 01 7 Barriers for Rank Methods in Arithmetic Complexity (2018) (1)
Zigzag Products, Expander Constructions, Connections, and Applications (2003) (1)
Expander codes over reals, Euclidean sections, and compressed sensing (2009) (1)
Operator Scaling : Theory , Applications and Connections 1 (2017) (1)
Perfect Hashing, Graph Entropy, and Circuit Complexity (preliminary version) (1990) (1)
Graphs and their Applications Lecture notes for a course (2003) (1)
NP and Mathematics – a computational complexity perspective (2006) (1)
The Wonders of the Digital Envelope - A Crash Course in Modern Cryptography (1994) (1)
III.24 Expanders (2010) (0)
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification (2022) (0)
An asymptotic bound on integer sums of squares (2009) (0)
Themes Complexity Theory ’ 94 In the months of August and September , 1994 (0)
A Necessity of Shared Randomness 5 Final Remarks (1997) (0)
Operator Scaling: Theory and Applications (2019) (0)
Quadratic Dynamical Systems ( Preliminary Version ) y (2019) (0)
On the interaction of TCS and Math (2014) (0)
Randomness Conductors and Constant-Degree Lossless Expanders [Extended Abstract] (2009) (0)
On the nature of the Theory of Computation (ToC) (2018) (0)
Simulations Among Concurrent-Write PRAMs Computation (2003) (0)
Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation (2020) (0)
Computational pseudo-randomness (1995) (0)
Optimal Seperation of Treelike and General Resolution Preliminary Version (1999) (0)
Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version) (1983) (0)
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network (2020) (0)
Polynomial time algorithms in invariant theory for torus actions (2021) (0)
Computational Complexity: a Conceptual Perspective Organization and Chapter Summaries (0)
The Power and Weakness of Randomness (When You are Short on Time) (2011) (0)
1 The Black-Box Power of Nondeterminism , Randomness , and Quantum Computation (2012) (0)
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds (2019) (0)
Average case complexity (2004) (0)
Randomness , Pseudorandomness and Derandomization Sept 15 th , 2010 Lecture Notes 2 : Cryptography and Pseudorandomness (0)
Non-commutative Optimization - Where Algebra, Analysis and Computational Complexity Meet (2022) (0)
COMPUTATIONAL INTRACTABILITY AND PSEUDORANDOMNESS The areas of computational intractability and pseudorandomness (2010) (0)
Example 4 in Subsection 3.2 We Proved That ~ R (1) (1994) (0)
Hardness vs. randomness-a survey (1989) (0)
Computational Complexity (2001) (0)
Near-Optimal Separation of Treelike andGeneral (2000) (0)
Symmetric LDPC codes and local testing (2015) (0)
IV.20 Computational Complexity (2010) (0)
Space-Time Tradeoffs for Graph Properties by Yevgeniy Dodis (0)
Randomness Conductors and Constant-Degree Lossless (2009) (0)
08w5094 Analytic Tools in Computational Complexity (2008) (0)
Randomness - A Computational Complexity Perspective (2008) (0)
Advances in Complexity Theory (2004) (0)
Quantum Computing Since Democritus, A Book Review (2014) (0)
3.1.1 Triangulating a Monotone Polygon 3.2 Range Minima 2.3.2 Query Retrieval 3.1 All Nearest Smaller Values 2.2 Preex Minima and All Nearest Smaller Values (1998) (0)
Space-time Tradeoos for Graph Properties Space-time Tradeoos for Graph Properties (1999) (0)
Fairness in Scheduling On-line Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing. In (1995) (0)
Timed Modal Specifications........ 8 (0)
Pairwise Independence and Derandomization Michael Luby (2006) (0)
Connections between graphs and matrix spaces (2022) (0)
Population recovery and partial identification (2015) (0)
Hardness vs. Randomness - A Survey (abstract). (1989) (0)
Studies in computational complexity (1983) (0)
Computational Complexity ( 10 w 5028 ) (2011) (0)
Association schemes, non-commutative polynomial tail estimates, and Lasserre lower bounds for planted clique (2013) (0)
Applications of the sum-product theorem in finite fields (2006) (0)
Probabilistic and Deterministic Approximations of the Permanent (abstract) (1999) (0)
THE COl\rIPLEXITY OF PARALLEL SORTING FriedheIm Meyer auf der Heide (1985) (0)
Local Expanders (2017) (0)
Characterizing Non-Deterministic Circuit Size (Four variations on one theme) (1993) (0)
Rubber bands, convex embeddings and connectivity (2007) (0)
The work of Leslie Valiant (2009) (0)

This paper list is powered by the following services:

Other Resources About Avi Wigderson

What Schools Are Affiliated With Avi Wigderson?

Avi Wigderson is affiliated with the following schools:

Avi Wigderson's AcademicInfluence.com Rankings

Computer Science