Avi Wigderson

Oded Goldreich, Avi Wigderson: On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. Electronic Colloquium on Computational Complexity (ECCC) 20: 43 (2013)

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

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. 41(6): 1722-1768 (2012)

Avi Wigderson, Amir Yehudayoff: Population Recovery and Partial Identification. FOCS 2012: 390-399

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff: Restriction access. ITCS 2012: 19-33

Zeev Dvir, Shubhangi Saraf, Avi Wigderson: Improved rank bounds for design matrices and a new proof of Kelly's theorem. CoRR abs/1211.0330 (2012)

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson: Sylvester-Gallai type theorems for approximate collinearity. CoRR abs/1211.0331 (2012)

Avi Wigderson, Amir Yehudayoff: Population Recovery and Partial Identification. Electronic Colloquium on Computational Complexity (ECCC) 19: 118 (2012)

Zeev Dvir, Shubhangi Saraf, Avi Wigderson: Improved rank bounds for design matrices and a new proof of Kelly's theorem. Electronic Colloquium on Computational Complexity (ECCC) 19: 138 (2012)

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson: Sylvester-Gallai type theorems for approximate collinearity. Electronic Colloquium on Computational Complexity (ECCC) 19: 139 (2012)

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff: Restriction Access. Electronic Colloquium on Computational Complexity (ECCC) 18: 160 (2011)

Xi Chen, Neeraj Kayal, Avi Wigderson: Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends in Theoretical Computer Science 6(1-2): 1-138 (2011)

Zeev Dvir, Avi Wigderson: Kakeya Sets, New Mergers, and Old Extractors. SIAM J. Comput. 40(3): 778-792 (2011)

Oded Goldreich, Avi Wigderson: On the Circuit Complexity of Perfect Hashing. Studies in Complexity and Cryptography 2011: 26-29

Oded Goldreich, Salil P. Vadhan, Avi Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator. Studies in Complexity and Cryptography 2011: 59-67

Oded Goldreich, Noam Nisan, Avi Wigderson: On Yao's XOR-Lemma. Studies in Complexity and Cryptography 2011: 273-301

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

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson: Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. J. ACM 57(4) (2010)

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

Zeev Dvir, Avi Wigderson: Monotone Expanders: Constructions and Applications. Theory of Computing 6(1): 291-308 (2010)

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff: Relationless Completeness and Separations. IEEE Conference on Computational Complexity 2010: 280-290

Tali Kaufman, Avi Wigderson: Symmetric LDPC Codes and Local Testing. ICS 2010: 406-421

Tali Kaufman, Avi Wigderson: Symmetric LDPC Codes and Local Testing. Property Testing 2010: 312-319

Benny Applebaum, Boaz Barak, Avi Wigderson: Public-key cryptography from different assumptions. STOC 2010: 171-180

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff: Non-commutative circuits and the sum-of-squares problem. STOC 2010: 667-676

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff: Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. CoRR abs/1009.4375 (2010)

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff: Non-commutative circuits and the sum-of-squares problem. Electronic Colloquium on Computational Complexity (ECCC) 17: 21 (2010)

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson: Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. Electronic Colloquium on Computational Complexity (ECCC) 17: 37 (2010)

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff: Relationless completeness and separations. Electronic Colloquium on Computational Complexity (ECCC) 17: 40 (2010)

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff: Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 149 (2010)

Zeev Dvir, Ariel Gabizon, Avi Wigderson: Extractors And Rank Extractors For Polynomial Sources. Computational Complexity 18(1): 1-58 (2009)

Emanuele Viola, Avi Wigderson: One-way multiparty communication lower bound for pointer jumping with applications. Combinatorica 29(6): 719-743 (2009)

Scott Aaronson, Avi Wigderson: Algebrization: A New Barrier in Complexity Theory. TOCT 1(1) (2009)

Arkadev Chattopadhyay, Avi Wigderson: Linear Systems over Composite Moduli. FOCS 2009: 43-52

Avi Wigderson: Randomness extractors -- applications and constructions. FSTTCS 2009: 471-473

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

