| 2024 | FOCS | Constant-Depth Arithmetic Circuits for Linear Algebra Problems. | Robert Andrews, Avi Wigderson |
| 2023 | STOC | An Optimal "It Ain't Over Till It's Over" Theorem. | Ronen Eldan, Avi Wigderson, Pei Wu |
| 2022 | FOCS | Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. | Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson |
| 2022 | ISSAC | Non-commutative Optimization - Where Algebra, Analysis and Computational Complexity Meet. | Avi Wigderson |
| 2021 | FOCS | Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. | Oded Goldreich, Avi Wigderson |
| 2020 | FOCS | Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties. | Visu Makam, Avi Wigderson |
| 2019 | FOCS | Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes. | Peter Brgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson |
| 2019 | FOCS | More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer. | Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson |
| 2018 | FOCS | Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes. | Peter Brgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson |
| 2018 | STOC | Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. | Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson |
| 2017 | FOCS | Much Faster Algorithms for Matrix Scaling. | Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson |
| 2017 | STOC | Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. | Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
| 2016 | FOCS | A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. | Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
| 2016 | SODA | Towards Optimal Deterministic Coding for Interactive Communication. | Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson |
| 2015 | FOCS | Compressing and Teaching for Low VC-Dimension. | Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff |
| 2015 | STOC | Reed-Muller Codes for Random Erasures and Errors. | Emmanuel Abbe, Amir Shpilka, Avi Wigderson |
| 2015 | STOC | Sum-of-squares Lower Bounds for Planted Clique. | Raghu Meka, Aaron Potechin, Avi Wigderson |
| 2014 | STOC | Breaking the quadratic barrier for 3-LCC's over the reals. | Zeev Dvir, Shubhangi Saraf, Avi Wigderson |
| 2014 | STOC | Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. | Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson |
| 2014 | STOC | On derandomizing algorithms that err extremely rarely. | Oded Goldreich, Avi Wigderson |
| 2013 | STOC | Interactive proofs of proximity: delegating computation in sublinear time. | Guy N. Rothblum, Salil P. Vadhan, Avi Wigderson |
| 2012 | FOCS | Population Recovery and Partial Identification. | Avi Wigderson, Amir Yehudayoff |
| 2011 | STOC | Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. | Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson |
| 2010 | STOC | Public-key cryptography from different assumptions. | Benny Applebaum, Boaz Barak, Avi Wigderson |
| 2010 | STOC | Non-commutative circuits and the sum-of-squares problem. | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
| 2009 | FOCS | Linear Systems over Composite Moduli. | Arkadev Chattopadhyay, Avi Wigderson |
| 2009 | ICALP | Towards a Study of Low-Complexity Graphs. | Sanjeev Arora, David Steurer, Avi Wigderson |
| 2009 | STOC | New direct-product testers and 2-query PCPs. | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
| 2009 | STOC | The work of Leslie Valiant. | Avi Wigderson |
| 2008 | CSR | Randomness - A Computational Complexity Perspective. | Avi Wigderson |
| 2008 | FOCS | Kakeya Sets, New Mergers and Old Extractors. | Zeev Dvir, Avi Wigderson |
| 2008 | FOCS | Spherical Cubes and Rounding in High Dimensions. | Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson |
| 2008 | STOC | Algebrization: a new barrier in complexity theory. | Scott Aaronson, Avi Wigderson |
| 2008 | STOC | Uniform direct product theorems: simplified, optimized, and derandomized. | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson |
| 2007 | FOCS | Extractors and Rank Extractors for Polynomial Sources. | Zeev Dvir, Ariel Gabizon, Avi Wigderson |
| 2007 | FOCS | One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. | Emanuele Viola, Avi Wigderson |
| 2006 | LATIN | The Power and Weakness of Randomness in Computation. | Avi Wigderson |
| 2006 | STOC | 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. | Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson |
| 2005 | FOCS | A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. | Avi Wigderson, David Xiao |
| 2005 | STOC | Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. | Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson |
| 2004 | FOCS | Extracting Randomness Using Few Independent Sources. | Boaz Barak, Russell Impagliazzo, Avi Wigderson |
| 2004 | STOC | A new family of Cayley expanders (?). | Eyal Rozenman, Aner Shalev, Avi Wigderson |
| 2004 | STOC | Derandomizing homomorphism testing in general groups. | Amir Shpilka, Avi Wigderson |
| 2004 | STOC | Depth through breadth, or why should we attend talks in other areas? | Avi Wigderson |
| 2003 | STOC | Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. | Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson |
| 2003 | STOC | Extractors: optimal up to constant factors. | Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2002 | STOC | Randomness conductors and constant-degree lossless expanders. | Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2002 | STOC | Expanders from symmetric codes. | Roy Meshulam, Avi Wigderson |
| 2001 | FOCS | Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. | Noga Alon, Alexander Lubotzky, Avi Wigderson |
| 2001 | ICALP | On Interactive Proofs with a Laconic Prover. | Oded Goldreich, Salil P. Vadhan, Avi Wigderson |
| 2000 | FOCS | Pseudorandom Generators in Propositional Proof Complexity. | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 2000 | FOCS | Extracting Randomness via Repeated Condensing. | Omer Reingold, Ronen Shaltiel, Avi Wigderson |
| 2000 | FOCS | Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. | Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2000 | ICALP | On Pseudorandomness with respect to Deterministic Observes. | Oded Goldreich, Avi Wigderson |
| 2000 | STOC | Space complexity in propositional calculus. | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 2000 | STOC | Extractors and pseudo-random generators with optimal seed length. | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson |
| 1999 | FOCS | Near-Optimal Conversion of Hardness into Pseudo-Randomness. | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson |
| 1999 | STOC | Short Proofs are Narrow - Resolution Made Simple. | Eli Ben-Sasson, Avi Wigderson |
| 1998 | FOCS | The Quantum Communication Complexity of Sampling. | Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson |
| 1998 | FOCS | Randomness vs. Time: De-Randomization under a Uniform Assumption. | Russell Impagliazzo, Avi Wigderson |
| 1998 | ICALP | Do Probabilistic Algorithms Outperform Deterministic Ones? | Avi Wigderson |
| 1998 | STOC | Quantum vs. Classical Communication and Computation. | Harry Buhrman, Richard Cleve, Avi Wigderson |
| 1998 | STOC | A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. | Nathan Linial, Alex Samorodnitsky, Avi Wigderson |
| 1997 | STOC | SL <= L | Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou |
| 1997 | STOC | Untitled record | Russell Impagliazzo, Avi Wigderson |
| 1997 | STOC | Direct Product Results and the GCD Problem, in Old and New Communication Models. | Itzhak Parnafes, Ran Raz, Avi Wigderson |
| 1997 | STOC | Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. | Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao |
| 1996 | FOCS | Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. | Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou |
| 1996 | STOC | Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. | Lszl Babai, Anna Gl, Jnos Kollr, Lajos Rnyai, Tibor Szab, Avi Wigderson |
| 1995 | CRYPTO | Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs. | Ivan Damgrd, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson |
| 1995 | FOCS | Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version). | Noam Nisan, Avi Wigderson |
| 1995 | STOC | On data structures and asymmetric communication complexity. | Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson |
| 1995 | STOC | On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern. | Noam Nisan, Avi Wigderson |
| 1994 | FOCS | On Rank vs. Communication Complexity | Noam Nisan, Avi Wigderson |
| 1994 | STOC | On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). | Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson |
| 1994 | STOC | Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. | Oded Goldreich, Avi Wigderson |
| 1994 | STOC | Pseudorandomness for network algorithms. | Russell Impagliazzo, Noam Nisan, Avi Wigderson |
| 1994 | STOC | The amazing power of pairwise independence (abstract). | Avi Wigderson |
| 1993 | STOC | Characterizing non-deterministic circuit size. | Mauricio Karchmer, Avi Wigderson |
| 1993 | STOC | Expanders that beat the eigenvalue bound: explicit construction and applications. | Avi Wigderson, David Zuckerman |
| 1992 | FOCS | Undirected Connectivity in O(log ^1.5 n) Space | Noam Nisan, Endre Szemerdi, Avi Wigderson |
| 1992 | FOCS | Quadratic Dynamical Systems (Preliminary Version) | Yuri Rabinovich, Alistair Sinclair, Avi Wigderson |
| 1992 | MFCS | The Complexity of Graph Connectivity. | Avi Wigderson |
| 1991 | FOCS | Search Problems in the Decision Tree Model (Preliminary Version) | Lszl Lovsz, Moni Naor, Ilan Newman, Avi Wigderson |
| 1991 | STOC | Self-Testing/Correcting for Polynomials and for Approximate Functions | Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson |
| 1991 | STOC | Rounds in Communication Complexity Revisited | Noam Nisan, Avi Wigderson |
| 1990 | STOC | On the Power of Randomization in Online Algorithms (Extended Abstract) | Shai Ben-David, Allan Borodin, Richard M. Karp, Gbor Tardos, Avi Wigderson |
| 1990 | STOC | Not All Keys Can Be Hashed in Constant Time (Preliminary Version) | Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson |
| 1990 | STOC | Monotone Circuits for Matching Require Linear Depth | Ran Raz, Avi Wigderson |
| 1989 | CRYPTO | Efficient Identification Schemes Using Two Prover Interactive Proofs. | Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson |
| 1989 | FOCS | Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract) | Aviad Cohen, Avi Wigderson |
| 1989 | FOCS | Probabilistic Communication Complexity of Boolean Relations (Extended Abstract) | Ran Raz, Avi Wigderson |
| 1989 | SPAA | Towards Understanding Exclusive Read. | Faith E. Fich, Avi Wigderson |
| 1988 | FOCS | Hardness vs. Randomness (Extended Abstract) | Noam Nisan, Avi Wigderson |
| 1988 | STOC | Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions | Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson |
| 1988 | STOC | Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract) | Michael Ben-Or, Shafi Goldwasser, Avi Wigderson |
| 1988 | STOC | Monotone Circuits for Connectivity Require Super-logarithmic Depth | Mauricio Karchmer, Avi Wigderson |
| 1988 | STACS | On Computations with Integer Division. | Bettina Just, Friedhelm Meyer auf der Heide, Avi Wigderson |
| 1987 | STOC | How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority | Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1986 | CRYPTO | How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. | Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1986 | FOCS | Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract) | Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1986 | FOCS | On a Search Problem Related to Branch-and-Bound Procedures | Richard M. Karp, Michael E. Saks, Avi Wigderson |
| 1986 | FOCS | A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications | Nathan Linial, Lszl Lovsz, Avi Wigderson |
| 1986 | FOCS | Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees | Michael E. Saks, Avi Wigderson |
| 1986 | ICALP | A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. | Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson |
| 1986 | MFCS | Proofs that Release Minimum Knowledge. | Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1986 | STACS | A Time-Space Tradeoff for Element Distinctness. | Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson |
| 1986 | TARK | On Play by Means of Computing Machines. | Nimrod Megiddo, Avi Wigderson |
| 1985 | FOCS | Multi-Layer Grid Embeddings | Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson |
| 1985 | FOCS | Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) | Mikls Ajtai, Avi Wigderson |
| 1985 | FOCS | The Complexity of Parallel Sorting | Friedhelm Meyer auf der Heide, Avi Wigderson |
| 1985 | FOCS | The Complexity of Parallel Computation on Matroids | Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | STOC | One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation | Faith E. Fich, Friedhelm Meyer auf der Heide, Prabhakar Ragde, Avi Wigderson |
| 1985 | STOC | Constructing a Perfect Matching is in Random NC | Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | STOC | Are Search and Decision Problems Computationally Equivalent? | Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1984 | FOCS | How to Share Memory in a Distributed System (A Preliminary Version) | Eli Upfal, Avi Wigderson |
| 1984 | PODC | Relations Between Concurrent-Write Models of Parallel Computation. | Faith E. Fich, Prabhakar Ragde, Avi Wigderson |
| 1984 | STOC | A Fast Parallel Algorithm for the Maximal Independent Set Problem | Richard M. Karp, Avi Wigderson |
| 1983 | FOCS | Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version) | Uzi Vishkin, Avi Wigderson |
| 1983 | STOC | Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version) | Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson |
| 1983 | STOC | How Discreet is the Discrete Log? | Douglas L. Long, Avi Wigderson |
| 1982 | CRYPTO | On the Security of Multi-Party Protocols in Distributed Systems. | Danny Dolev, Avi Wigderson |
| 1982 | STOC | A New Approximate Graph Coloring Algorithm | Avi Wigderson |