Avi Wigderson - RankMe

396 papers A* 112A 30B 6Misc 1Journal 207Unranked 29

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification. SIAM J. Comput. Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson
2025	J	`jnl`	On Linear-Algebraic Notions of Expansion. Theory Comput. Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
2025	A	`conf`	Sparser Abelian High Dimensional Expanders. CCC Yotam Dikstein, Siqi Liu, Avi Wigderson
2025	J	`jnl`	The communication complexity of distributed estimation. CoRR Parikshit Gopalan, Raghu Meka, Prasad Raghavendra, Mihir Singhal, Avi Wigderson
2024	A	`conf`	Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. CCC Peter Bürgisser, Mahmut Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
2024	J	`jnl`	Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture. CoRR Peter Bürgisser, Mahmut Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
2024	A*	`conf`	Constant-Depth Arithmetic Circuits for Linear Algebra Problems. FOCS Robert Andrews, Avi Wigderson
2024	J	`jnl`	Constant-Depth Arithmetic Circuits for Linear Algebra Problems. CoRR Robert Andrews, Avi Wigderson
2024	J	`jnl`	Constant-Depth Arithmetic Circuits for Linear Algebra Problems. Electron. Colloquium Comput. Complex. Robert Andrews, Avi Wigderson
2024	J	`jnl`	Sparser Abelian High Dimensional Expanders. CoRR Yotam Dikstein, Siqi Liu, Avi Wigderson
2023	A*	`conf`	An Optimal "It Ain't Over Till It's Over" Theorem. STOC Ronen Eldan, Avi Wigderson, Pei Wu
2023	J	`jnl`	On linear-algebraic notions of expansion. Electron. Colloquium Comput. Complex. Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
2022	A*	`conf`	Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. FOCS Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson
2022	J	`jnl`	Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. CoRR Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson
2022	J	`jnl`	An Optimal "It Ain't Over Till It's Over" Theorem. CoRR Ronen Eldan, Avi Wigderson, Pei Wu
2022	J	`jnl`	Connections between graphs and matrix spaces. CoRR Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
2022	B	`conf`	Non-commutative Optimization - Where Algebra, Analysis and Computational Complexity Meet. ISSAC Avi Wigderson
2022	J	`jnl`	On linear-algebraic notions of expansion. CoRR Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
2022	J	`jnl`	Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. TheoretiCS Oded Goldreich, Avi Wigderson
2021	A*	`conf`	Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. FOCS Oded Goldreich, Avi Wigderson
2021	A	`conf`	On the Power and Limitations of Branch and Cut. CCC Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021	J	`jnl`	On the Power and Limitations of Branch and Cut. CoRR Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021	J	`jnl`	On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021	A	`conf`	Polynomial Time Algorithms in Invariant Theory for Torus Actions. CCC Peter Bürgisser, M. Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
2021	J	`jnl`	Polynomial time algorithms in invariant theory for torus actions. CoRR Peter Bürgisser, M. Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
2021	J	`jnl`	Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Theory Comput. Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2021	A	`conf`	Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. CCC Oded Goldreich, Avi Wigderson
2021	J	`jnl`	Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. CoRR Oded Goldreich, Avi Wigderson
2020	J	`jnl`	Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network. Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
2020	J	`jnl`	Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
2020	—	`ch.`	On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. Computational Complexity and Property Testing Oded Goldreich, Avi Wigderson
2020	J	`jnl`	Operator Scaling: Theory and Applications. Found. Comput. Math. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
2020	J	`jnl`	Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
2020	A	`conf`	Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. CCC Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
2020	J	`jnl`	Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. SIAM J. Comput. Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson
2020	A*	`conf`	Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties. FOCS Visu Makam, Avi Wigderson
2020	J	`jnl`	The uncertainty principle: variations on a theme. CoRR Avi Wigderson, Yuval Wigderson
2019	—	`ch.`	Completeness theorems for non-cryptographic fault-tolerant distributed computation. Providing Sound Foundations for Cryptography Michael Ben-Or, Shafi Goldwasser, Avi Wigderson
2019	—	`ch.`	How to play any mental game, or a completeness theorem for protocols with honest majority. Providing Sound Foundations for Cryptography Oded Goldreich, Silvio Micali, Avi Wigderson
2019	A*	`conf`	More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer. FOCS Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
2019	J	`jnl`	More barriers for rank methods, via a "numeric to symbolic" transfer. CoRR Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
2019	—	`ch.`	Multi-prover interactive proofs: how to remove intractability assumptions. Providing Sound Foundations for Cryptography Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson
2019	J	`jnl`	Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. Comput. Complex. Or Meir, Avi Wigderson
2019	—	`ch.`	Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. Providing Sound Foundations for Cryptography Oded Goldreich, Silvio Micali, Avi Wigderson
2019	J	`jnl`	Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. CoRR Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
2019	J	`jnl`	Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. Electron. Colloquium Comput. Complex. Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
2019	J	`jnl`	Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). CoRR Visu Makam, Avi Wigderson
2019	J	`jnl`	Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). Electron. Colloquium Comput. Complex. Visu Makam, Avi Wigderson
2019	A	`conf`	Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. ITCS Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson
2019	J	`jnl`	Subspace arrangements, graph rigidity and derandomization through submodular optimization. CoRR Orit E. Raz, Avi Wigderson
2019	A*	`conf`	Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes. FOCS Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
2019	J	`jnl`	Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. CoRR Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
2018	A	`conf`	Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. ITCS Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
2018	A	`conf`	Barriers for Rank Methods in Arithmetic Complexity. ITCS Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
2018	A*	`conf`	Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes. FOCS Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
2018	J	`jnl`	Efficient algorithms for tensor scaling, quantum marginals and moment polytopes. CoRR Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
2018	J	`jnl`	Explicit Capacity Approaching Coding for Interactive Communication. IEEE Trans. Inf. Theory Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
2018	J	`jnl`	Local Expanders. Comput. Complex. Emanuele Viola, Avi Wigderson
2018	J	`jnl`	On the nature of the Theory of Computation (ToC). Electron. Colloquium Comput. Complex. Avi Wigderson
2018	J	`jnl`	Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing. CoRR Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
2018	A*	`conf`	Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. STOC Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
2018	J	`jnl`	Spanoids - an abstraction of spanning structures, and a barrier for LCCs. CoRR Zeev Dvir, Sivakanth Gopi, Avi Wigderson
2017	A*	`conf`	Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. STOC Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
2017	J	`jnl`	Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. CoRR Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
2017	J	`jnl`	Barriers for Rank Methods in Arithmetic Complexity. CoRR Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
2017	J	`jnl`	Barriers for Rank Methods in Arithmetic Complexity. Electron. Colloquium Comput. Complex. Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
2017	J	`jnl`	Interactions of Computational Complexity Theory and Mathematics. CoRR Avi Wigderson
2017	A*	`conf`	Much Faster Algorithms for Matrix Scaling. FOCS Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
2017	J	`jnl`	Much Faster Algorithms for Matrix Scaling. CoRR Zeyuan Allen Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
2017	J	`jnl`	Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. Electron. Colloquium Comput. Complex. Or Meir, Avi Wigderson
2017	J	`jnl`	Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Theory Comput. Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2017	J	`jnl`	Technical Perspective: Low-depth arithmetic circuits. Commun. ACM Avi Wigderson
2017	J	`jnl`	Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comput. Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2016	A*	`conf`	A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. FOCS Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
2016	J	`jnl`	Algorithmic aspects of Brascamp-Lieb inequalities. CoRR Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
2016	A	`conf`	Degree and Sensitivity: Tails of Two Distributions. CCC Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson
2016	J	`jnl`	Degree and Sensitivity: tails of two distributions. CoRR Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
2016	J	`jnl`	Degree and Sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
2016	J	`jnl`	Local Expanders. Electron. Colloquium Comput. Complex. Emanuele Viola, Avi Wigderson
2016	J	`jnl`	Population recovery and partial identification. Mach. Learn. Avi Wigderson, Amir Yehudayoff
2016	A	`conf`	Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CCC Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016	J	`jnl`	Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CoRR Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016	J	`jnl`	Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Electron. Colloquium Comput. Complex. Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016	A	`conf`	Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions. ITCS Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
2016	J	`jnl`	Symmetric LDPC codes and local testing. Comb. Tali Kaufman, Avi Wigderson
2016	A*	`conf`	Towards Optimal Deterministic Coding for Interactive Communication. SODA Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
2015	J	`jnl`	A deterministic polynomial time algorithm for non-commutative rational identity testing. CoRR Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
2015	A*	`conf`	Compressing and Teaching for Low VC-Dimension. FOCS Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2015	J	`jnl`	Invited Articles Foreword. J. ACM Avi Wigderson, Phokion G. Kolaitis
2015	J	`jnl`	Non-Commutative Arithmetic Circuits with Division. Theory Comput. Pavel Hrubes, Avi Wigderson
2015	A	`conf`	On Randomness Extraction in AC0. CCC Oded Goldreich, Emanuele Viola, Avi Wigderson
2015	J	`jnl`	On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. Oded Goldreich, Emanuele Viola, Avi Wigderson
2015	A*	`conf`	Reed-Muller Codes for Random Erasures and Errors. STOC Emmanuel Abbe, Amir Shpilka, Avi Wigderson
2015	J	`jnl`	Reed-Muller Codes for Random Erasures and Errors. IEEE Trans. Inf. Theory Emmanuel Abbe, Amir Shpilka, Avi Wigderson
2015	J	`jnl`	Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. CoRR Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
2015	J	`jnl`	Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
2015	—	`conf`	Sum-of-Squares Lower Bounds for Sparse PCA. NIPS Tengyu Ma, Avi Wigderson
2015	J	`jnl`	Sum-of-Squares Lower Bounds for Sparse PCA. CoRR Tengyu Ma, Avi Wigderson
2015	A*	`conf`	Sum-of-squares Lower Bounds for Planted Clique. STOC Raghu Meka, Aaron Potechin, Avi Wigderson
2015	J	`jnl`	Sum-of-squares lower bounds for planted clique. CoRR Raghu Meka, Aaron Potechin, Avi Wigderson
2015	J	`jnl`	Teaching and compressing for low VC-dimension. CoRR Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2015	J	`jnl`	Teaching and compressing for low VC-dimension. Electron. Colloquium Comput. Complex. Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2015	J	`jnl`	Towards Optimal Deterministic Coding for Interactive Communication. Electron. Colloquium Comput. Complex. Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
2014	A*	`conf`	Breaking the quadratic barrier for 3-LCC's over the reals. STOC Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2014	A	`conf`	Non-commutative arithmetic circuits with division. ITCS Pavel Hrubes, Avi Wigderson
2014	A*	`conf`	On derandomizing algorithms that err extremely rarely. STOC Oded Goldreich, Avi Wigderson
2014	J	`jnl`	Reed-Muller codes for random erasures and errors. CoRR Emmanuel Abbe, Amir Shpilka, Avi Wigderson
2014	A*	`conf`	Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. STOC Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2013	J	`jnl`	Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique. Electron. Colloquium Comput. Complex. Raghu Meka, Avi Wigderson
2013	J	`jnl`	Breaking the quadratic barrier for 3-LCCs over the Reals. CoRR Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2013	J	`jnl`	Breaking the quadratic barrier for 3-LCCs over the Reals. Electron. Colloquium Comput. Complex. Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2013	A*	`conf`	Interactive proofs of proximity: delegating computation in sublinear time. STOC Guy N. Rothblum, Salil P. Vadhan, Avi Wigderson
2013	J	`jnl`	On Derandomizing Algorithms that Err Extremely Rarely. Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
2013	J	`jnl`	On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
2013	J	`jnl`	Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2012	J	`jnl`	Improved rank bounds for design matrices and a new proof of Kelly's theorem CoRR Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2012	J	`jnl`	Improved rank bounds for design matrices and a new proof of Kelly's theorem. Electron. Colloquium Comput. Complex. Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2012	J	`jnl`	New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2012	A*	`conf`	Population Recovery and Partial Identification. FOCS Avi Wigderson, Amir Yehudayoff
2012	J	`jnl`	Population Recovery and Partial Identification. Electron. Colloquium Comput. Complex. Avi Wigderson, Amir Yehudayoff
2012	A	`conf`	Restriction access. ITCS Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff
2012	J	`jnl`	Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM Guy Kindler, Anup Rao, Ryan O'Donnell, Avi Wigderson
2012	J	`jnl`	Sylvester-Gallai type theorems for approximate collinearity CoRR Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2012	J	`jnl`	Sylvester-Gallai type theorems for approximate collinearity. Electron. Colloquium Comput. Complex. Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2011	J	`jnl`	Kakeya Sets, New Mergers, and Old Extractors. SIAM J. Comput. Zeev Dvir, Avi Wigderson
2011	—	`ch.`	On Yao's XOR-Lemma. Studies in Complexity and Cryptography Oded Goldreich, Noam Nisan, Avi Wigderson
2011	—	`ch.`	On the Circuit Complexity of Perfect Hashing. Studies in Complexity and Cryptography Oded Goldreich, Avi Wigderson
2011	J	`jnl`	Partial Derivatives in Arithmetic Complexity and Beyond. Found. Trends Theor. Comput. Sci. Xi Chen, Neeraj Kayal, Avi Wigderson
2011	A*	`conf`	Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. STOC Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson
2011	J	`jnl`	Restriction Access. Electron. Colloquium Comput. Complex. Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff
2011	—	`ch.`	Simplified Derandomization of BPP Using a Hitting Set Generator. Studies in Complexity and Cryptography Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2010	J	`jnl`	Monotone Expanders: Constructions and Applications. Theory Comput. Zeev Dvir, Avi Wigderson
2010	A*	`conf`	Non-commutative circuits and the sum-of-squares problem. STOC Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2010	J	`jnl`	Non-commutative circuits and the sum-of-squares problem. Electron. Colloquium Comput. Complex. Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2010	A*	`conf`	Public-key cryptography from different assumptions. STOC Benny Applebaum, Boaz Barak, Avi Wigderson
2010	J	`jnl`	Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes CoRR Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff
2010	J	`jnl`	Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. Electron. Colloquium Comput. Complex. Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff
2010	A	`conf`	Relationless Completeness and Separations. CCC Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2010	J	`jnl`	Relationless completeness and separations. Electron. Colloquium Comput. Complex. Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2010	J	`jnl`	Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. Electron. Colloquium Comput. Complex. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
2010	J	`jnl`	Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. J. ACM Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
2010	A	`conf`	Symmetric LDPC Codes and Local Testing. ICS Tali Kaufman, Avi Wigderson
2010	—	`ch.`	Symmetric LDPC Codes and Local Testing. Property Testing Tali Kaufman, Avi Wigderson
2010	J	`jnl`	Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2009	J	`jnl`	Algebrization: A New Barrier in Complexity Theory. ACM Trans. Comput. Theory Scott Aaronson, Avi Wigderson
2009	—	`conf`	Expander codes over reals, Euclidean sections, and compressed sensing. Allerton Venkatesan Guruswami, James R. Lee, Avi Wigderson
2009	J	`jnl`	Extractors And Rank Extractors For Polynomial Sources. Comput. Complex. Zeev Dvir, Ariel Gabizon, Avi Wigderson
2009	A*	`conf`	Linear Systems over Composite Moduli. FOCS Arkadev Chattopadhyay, Avi Wigderson
2009	J	`jnl`	Linear systems over composite moduli. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Avi Wigderson
2009	J	`jnl`	Monotone expanders - constructions and applications. Electron. Colloquium Comput. Complex. Zeev Dvir, Avi Wigderson
2009	J	`jnl`	New Direct-Product Testers and 2-Query PCPs. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2009	A*	`conf`	New direct-product testers and 2-query PCPs. STOC Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2009	J	`jnl`	One-way multiparty communication lower bound for pointer jumping with applications. Comb. Emanuele Viola, Avi Wigderson
2009	—	`conf`	Randomness extractors -- applications and constructions. FSTTCS Avi Wigderson
2009	A*	`conf`	The work of Leslie Valiant. STOC Avi Wigderson
2009	—	`conf`	Towards a Study of Low-Complexity Graphs. ICALP (1) Sanjeev Arora, David Steurer, Avi Wigderson
2008	J	`jnl`	Algebrization: A New Barrier in Complexity Theory. Electron. Colloquium Comput. Complex. Scott Aaronson, Avi Wigderson
2008	A*	`conf`	Algebrization: a new barrier in complexity theory. STOC Scott Aaronson, Avi Wigderson
2008	J	`jnl`	Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Theory Comput. Avi Wigderson, David Xiao
2008	—	`conf`	Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. APPROX-RANDOM Venkatesan Guruswami, James R. Lee, Avi Wigderson
2008	A*	`conf`	Kakeya Sets, New Mergers and Old Extractors. FOCS Zeev Dvir, Avi Wigderson
2008	J	`jnl`	Kakeya sets, new mergers and old extractors. Electron. Colloquium Comput. Complex. Zeev Dvir, Avi Wigderson
2008	J	`jnl`	Neighborly Embedded Manifolds. Discret. Comput. Geom. Gil Kalai, Avi Wigderson
2008	J	`jnl`	Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory Comput. Emanuele Viola, Avi Wigderson
2008	J	`jnl`	Public Key Cryptography from Different Assumptions. IACR Cryptol. ePrint Arch. Boaz Barak, Avi Wigderson
2008	Misc	`conf`	Randomness - A Computational Complexity Perspective. CSR Avi Wigderson
2008	A*	`conf`	Spherical Cubes and Rounding in High Dimensions. FOCS Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson
2008	J	`jnl`	Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2008	A*	`conf`	Uniform direct product theorems: simplified, optimized, and derandomized. STOC Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2007	A*	`conf`	Extractors and Rank Extractors for Polynomial Sources. FOCS Zeev Dvir, Ariel Gabizon, Avi Wigderson
2007	J	`jnl`	Extractors and Rank Extractors for Polynomial Sources. Electron. Colloquium Comput. Complex. Zeev Dvir, Ariel Gabizon, Avi Wigderson
2007	A	`conf`	Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. CCC Emanuele Viola, Avi Wigderson
2007	A*	`conf`	One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. FOCS Emanuele Viola, Avi Wigderson
2007	J	`jnl`	One-way multi-party communication lower bound for pointer jumping with applications. Electron. Colloquium Comput. Complex. Emanuele Viola, Avi Wigderson
2007	J	`jnl`	The Randomized Communication Complexity of Set Disjointness. Theory Comput. Johan Håstad, Avi Wigderson
2006	A*	`conf`	2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. STOC Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson
2006	J	`jnl`	A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. Comput. Complex. Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
2006	A	`conf`	Applications of the Sum-Product Theorem in Finite Fields. CCC Avi Wigderson
2006	J	`jnl`	Derandomizing Homomorphism Testing in General Groups. SIAM J. Comput. Amir Shpilka, Avi Wigderson
2006	J	`jnl`	Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications. Electron. Colloquium Comput. Complex. Avi Wigderson, David Xiao
2006	J	`jnl`	Extracting Randomness Using Few Independent Sources. SIAM J. Comput. Boaz Barak, Russell Impagliazzo, Avi Wigderson
2006	J	`jnl`	Extracting Randomness via Repeated Condensing. SIAM J. Comput. Omer Reingold, Ronen Shaltiel, Avi Wigderson
2006	J	`jnl`	Iterative Construction of Cayley Expander Graphs. Theory Comput. Eyal Rozenman, Aner Shalev, Avi Wigderson
2006	J	`jnl`	Reducing The Seed Length In The Nisan-Wigderson Generator. Comb. Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
2006	—	`conf`	Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM Irit Dinur, Madhu Sudan, Avi Wigderson
2006	J	`jnl`	Robust Local Testability of Tensor Products of LDPC Codes. Electron. Colloquium Comput. Complex. Irit Dinur, Madhu Sudan, Avi Wigderson
2006	B	`conf`	The Power and Weakness of Randomness in Computation. LATIN Avi Wigderson
2005	A	`conf`	A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. CCC Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson
2005	J	`jnl`	A Randomness-Efficient Sampler for Matrix-valued Functions and Applications Electron. Colloquium Comput. Complex. Avi Wigderson, David Xiao
2005	A*	`conf`	A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. FOCS Avi Wigderson, David Xiao
2005	J	`jnl`	Pairwise Independence and Derandomization. Found. Trends Theor. Comput. Sci. Michael Luby, Avi Wigderson
2005	A*	`conf`	Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. STOC Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
2004	A*	`conf`	A new family of Cayley expanders (?). STOC Eyal Rozenman, Aner Shalev, Avi Wigderson
2004	—	`ch.`	Average case complexity. Computational Complexity Theory Avi Wigderson
2004	—	`book`	Computational Complexity Theory. Steven Rudich, Avi Wigderson
2004	A*	`conf`	Depth through breadth, or why should we attend talks in other areas? STOC Avi Wigderson
2004	A*	`conf`	Derandomizing homomorphism testing in general groups. STOC Amir Shpilka, Avi Wigderson
2004	J	`jnl`	Expanders In Group Algebras. Comb. Roy Meshulam, Avi Wigderson
2004	A*	`conf`	Extracting Randomness Using Few Independent Sources. FOCS Boaz Barak, Russell Impagliazzo, Avi Wigderson
2004	J	`jnl`	Near Optimal Separation Of Tree-Like And General Resolution. Comb. Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson
2004	J	`jnl`	Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2003	—	`conf`	Computational Analogues of Entropy. RANDOM-APPROX Boaz Barak, Ronen Shaltiel, Avi Wigderson
2003	A*	`conf`	Extractors: optimal up to constant factors. STOC Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson
2003	A*	`conf`	Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. STOC Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson
2003	J	`jnl`	Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms Johan Håstad, Avi Wigderson
2003	J	`jnl`	The Quantum Communication Complexity of Sampling. SIAM J. Comput. Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
2003	—	`conf`	Zigzag Products, Expander Constructions, Connections, and Applications. FSTTCS Avi Wigderson
2002	—	`conf`	Computing Graph Properties by Randomized Subcube Partitions. RANDOM Ehud Friedgut, Jeff Kahn, Avi Wigderson
2002	—	`conf`	Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good. RANDOM Oded Goldreich, Avi Wigderson
2002	J	`jnl`	Derandomization that is rarely wrong from short advice that is typically good Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
2002	A	`conf`	Expanders from Symmetric Codes. CCC Roy Meshulam, Avi Wigderson
2002	A*	`conf`	Expanders from symmetric codes. STOC Roy Meshulam, Avi Wigderson
2002	J	`jnl`	In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2002	J	`jnl`	On interactive proofs with a laconic prover. Comput. Complex. Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2002	A	`conf`	Randomness Conductors and Constant-Degree Lossless Expanders. CCC Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson
2002	A*	`conf`	Randomness conductors and constant-degree lossless expanders. STOC Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson
2002	J	`jnl`	Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. Comb. Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao
2002	J	`jnl`	Space Complexity in Propositional Calculus. SIAM J. Comput. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2001	J	`jnl`	Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complex. Amir Shpilka, Avi Wigderson
2001	J	`jnl`	Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors Electron. Colloquium Comput. Complex. Omer Reingold, Salil P. Vadhan, Avi Wigderson
2001	A	`conf`	In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. CCC Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2001	J	`jnl`	On Interactive Proofs with a Laconic Prover Electron. Colloquium Comput. Complex. Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2001	A*	`conf`	On Interactive Proofs with a Laconic Prover. ICALP Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2001	J	`jnl`	Randomness vs Time: Derandomization under a Uniform Assumption. J. Comput. Syst. Sci. Russell Impagliazzo, Avi Wigderson
2001	A*	`conf`	Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. FOCS Noga Alon, Alexander Lubotzky, Avi Wigderson
2001	J	`jnl`	Short proofs are narrow - resolution made simple. J. ACM Eli Ben-Sasson, Avi Wigderson
2001	A	`conf`	Simple Analysis of Graph Tests for Linearity and PCP. CCC Johan Håstad, Avi Wigderson
2000	J	`jnl`	A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Comb. Nathan Linial, Alex Samorodnitsky, Avi Wigderson
2000	J	`jnl`	An J. ACM Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou
2000	A*	`conf`	Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. FOCS Omer Reingold, Salil P. Vadhan, Avi Wigderson
2000	J	`jnl`	Extracting Randomness via Repeated Condensing Electron. Colloquium Comput. Complex. Omer Reingold, Ronen Shaltiel, Avi Wigderson
2000	A*	`conf`	Extracting Randomness via Repeated Condensing. FOCS Omer Reingold, Ronen Shaltiel, Avi Wigderson
2000	J	`jnl`	Extractors and pseudo-random generators with optimal seed length Electron. Colloquium Comput. Complex. Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
2000	A*	`conf`	Extractors and pseudo-random generators with optimal seed length. STOC Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
2000	J	`jnl`	Near-Optimal Separation of Treelike and General Resolution Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson
2000	J	`jnl`	On Pseudorandomness with respect to Deterministic Observers. Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
2000	—	`conf`	On Pseudorandomness with respect to Deterministic Observes. ICALP Satellite Workshops Oded Goldreich, Avi Wigderson
2000	J	`jnl`	Pseudorandom Generators in Propositional Proof Complexity Electron. Colloquium Comput. Complex. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2000	A*	`conf`	Pseudorandom Generators in Propositional Proof Complexity. FOCS Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2000	J	`jnl`	Simplified derandomization of BPP using a hitting set generator. Electron. Colloquium Comput. Complex. Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2000	A*	`conf`	Space complexity in propositional calculus. STOC Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
1999	A	`conf`	De-Randomizing BPP: The State of the Art. CCC Avi Wigderson
1999	J	`jnl`	Depth-3 Arithmetic Formulae over Fields of Characteristic Zero Electron. Colloquium Comput. Complex. Amir Shpilka, Avi Wigderson
1999	A	`conf`	Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. CCC Amir Shpilka, Avi Wigderson
1999	A	`conf`	Deterministic Amplification of Space-Bounded Probabilistic Algorithms. CCC Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson
1999	J	`jnl`	Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Comb. Avi Wigderson, David Zuckerman
1999	—	`conf`	Improved Derandomization of BPP Using a Hitting Set Generator. RANDOM-APPROX Oded Goldreich, Avi Wigderson
1999	A*	`conf`	Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
1999	—	`conf`	Probabilistic and Deterministic Approximations of the Permanent (abstract). RANDOM-APPROX Avi Wigderson
1999	A	`conf`	Short Proofs Are Narrow - Resolution Made Simple (Abstract). CCC Eli Ben-Sasson, Avi Wigderson
1999	A*	`conf`	Short Proofs are Narrow - Resolution Made Simple. STOC Eli Ben-Sasson, Avi Wigderson
1999	J	`jnl`	Short Proofs are Narrow - Resolution made Simple Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Avi Wigderson
1999	J	`jnl`	Space Complexity in Propositional Calculus Electron. Colloquium Comput. Complex. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
1999	J	`jnl`	Superpolynomial Lower Bounds for Monotone Span Programs. Comb. László Babai, Anna Gál, Avi Wigderson
1999	J	`jnl`	Techniques for bounding the convergence rate of genetic algorithms. Random Struct. Algorithms Yuri Rabinovich, Avi Wigderson
1998	A*	`conf`	A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. STOC Nathan Linial, Alex Samorodnitsky, Avi Wigderson
1998	J	`jnl`	Deterministic Amplification of Space Bounded Probabilistic Algorithms. Electron. Colloquium Comput. Complex. Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson
1998	A*	`conf`	Do Probabilistic Algorithms Outperform Deterministic Ones? ICALP Avi Wigderson
1998	J	`jnl`	On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
1998	J	`jnl`	On the Power of Finite Automata with Both Nondeterministic and Probabilistic States. SIAM J. Comput. Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson
1998	A*	`conf`	Quantum vs. Classical Communication and Computation. STOC Harry Buhrman, Richard Cleve, Avi Wigderson
1998	A*	`conf`	Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS Russell Impagliazzo, Avi Wigderson
1998	A*	`conf`	The Quantum Communication Complexity of Sampling. FOCS Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
1997	A*	`conf`	Direct Product Results and the GCD Problem, in Old and New Communication Models. STOC Itzhak Parnafes, Ran Raz, Avi Wigderson
1997	J	`jnl`	Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Comput. Complex. Noam Nisan, Avi Wigderson
1997	A*	`conf`	Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. STOC Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao
1997	A*	`conf`	SL <= L STOC Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou
1997	J	`jnl`	Theory of computing: a scientific perspective (extended abstract). SIGACT News Oded Goldreich, Avi Wigderson
1997	J	`jnl`	Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Struct. Algorithms Oded Goldreich, Avi Wigderson
1996	J	`jnl`	A Method for Obtaining Randomized Algorithms with Small Tail Probabilities. Algorithmica Helmut Alt, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, Avi Wigderson
1996	—	`conf`	A New ISTCS Roded Sharan, Avi Wigderson
1996	J	`jnl`	Boolean complexity classes vs. their arithmetic analogs. Random Struct. Algorithms Anna Gál, Avi Wigderson
1996	A*	`conf`	Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. FOCS Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou
1996	A*	`conf`	Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. STOC László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson
1996	J	`jnl`	On the Circuit Complexity of Perfect Hashing Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
1996	J	`jnl`	The Tree Model for Hashing: Lower and Upper Bounds. SIAM J. Comput. Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson
1996	J	`jnl`	The future of computational complexity theory: part I. SIGACT News Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser
1996	J	`jnl`	Theory of Computing: A Scientific Perspective. ACM Comput. Surv. Oded Goldreich, Avi Wigderson
1995	J	`jnl`	Boolean Complexity Classes vs. Their Arithmetic Analogs Electron. Colloquium Comput. Complex. Anna Gál, Avi Wigderson
1995	—	`conf`	Computational Pseudo-Randomness. ISTCS Avi Wigderson
1995	J	`jnl`	Derandomized Graph Products. Comput. Complex. Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
1995	A*	`conf`	Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs. CRYPTO Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson
1995	A*	`conf`	Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version). FOCS Noam Nisan, Avi Wigderson
1995	J	`jnl`	Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. SIAM J. Discret. Math. Ilan Newman, Avi Wigderson
1995	J	`jnl`	On Rank vs. Communication Complexity. Comb. Noam Nisan, Avi Wigderson
1995	J	`jnl`	On Yao's XOR-Lemma Electron. Colloquium Comput. Complex. Oded Goldreich, Noam Nisan, Avi Wigderson
1995	A*	`conf`	On data structures and asymmetric communication complexity. STOC Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
1995	J	`jnl`	On the Second Eigenvalue of Hypergraphs. Comb. Joel Friedman, Avi Wigderson
1995	A*	`conf`	On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern. STOC Noam Nisan, Avi Wigderson
1995	J	`jnl`	Search Problems in the Decision Tree Model. SIAM J. Discret. Math. László Lovász, Moni Naor, Ilan Newman, Avi Wigderson
1995	J	`jnl`	Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Comput. Complex. Mauricio Karchmer, Ran Raz, Avi Wigderson
1994	—	`conf`	A Direct Product Theorem. SCT Russell Impagliazzo, Ran Raz, Avi Wigderson
1994	J	`jnl`	Hardness vs Randomness. J. Comput. Syst. Sci. Noam Nisan, Avi Wigderson
1994	—	`conf`	NL/poly <= +/poly (Preliminary Version). SCT Avi Wigderson
1994	J	`jnl`	Non-Deterministic Communication Complexity with Few Witnesses. J. Comput. Syst. Sci. Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
1994	A*	`conf`	On Rank vs. Communication Complexity FOCS Noam Nisan, Avi Wigderson
1994	J	`jnl`	On Rank vs. Communication Complexity Electron. Colloquium Comput. Complex. Noam Nisan, Avi Wigderson
1994	J	`jnl`	On the Power of Randomization in On-Line Algorithms. Algorithmica Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson
1994	A*	`conf`	On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). STOC Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson
1994	A*	`conf`	Pseudorandomness for network algorithms. STOC Russell Impagliazzo, Noam Nisan, Avi Wigderson
1994	—	`conf`	The Wonders of the Digital Envelope - A Crash Course in Modern Cryptography. IFIP Congress (1) Avi Wigderson
1994	A*	`conf`	The amazing power of pairwise independence (abstract). STOC Avi Wigderson
1994	J	`jnl`	Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing Electron. Colloquium Comput. Complex. Oded Goldreich, Avi Wigderson
1994	A*	`conf`	Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. STOC Oded Goldreich, Avi Wigderson
1993	J	`jnl`	BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Comput. Complex. László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson
1993	A*	`conf`	Characterizing non-deterministic circuit size. STOC Mauricio Karchmer, Avi Wigderson
1993	J	`jnl`	Combinatorial characterization of read-once formulae. Discret. Math. Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson
1993	J	`jnl`	Constructing Small Sets that are Uniform in Arithmetic Progressions. Comb. Probab. Comput. Alexander A. Razborov, Endre Szemerédi, Avi Wigderson
1993	—	`conf`	Deterministic Approximate Counting of Depth-2 Circuits. ISTCS Michael Luby, Boban Velickovic, Avi Wigderson
1993	A*	`conf`	Expanders that beat the eigenvalue bound: explicit construction and applications. STOC Avi Wigderson, David Zuckerman
1993	J	`jnl`	On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity. Theor. Comput. Sci. Rafi Heiman, Ilan Newman, Avi Wigderson
1993	—	`conf`	On Span Programs. SCT Mauricio Karchmer, Avi Wigderson
1993	—	`conf`	One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge. ISTCS Rafail Ostrovsky, Avi Wigderson
1993	J	`jnl`	Rounds in Communication Complexity Revisited. SIAM J. Comput. Noam Nisan, Avi Wigderson
1993	J	`jnl`	Universal Traversal Sequences for Expander Graphs. Inf. Process. Lett. Shlomo Hoory, Avi Wigderson
1993	J	`jnl`	n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom. Inf. Process. Lett. Alexander A. Razborov, Avi Wigderson
1992	J	`jnl`	Geometric medians. Discret. Math. Joseph Gil, William L. Steiger, Avi Wigderson
1992	J	`jnl`	Monotone Circuits for Matching Require Linear Depth. J. ACM Ran Raz, Avi Wigderson
1992	—	`conf`	Non-deterministic Communication Complexity with Few Witness. SCT Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
1992	A*	`ed.`	Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada STOC S. Rao Kosaraju, Mike Fellows, Avi Wigderson, John A. Ellis
1992	A*	`conf`	Quadratic Dynamical Systems (Preliminary Version) FOCS Yuri Rabinovich, Alistair Sinclair, Avi Wigderson
1992	B	`conf`	The Complexity of Graph Connectivity. MFCS Avi Wigderson
1992	A*	`conf`	Undirected Connectivity in O(log ^1.5 n) Space FOCS Noam Nisan, Endre Szemerédi, Avi Wigderson
1991	J	`jnl`	A Lower Bound on the Area of Permutation Layouts. Algorithmica Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson
1991	—	`conf`	An Analysis of a Simple Genetic Algorithm. ICGA Yuri Rabinovich, Avi Wigderson
1991	J	`jnl`	Linear-Size Constant-Depth Polylog-Treshold Circuits. Inf. Process. Lett. Prabhakar Ragde, Avi Wigderson
1991	J	`jnl`	Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM Oded Goldreich, Silvio Micali, Avi Wigderson
1991	J	`jnl`	Randomized VS. Deterministic Decision Tree Complexity for Read-Once Boolean Functions. Comput. Complex. Rafi Heiman, Avi Wigderson
1991	—	`conf`	Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions. SCT Rafi Heiman, Avi Wigderson
1991	A*	`conf`	Rounds in Communication Complexity Revisited STOC Noam Nisan, Avi Wigderson
1991	A*	`conf`	Search Problems in the Decision Tree Model (Preliminary Version) FOCS László Lovász, Moni Naor, Ilan Newman, Avi Wigderson
1991	A*	`conf`	Self-Testing/Correcting for Polynomials and for Approximate Functions STOC Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson
1991	—	`conf`	Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity. SCT Mauricio Karchmer, Ran Raz, Avi Wigderson
1990	—	`conf`	Composition of the Universal Relation. Advances In Computational Complexity Theory Johan Håstad, Avi Wigderson
1990	J	`jnl`	Linear Circuits over GF(2). SIAM J. Comput. Noga Alon, Mauricio Karchmer, Avi Wigderson
1990	J	`jnl`	Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discret. Math. Mauricio Karchmer, Avi Wigderson
1990	A*	`conf`	Monotone Circuits for Matching Require Linear Depth STOC Ran Raz, Avi Wigderson
1990	A*	`conf`	Not All Keys Can Be Hashed in Constant Time (Preliminary Version) STOC Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson
1990	—	`conf`	On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity. SCT Rafi Heiman, Ilan Newman, Avi Wigderson
1990	A*	`conf`	On the Power of Randomization in Online Algorithms (Extended Abstract) STOC Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson
1990	—	`conf`	Perfect Hashing, Graph Entropy, and Circuit Complexity. SCT Ilan Newman, Prabhakar Ragde, Avi Wigderson
1990	J	`jnl`	Toward Understanding Exclusive Read. SIAM J. Comput. Faith E. Fich, Avi Wigderson
1989	J	`jnl`	Deterministic Simulation of Probabilistic Constant Depth Circuits. Adv. Comput. Res. Miklós Ajtai, Avi Wigderson
1989	A*	`conf`	Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract) FOCS Aviad Cohen, Avi Wigderson
1989	A*	`conf`	Efficient Identification Schemes Using Two Prover Interactive Proofs. CRYPTO Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson
1989	—	`conf`	Hardness vs. Randomness - A Survey (abstract). SCT Noam Nisan, Avi Wigderson
1989	J	`jnl`	On Computations with Integer Division. RAIRO Theor. Informatics Appl. Bettina Just, Friedhelm Meyer auf der Heide, Avi Wigderson
1989	A*	`conf`	Probabilistic Communication Complexity of Boolean Relations (Extended Abstract) FOCS Ran Raz, Avi Wigderson
1989	B	`conf`	Towards Understanding Exclusive Read. SPAA Faith E. Fich, Avi Wigderson
1988	J	`jnl`	A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. Theor. Comput. Sci. Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1988	A*	`conf`	Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract) STOC Michael Ben-Or, Shafi Goldwasser, Avi Wigderson
1988	A*	`conf`	Hardness vs. Randomness (Extended Abstract) FOCS Noam Nisan, Avi Wigderson
1988	A*	`conf`	Monotone Circuits for Connectivity Require Super-logarithmic Depth STOC Mauricio Karchmer, Avi Wigderson
1988	A*	`conf`	Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions STOC Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson
1988	A	`conf`	On Computations with Integer Division. STACS Bettina Just, Friedhelm Meyer auf der Heide, Avi Wigderson
1988	J	`jnl`	Relations Between Concurrent-Write Models of Parallel Computation. SIAM J. Comput. Faith E. Fich, Prabhakar Ragde, Avi Wigderson
1988	J	`jnl`	Rubber bands, convex embeddings and graph connectivity. Comb. Nathan Linial, László Lovász, Avi Wigderson
1988	J	`jnl`	Simulations Among Concurrent-Write PRAMs. Algorithmica Faith E. Fich, Prabhakar Ragde, Avi Wigderson
1988	J	`jnl`	The Complexity of Parallel Search. J. Comput. Syst. Sci. Richard M. Karp, Eli Upfal, Avi Wigderson
1988	J	`jnl`	The Discrete Logarithm Hides O(log n) Bits. SIAM J. Comput. Douglas L. Long, Avi Wigderson
1988	J	`jnl`	The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)). SIAM J. Discret. Math. Prabhakar Ragde, William L. Steiger, Endre Szemerédi, Avi Wigderson
1987	J	`jnl`	A Time-Space Tradeoff for Element Distinctness. SIAM J. Comput. Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1987	A*	`conf`	How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority STOC Oded Goldreich, Silvio Micali, Avi Wigderson
1987	J	`jnl`	How to share memory in a distributed system. J. ACM Eli Upfal, Avi Wigderson
1987	J	`jnl`	The Complexity of Parallel Sorting. SIAM J. Comput. Friedhelm Meyer auf der Heide, Avi Wigderson
1986	A*	`conf`	A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications FOCS Nathan Linial, László Lovász, Avi Wigderson
1986	A	`conf`	A Time-Space Tradeoff for Element Distinctness. STACS Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1986	A*	`conf`	A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. ICALP Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1986	J	`jnl`	Constructing a perfect matching is in random NC. Comb. Richard M. Karp, Eli Upfal, Avi Wigderson
1986	A*	`conf`	How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. CRYPTO Oded Goldreich, Silvio Micali, Avi Wigderson
1986	B	`conf`	On Play by Means of Computing Machines. TARK Nimrod Megiddo, Avi Wigderson
1986	A*	`conf`	On a Search Problem Related to Branch-and-Bound Procedures FOCS Richard M. Karp, Michael E. Saks, Avi Wigderson
1986	A*	`conf`	Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees FOCS Michael E. Saks, Avi Wigderson
1986	B	`conf`	Proofs that Release Minimum Knowledge. MFCS Oded Goldreich, Silvio Micali, Avi Wigderson
1986	A*	`conf`	Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract) FOCS Oded Goldreich, Silvio Micali, Avi Wigderson
1985	J	`jnl`	A Fast Parallel Algorithm for the Maximal Independent Set Problem J. ACM Richard M. Karp, Avi Wigderson
1985	A*	`conf`	Are Search and Decision Problems Computationally Equivalent? STOC Richard M. Karp, Eli Upfal, Avi Wigderson
1985	A*	`conf`	Constructing a Perfect Matching is in Random NC STOC Richard M. Karp, Eli Upfal, Avi Wigderson
1985	A*	`conf`	Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) FOCS Miklós Ajtai, Avi Wigderson
1985	A*	`conf`	Multi-Layer Grid Embeddings FOCS Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson
1985	A*	`conf`	One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation STOC Faith E. Fich, Friedhelm Meyer auf der Heide, Prabhakar Ragde, Avi Wigderson
1985	J	`jnl`	Rectilinear Graphs and their Embeddings. SIAM J. Comput. Gopalakrishnan Vijayan, Avi Wigderson
1985	A*	`conf`	The Complexity of Parallel Computation on Matroids FOCS Richard M. Karp, Eli Upfal, Avi Wigderson
1985	A*	`conf`	The Complexity of Parallel Sorting FOCS Friedhelm Meyer auf der Heide, Avi Wigderson
1985	J	`jnl`	Trade-Offs Between Depth and Width in Parallel Computation. SIAM J. Comput. Uzi Vishkin, Avi Wigderson
1984	A*	`conf`	A Fast Parallel Algorithm for the Maximal Independent Set Problem STOC Richard M. Karp, Avi Wigderson
1984	A*	`conf`	How to Share Memory in a Distributed System (A Preliminary Version) FOCS Eli Upfal, Avi Wigderson
1984	A*	`conf`	Relations Between Concurrent-Write Models of Parallel Computation. PODC Faith E. Fich, Prabhakar Ragde, Avi Wigderson
1983	J	`jnl`	Dynamic Parallel Memories Inf. Control. Uzi Vishkin, Avi Wigderson
1983	A*	`conf`	How Discreet is the Discrete Log? STOC Douglas L. Long, Avi Wigderson
1983	J	`jnl`	Improving the Performance Guarantee for Approximate Graph Coloring J. ACM Avi Wigderson
1983	J	`jnl`	Succinct Representations of Graphs Inf. Control. Hana Galperin, Avi Wigderson
1983	A*	`conf`	Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version) STOC Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson
1983	A*	`conf`	Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version) FOCS Uzi Vishkin, Avi Wigderson
1982	A*	`conf`	A New Approximate Graph Coloring Algorithm STOC Avi Wigderson
1982	A*	`conf`	On the Security of Multi-Party Protocols in Distributed Systems. CRYPTO Danny Dolev, Avi Wigderson