Avi Wigderson: The work of Leslie Valiant. STOC 2009: 1-2

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New direct-product testers and 2-query PCPs. STOC 2009: 131-140

Arkadev Chattopadhyay, Avi Wigderson: Linear systems over composite moduli. Electronic Colloquium on Computational Complexity (ECCC) 16: 84 (2009)

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New Direct-Product Testers and 2-Query PCPs. Electronic Colloquium on Computational Complexity (ECCC) 16: 90 (2009)

Zeev Dvir, Avi Wigderson: Monotone expanders - constructions and applications. Electronic Colloquium on Computational Complexity (ECCC) 16: 135 (2009)

Gil Kalai, Avi Wigderson: Neighborly Embedded Manifolds. Discrete & Computational Geometry 40(3): 319-324 (2008)

Avi Wigderson, David Xiao: Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Theory of Computing 4(1): 53-76 (2008)

Emanuele Viola, Avi Wigderson: Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1): 137-168 (2008)

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

Avi Wigderson: Randomness - A Computational Complexity Perspective. CSR 2008: 1-2

Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson: Spherical Cubes and Rounding in High Dimensions. FOCS 2008: 189-198

Zeev Dvir, Avi Wigderson: Kakeya Sets, New Mergers and Old Extractors. FOCS 2008: 625-633

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform direct product theorems: simplified, optimized, and derandomized. STOC 2008: 579-588

Scott Aaronson, Avi Wigderson: Algebrization: a new barrier in complexity theory. STOC 2008: 731-740

Scott Aaronson, Avi Wigderson: Algebrization: A New Barrier in Complexity Theory. Electronic Colloquium on Computational Complexity (ECCC) 15(005) (2008)

Zeev Dvir, Avi Wigderson: Kakeya sets, new mergers and old extractors. Electronic Colloquium on Computational Complexity (ECCC) 15(058) (2008)

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electronic Colloquium on Computational Complexity (ECCC) 15(079) (2008)

Boaz Barak, Avi Wigderson: Public Key Cryptography from Different Assumptions. IACR Cryptology ePrint Archive 2008: 335 (2008)

Johan Håstad, Avi Wigderson: The Randomized Communication Complexity of Set Disjointness. Theory of Computing 3(1): 211-219 (2007)

Emanuele Viola, Avi Wigderson: Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. IEEE Conference on Computational Complexity 2007: 141-154

Zeev Dvir, Ariel Gabizon, Avi Wigderson: Extractors and Rank Extractors for Polynomial Sources. FOCS 2007: 52-62

Emanuele Viola, Avi Wigderson: One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. FOCS 2007: 427-437

Zeev Dvir, Ariel Gabizon, Avi Wigderson: Extractors and Rank Extractors for Polynomial Sources. Electronic Colloquium on Computational Complexity (ECCC) 14(056) (2007)

Emanuele Viola, Avi Wigderson: One-way multi-party communication lower bound for pointer jumping with applications. Electronic Colloquium on Computational Complexity (ECCC) 14(079) (2007)

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson: A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. Computational Complexity 15(4): 391-432 (2006)

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Reducing The Seed Length In The Nisan-Wigderson Generator. Combinatorica 26(6): 647-681 (2006)

Omer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing. SIAM J. Comput. 35(5): 1185-1209 (2006)

Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. SIAM J. Comput. 36(4): 1095-1118 (2006)

Amir Shpilka, Avi Wigderson: Derandomizing Homomorphism Testing in General Groups. SIAM J. Comput. 36(4): 1215-1230 (2006)

Eyal Rozenman, Aner Shalev, Avi Wigderson: Iterative Construction of Cayley Expander Graphs. Theory of Computing 2(1): 91-120 (2006)

Irit Dinur, Madhu Sudan, Avi Wigderson: Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM 2006: 304-315

Avi Wigderson: Applications of the Sum-Product Theorem in Finite Fields. IEEE Conference on Computational Complexity 2006: 111

Avi Wigderson: The Power and Weakness of Randomness in Computation. LATIN 2006: 28-29

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

Avi Wigderson, David Xiao: Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications. Electronic Colloquium on Computational Complexity (ECCC) 13(105) (2006)

