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