Irit Dinur, Madhu Sudan, Avi Wigderson: Robust Local Testability of Tensor Products of LDPC Codes. Electronic Colloquium on Computational Complexity (ECCC) 13(118) (2006)

Michael Luby, Avi Wigderson: Pairwise Independence and Derandomization. Foundations and Trends in Theoretical Computer Science 1(4) (2005)

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson: A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. IEEE Conference on Computational Complexity 2005: 52-66

Avi Wigderson, David Xiao: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. FOCS 2005: 397-406

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson: Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. STOC 2005: 1-10

Avi Wigderson, David Xiao: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. Electronic Colloquium on Computational Complexity (ECCC)(107) (2005)

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near Optimal Separation Of Tree-Like And General Resolution. Combinatorica 24(4): 585-603 (2004)

Roy Meshulam, Avi Wigderson: Expanders In Group Algebras. Combinatorica 24(4): 659-680 (2004)

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

Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. FOCS 2004: 384-393

Amir Shpilka, Avi Wigderson: Derandomizing homomorphism testing in general groups. STOC 2004: 427-435

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

Avi Wigderson: Depth through breadth, or why should we attend talks in other areas? STOC 2004: 579

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

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

Avi Wigderson: Zigzag Products, Expander Constructions, Connections, and Applications. FSTTCS 2003: 443

Boaz Barak, Ronen Shaltiel, Avi Wigderson: Computational Analogues of Entropy. RANDOM-APPROX 2003: 200-215

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

Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. STOC 2003: 612-621

Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On interactive proofs with a laconic prover. Computational Complexity 11(1-2): 1-53 (2002)

Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao: Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. Combinatorica 22(4): 555-574 (2002)

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

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

Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Randomness Conductors and Constant-Degree Lossless Expanders. IEEE Conference on Computational Complexity 2002: 15

Roy Meshulam, Avi Wigderson: Expanders from Symmetric Codes. IEEE Conference on Computational Complexity 2002: 16

Ehud Friedgut, Jeff Kahn, Avi Wigderson: Computing Graph Properties by Randomized Subcube Partitions. RANDOM 2002: 105-113

Oded Goldreich, Avi Wigderson: Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good. RANDOM 2002: 209-223

Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Randomness conductors and constant-degree lossless expanders. STOC 2002: 659-668

Roy Meshulam, Avi Wigderson: Expanders from symmetric codes. STOC 2002: 669-677

Oded Goldreich, Avi Wigderson: Derandomization that is rarely wrong from short advice that is typically good. Electronic Colloquium on Computational Complexity (ECCC)(039) (2002)

Amir Shpilka, Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1): 1-27 (2001)

Eli Ben-Sasson, Avi Wigderson: Short proofs are narrow - resolution made simple. J. ACM 48(2): 149-169 (2001)

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

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. IEEE Conference on Computational Complexity 2001: 2-12

Johan Håstad, Avi Wigderson: Simple Analysis of Graph Tests for Linearity and PCP. IEEE Conference on Computational Complexity 2001: 244-254

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

Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover. ICALP 2001: 334-345

Omer Reingold, Salil P. Vadhan, Avi Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. Electronic Colloquium on Computational Complexity (ECCC) 8(18) (2001)

Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover. Electronic Colloquium on Computational Complexity (ECCC) 8(46) (2001)

Nathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica 20(4): 545-568 (2000)

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

Omer Reingold, Salil P. Vadhan, Avi Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. FOCS 2000: 3-13

Omer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing. FOCS 2000: 22-31

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53

Oded Goldreich, Avi Wigderson: On Pseudorandomness with respect to Deterministic Observes. ICALP Satellite Workshops 2000: 77-84

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length. STOC 2000: 1-10

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space complexity in propositional calculus. STOC 2000: 358-367

Oded Goldreich, Salil P. Vadhan, Avi Wigderson: Simplified derandomization of BPP using a hitting set generator. Electronic Colloquium on Computational Complexity (ECCC) 7(4) (2000)

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near-Optimal Separation of Treelike and General Resolution. Electronic Colloquium on Computational Complexity (ECCC) 7(5) (2000)

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length. Electronic Colloquium on Computational Complexity (ECCC) 7(9) (2000)

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. Electronic Colloquium on Computational Complexity (ECCC) 7(23) (2000)

Oded Goldreich, Avi Wigderson: On Pseudorandomness with respect to Deterministic Observers. Electronic Colloquium on Computational Complexity (ECCC) 7(56) (2000)

Omer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing. Electronic Colloquium on Computational Complexity (ECCC) 7(59) (2000)

Avi Wigderson, David Zuckerman: Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Combinatorica 19(1): 125-138 (1999)

László Babai, Anna Gál, Avi Wigderson: Superpolynomial Lower Bounds for Monotone Span Programs. Combinatorica 19(3): 301-319 (1999)

Yuri Rabinovich, Avi Wigderson: Techniques for bounding the convergence rate of genetic algorithms. Random Struct. Algorithms 14(2): 111-138 (1999)

Eli Ben-Sasson, Avi Wigderson: Short Proofs Are Narrow - Resolution Made Simple (Abstract). IEEE Conference on Computational Complexity 1999: 2

Avi Wigderson: De-Randomizing BPP: The State of the Art. IEEE Conference on Computational Complexity 1999: 76-

Amir Shpilka, Avi Wigderson: Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. IEEE Conference on Computational Complexity 1999: 87-

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson: Deterministic Amplification of Space-Bounded Probabilistic Algorithms. IEEE Conference on Computational Complexity 1999: 188-

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS 1999: 181-190

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

Oded Goldreich, Avi Wigderson: Improved Derandomization of BPP Using a Hitting Set Generator. RANDOM-APPROX 1999: 131-137

Eli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution Made Simple. STOC 1999: 517-526

Eli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution made Simple. Electronic Colloquium on Computational Complexity (ECCC) 6(22) (1999)

Amir Shpilka, Avi Wigderson: Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. Electronic Colloquium on Computational Complexity (ECCC) 6(23) (1999)

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus. Electronic Colloquium on Computational Complexity (ECCC)(40) (1999)

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

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

Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson: The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351

Russell Impagliazzo, Avi Wigderson: Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS 1998: 734-743

Avi Wigderson: Do Probabilistic Algorithms Outperform Deterministic Ones? ICALP 1998: 212-214

Harry Buhrman, Richard Cleve, Avi Wigderson: Quantum vs. Classical Communication and Computation. STOC 1998: 63-68

Nathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. STOC 1998: 644-652

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson: Deterministic Amplification of Space Bounded Probabilistic Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 5(72) (1998)

Noam Nisan, Avi Wigderson: Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity 6(3): 217-234 (1997)

Oded Goldreich, Avi Wigderson: Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Struct. Algorithms 11(4): 315-343 (1997)

Oded Goldreich, Avi Wigderson: Theory of computing: a scientific perspective (extended abstract). SIGACT News 28(3): 100-102 (1997)

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

Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou: SL <= L^4/3. STOC 1997: 230-239

Itzhak Parnafes, Ran Raz, Avi Wigderson: Direct Product Results and the GCD Problem, in Old and New Communication Models. STOC 1997: 363-372

Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao: Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. STOC 1997: 739-748

Helmut Alt, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, Avi Wigderson: A Method for Obtaining Randomized Algorithms with Small Tail Probabilities. Algorithmica 16(4/5): 543-547 (1996)

Oded Goldreich, Avi Wigderson: Theory of Computing: A Scientific Perspective. ACM Comput. Surv. 28(4es): 218 (1996)

Anna Gál, Avi Wigderson: Boolean complexity classes vs. their arithmetic analogs. Random Struct. Algorithms 9(1-2): 99-111 (1996)

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

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

Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou: Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. FOCS 1996: 412-421

Roded Sharan, Avi Wigderson: A New NCAlgorithm for Perfect Matching in Bipartite Cubic Graphs. ISTCS 1996: 202-207

László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson: Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. STOC 1996: 603-611

Oded Goldreich, Avi Wigderson: On the Circuit Complexity of Perfect Hashing. Electronic Colloquium on Computational Complexity (ECCC) 3(41) (1996)

Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman: Derandomized Graph Products. Computational Complexity 5(1): 60-75 (1995)

Mauricio Karchmer, Ran Raz, Avi Wigderson: Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Computational Complexity 5(3/4): 191-204 (1995)

Joel Friedman, Avi Wigderson: On the Second Eigenvalue of Hypergraphs. Combinatorica 15(1): 43-65 (1995)

Noam Nisan, Avi Wigderson: On Rank vs. Communication Complexity. Combinatorica 15(4): 557-565 (1995)

László Lovász, Moni Naor, Ilan Newman, Avi Wigderson: Search Problems in the Decision Tree Model. SIAM J. Discrete Math. 8(1): 119-132 (1995)

Ilan Newman, Avi Wigderson: Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. SIAM J. Discrete Math. 8(4): 536-542 (1995)

Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson: Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs. CRYPTO 1995: 325-338

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

Avi Wigderson: Computational Pseudo-Randomness. ISTCS 1995: 218-219

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On data structures and asymmetric communication complexity. STOC 1995: 103-111

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

Anna Gál, Avi Wigderson: Boolean Complexity Classes vs. Their Arithmetic Analogs. Electronic Colloquium on Computational Complexity (ECCC) 2(49) (1995)

Oded Goldreich, Noam Nisan, Avi Wigderson: On Yao's XOR-Lemma. Electronic Colloquium on Computational Complexity (ECCC) 2(50) (1995)

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

Noam Nisan, Avi Wigderson: Hardness vs Randomness. J. Comput. Syst. Sci. 49(2): 149-167 (1994)

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

Avi Wigderson: NL/poly <= +/poly (Preliminary Version). Structure in Complexity Theory Conference 1994: 59-62

Russell Impagliazzo, Ran Raz, Avi Wigderson: A Direct Product Theorem. Structure in Complexity Theory Conference 1994: 88-96

Noam Nisan, Avi Wigderson: On Rank vs. Communication Complexity. FOCS 1994: 831-836

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

Russell Impagliazzo, Noam Nisan, Avi Wigderson: Pseudorandomness for network algorithms. STOC 1994: 356-364

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

Avi Wigderson: The amazing power of pairwise independence (abstract). STOC 1994: 645-647

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

Noam Nisan, Avi Wigderson: On Rank vs. Communication Complexity. Electronic Colloquium on Computational Complexity (ECCC) 1(1) (1994)

Oded Goldreich, Avi Wigderson: Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing. Electronic Colloquium on Computational Complexity (ECCC) 1(2) (1994)

László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson: BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity 3: 307-318 (1993)

Alexander A. Razborov, Endre Szemerédi, Avi Wigderson: Constructing Small Sets that are Uniform in Arithmetic Progressions. Combinatorics, Probability & Computing 2: 513-518 (1993)

Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson: Combinatorial characterization of read-once formulae. Discrete Mathematics 114(1-3): 275-282 (1993)

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

Shlomo Hoory, Avi Wigderson: Universal Traversal Sequences for Expander Graphs. Inf. Process. Lett. 46(2): 67-69 (1993)

Noam Nisan, Avi Wigderson: Rounds in Communication Complexity Revisited. SIAM J. Comput. 22(1): 211-219 (1993)

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

Mauricio Karchmer, Avi Wigderson: On Span Programs. Structure in Complexity Theory Conference 1993: 102-111

Rafail Ostrovsky, Avi Wigderson: One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge. ISTCS 1993: 3-17

Michael Luby, Boban Velickovic, Avi Wigderson: Deterministic Approximate Counting of Depth-2 Circuits. ISTCS 1993: 18-24

Avi Wigderson, David Zuckerman: Expanders that beat the eigenvalue bound: explicit construction and applications. STOC 1993: 245-251

Mauricio Karchmer, Avi Wigderson: Characterizing non-deterministic circuit size. STOC 1993: 532-540

Joseph Gil, William L. Steiger, Avi Wigderson: Geometric medians. Discrete Mathematics 108(1-3): 37-51 (1992)

Ran Raz, Avi Wigderson: Monotone Circuits for Matching Require Linear Depth. J. ACM 39(3): 736-744 (1992)

Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson: Non-deterministic Communication Complexity with Few Witness. Structure in Complexity Theory Conference 1992: 275-281

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

Yuri Rabinovich, Alistair Sinclair, Avi Wigderson: Quadratic Dynamical Systems (Preliminary Version). FOCS 1992: 304-313

Avi Wigderson: The Complexity of Graph Connectivity. MFCS 1992: 112-132

S. Rao Kosaraju, Mike Fellows, Avi Wigderson, John A. Ellis (Eds.): Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada. ACM 1992, isbn 0-89791-511-9

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

Rafi Heiman, Avi Wigderson: Randomized VS. Deterministic Decision Tree Complexity for Read-Once Boolean Functions. Computational Complexity 1: 311-329 (1991)

Prabhakar Ragde, Avi Wigderson: Linear-Size Constant-Depth Polylog-Treshold Circuits. Inf. Process. Lett. 39(3): 143-146 (1991)

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

Rafi Heiman, Avi Wigderson: Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions. Structure in Complexity Theory Conference 1991: 172-179

Mauricio Karchmer, Ran Raz, Avi Wigderson: Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity. Structure in Complexity Theory Conference 1991: 299-304

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

Yuri Rabinovich, Avi Wigderson: An Analysis of a Simple Genetic Algorithm. ICGA 1991: 215-221

Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson: Self-Testing/Correcting for Polynomials and for Approximate Functions. STOC 1991: 32-42

Noam Nisan, Avi Wigderson: Rounds in Communication Complexity Revisited. STOC 1991: 419-429

Faith E. Fich, Avi Wigderson: Toward Understanding Exclusive Read. SIAM J. Comput. 19(4): 718-727 (1990)

Noga Alon, Mauricio Karchmer, Avi Wigderson: Linear Circuits over GF(2). SIAM J. Comput. 19(6): 1064-1067 (1990)

Mauricio Karchmer, Avi Wigderson: Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discrete Math. 3(2): 255-265 (1990)

Rafi Heiman, Ilan Newman, Avi Wigderson: On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity. Structure in Complexity Theory Conference 1990: 78-87

Ilan Newman, Prabhakar Ragde, Avi Wigderson: Perfect Hashing, Graph Entropy, and Circuit Complexity. Structure in Complexity Theory Conference 1990: 91-99

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

Ran Raz, Avi Wigderson: Monotone Circuits for Matching Require Linear Depth. STOC 1990: 287-292

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

Bettina Just, Friedhelm Meyer auf der Heide, Avi Wigderson: On Computations with Integer Division. ITA 23(1): 101-111 (1989)

Noam Nisan, Avi Wigderson: Hardness vs. Randomness - A Survey (abstract). Structure in Complexity Theory Conference 1989: 54

Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson: Efficient Identification Schemes Using Two Prover Interactive Proofs. CRYPTO 1989: 498-506

Aviad Cohen, Avi Wigderson: Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract). FOCS 1989: 14-19

Ran Raz, Avi Wigderson: Probabilistic Communication Complexity of Boolean Relations (Extended Abstract). FOCS 1989: 562-567

Faith E. Fich, Avi Wigderson: Towards Understanding Exclusive Read. SPAA 1989: 76-82

Faith E. Fich, Prabhakar Ragde, Avi Wigderson: Simulations Among Concurrent-Write PRAMs. Algorithmica 3: 43-51 (1988)

Nathan Linial, László Lovász, Avi Wigderson: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1): 91-102 (1988)

Richard M. Karp, Eli Upfal, Avi Wigderson: The Complexity of Parallel Search. J. Comput. Syst. Sci. 36(2): 225-253 (1988)

Douglas L. Long, Avi Wigderson: The Discrete Logarithm Hides O(log n) Bits. SIAM J. Comput. 17(2): 363-372 (1988)

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

Prabhakar Ragde, William L. Steiger, Endre Szemerédi, Avi Wigderson: The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)). SIAM J. Discrete Math. 1(3): 399-410 (1988)

Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. Theor. Comput. Sci. 58: 57-68 (1988)

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

Bettina Just, Friedhelm Meyer auf der Heide, Avi Wigderson: On Computations with Integer Division. STACS 1988: 29-37

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

Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson: Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions. STOC 1988: 113-131

Mauricio Karchmer, Avi Wigderson: Monotone Circuits for Connectivity Require Super-logarithmic Depth. STOC 1988: 539-550

Eli Upfal, Avi Wigderson: How to share memory in a distributed system. J. ACM 34(1): 116-127 (1987)

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

Friedhelm Meyer auf der Heide, Avi Wigderson: The Complexity of Parallel Sorting. SIAM J. Comput. 16(1): 100-107 (1987)

Oded Goldreich, Silvio Micali, Avi Wigderson: How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. STOC 1987: 218-229

Richard M. Karp, Eli Upfal, Avi Wigderson: Constructing a perfect matching is in random NC. Combinatorica 6(1): 35-48 (1986)

Oded Goldreich, Silvio Micali, Avi Wigderson: How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. CRYPTO 1986: 171-185

Richard M. Karp, Michael E. Saks, Avi Wigderson: On a Search Problem Related to Branch-and-Bound Procedures. FOCS 1986: 19-28

Michael E. Saks, Avi Wigderson: Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. FOCS 1986: 29-38

Nathan Linial, László Lovász, Avi Wigderson: A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications. FOCS 1986: 39-48

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

Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. ICALP 1986: 50-59

Oded Goldreich, Silvio Micali, Avi Wigderson: Proofs that Release Minimum Knowledge. MFCS 1986: 639-650

Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Time-Space Tradeoff for Element Distinctness. STACS 1986: 353-358

Nimrod Megiddo, Avi Wigderson: On Play by Means of Computing Machines. TARK 1986: 259-274

Richard M. Karp, Avi Wigderson: A Fast Parallel Algorithm for the Maximal Independent Set Problem. J. ACM 32(4): 762-773 (1985)

Uzi Vishkin, Avi Wigderson: Trade-Offs Between Depth and Width in Parallel Computation. SIAM J. Comput. 14(2): 303-314 (1985)

Gopalakrishnan Vijayan, Avi Wigderson: Rectilinear Graphs and their Embeddings. SIAM J. Comput. 14(2): 355-372 (1985)

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

Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson: Multi-Layer Grid Embeddings. FOCS 1985: 186-196

Friedhelm Meyer auf der Heide, Avi Wigderson: The Complexity of Parallel Sorting. FOCS 1985: 532-540

Richard M. Karp, Eli Upfal, Avi Wigderson: The Complexity of Parallel Computation on Matroids. FOCS 1985: 541-550

Richard M. Karp, Eli Upfal, Avi Wigderson: Constructing a Perfect Matching is in Random NC. STOC 1985: 22-32

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

Richard M. Karp, Eli Upfal, Avi Wigderson: Are Search and Decision Problems Computationally Equivalent? STOC 1985: 464-475

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

Faith E. Fich, Prabhakar Ragde, Avi Wigderson: Relations Between Concurrent-Write Models of Parallel Computation. PODC 1984: 179-189

Richard M. Karp, Avi Wigderson: A Fast Parallel Algorithm for the Maximal Independent Set Problem. STOC 1984: 266-272

Uzi Vishkin, Avi Wigderson: Dynamic Parallel Memories. Information and Control 56(3): 174-182 (1983)

Hana Galperin, Avi Wigderson: Succinct Representations of Graphs. Information and Control 56(3): 183-198 (1983)

Avi Wigderson: Improving the Performance Guarantee for Approximate Graph Coloring. J. ACM 30(4): 729-735 (1983)

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

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

Douglas L. Long, Avi Wigderson: How Discreet is the Discrete Log? STOC 1983: 413-420

Danny Dolev, Avi Wigderson: On the Security of Multi-Party Protocols in Distributed Systems. CRYPTO 1982: 167-175

Avi Wigderson: A New Approximate Graph Coloring Algorithm. STOC 1982: 325-329