Avi Wigderson

ORCID

Publication Activity (10 Years)

Years Active: 1982-2024
Publications (10 Years): 93

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

FOCS

STOC

Publications

Peter Bürgisser, Mahmut Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. CCC (2024)
Robert Andrews, Avi Wigderson
Constant-Depth Arithmetic Circuits for Linear Algebra Problems. Electron. Colloquium Comput. Complex. (2024)
Peter Bürgisser, Mahmut Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture. CoRR (2024)
Robert Andrews, Avi Wigderson
Constant-Depth Arithmetic Circuits for Linear Algebra Problems. CoRR (2024)
Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
On linear-algebraic notions of expansion. Electron. Colloquium Comput. Complex. (2023)
Ronen Eldan, Avi Wigderson, Pei Wu
An Optimal "It Ain't Over Till It's Over" Theorem. STOC (2023)
Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. FOCS (2022)
Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
Connections between graphs and matrix spaces. CoRR (2022)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. TheoretiCS 1 (2022)
Avi Wigderson
Non-commutative Optimization - Where Algebra, Analysis and Computational Complexity Meet. ISSAC (2022)
Ronen Eldan, Avi Wigderson, Pei Wu
An Optimal "It Ain't Over Till It's Over" Theorem. CoRR (2022)
Oded Goldreich, Avi Wigderson
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. FOCS (2022)
Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
On linear-algebraic notions of expansion. CoRR (2022)
Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. CoRR (2022)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Computational Complexity Conference (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. CoRR (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. 28 (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. Computational Complexity Conference (2021)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Theory Comput. 17 (2021)
Peter Bürgisser, M. Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
Polynomial Time Algorithms in Invariant Theory for Torus Actions. Computational Complexity Conference (2021)
Peter Bürgisser, M. Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
Polynomial time algorithms in invariant theory for torus actions. CoRR (2021)
Oded Goldreich, Avi Wigderson
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. FOCS (2021)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. CoRR (2021)
Avi Wigderson, Yuval Wigderson
The uncertainty principle: variations on a theme. CoRR (2020)
Visu Makam, Avi Wigderson
Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties. FOCS (2020)
Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. Computational Complexity Conference (2020)
Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. SIAM J. Comput. 49 (3) (2020)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich, Avi Wigderson
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich, Avi Wigderson
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network. Electron. Colloquium Comput. Complex. 27 (2020)
Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
Operator Scaling: Theory and Applications. Found. Comput. Math. 20 (2) (2020)
Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. Electron. Colloquium Comput. Complex. 26 (2019)
Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. CoRR (2019)
Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer. FOCS (2019)
Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes. FOCS (2019)
Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson
More barriers for rank methods, via a "numeric to symbolic" transfer. CoRR (2019)
Or Meir, Avi Wigderson
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. Comput. Complex. 28 (2) (2019)
Visu Makam, Avi Wigderson
Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). Electron. Colloquium Comput. Complex. 26 (2019)
Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. ITCS (2019)
Orit E. Raz, Avi Wigderson
Subspace arrangements, graph rigidity and derandomization through submodular optimization. CoRR (2019)
Visu Makam, Avi Wigderson
Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). CoRR (2019)
Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. CoRR (2019)
Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. ITCS (2018)
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. STOC (2018)
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing. CoRR (2018)
Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
Efficient algorithms for tensor scaling, quantum marginals and moment polytopes. CoRR (2018)
Zeev Dvir, Sivakanth Gopi, Avi Wigderson
Spanoids - an abstraction of spanning structures, and a barrier for LCCs. CoRR (2018)
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
Explicit Capacity Approaching Coding for Interactive Communication. IEEE Trans. Inf. Theory 64 (10) (2018)
Emanuele Viola, Avi Wigderson
Local Expanders. Comput. Complex. 27 (2) (2018)
Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes. FOCS (2018)
Avi Wigderson
On the nature of the Theory of Computation (ToC). Electron. Colloquium Comput. Complex. 25 (2018)
Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
Barriers for Rank Methods in Arithmetic Complexity. ITCS (2018)
Zeyuan Allen Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
Much Faster Algorithms for Matrix Scaling. CoRR (2017)
Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson
Much Faster Algorithms for Matrix Scaling. FOCS (2017)
Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. CoRR (2017)
Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
Barriers for Rank Methods in Arithmetic Complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. STOC (2017)
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comput. 46 (1) (2017)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Theory Comput. 13 (1) (2017)
Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
Barriers for Rank Methods in Arithmetic Complexity. CoRR (2017)
Avi Wigderson
Technical Perspective: Low-depth arithmetic circuits. Commun. ACM 60 (6) (2017)
Avi Wigderson
Interactions of Computational Complexity Theory and Mathematics. CoRR (2017)
Or Meir, Avi Wigderson
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. Electron. Colloquium Comput. Complex. 24 (2017)
Avi Wigderson, Amir Yehudayoff
Population recovery and partial identification. Mach. Learn. 102 (1) (2016)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Computational Complexity Conference (2016)
Emanuele Viola, Avi Wigderson
Local Expanders. Electron. Colloquium Comput. Complex. 23 (2016)
Tali Kaufman, Avi Wigderson
Symmetric LDPC codes and local testing. Comb. 36 (1) (2016)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CoRR (2016)
Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
Algorithmic aspects of Brascamp-Lieb inequalities. CoRR (2016)
Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
Degree and Sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex. 23 (2016)
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
Towards Optimal Deterministic Coding for Interactive Communication. SODA (2016)
Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
Degree and Sensitivity: tails of two distributions. CoRR (2016)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson
Degree and Sensitivity: Tails of Two Distributions. Computational Complexity Conference (2016)
Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions. ITCS (2016)
Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. FOCS (2016)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Teaching and compressing for low VC-dimension. CoRR (2015)
Tengyu Ma, Avi Wigderson
Sum-of-Squares Lower Bounds for Sparse PCA. NIPS (2015)
Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. CoRR (2015)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Teaching and compressing for low VC-dimension. Electron. Colloquium Comput. Complex. 22 (2015)
Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. Electron. Colloquium Comput. Complex. 22 (2015)
Oded Goldreich, Emanuele Viola, Avi Wigderson
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. 22 (2015)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Compressing and Teaching for Low VC-Dimension. FOCS (2015)
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
Reed-Muller Codes for Random Erasures and Errors. IEEE Trans. Inf. Theory 61 (10) (2015)
Pavel Hrubes, Avi Wigderson
Non-Commutative Arithmetic Circuits with Division. Theory Comput. 11 (2015)
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
Reed-Muller Codes for Random Erasures and Errors. STOC (2015)
Raghu Meka, Aaron Potechin, Avi Wigderson
Sum-of-squares Lower Bounds for Planted Clique. STOC (2015)
Tengyu Ma, Avi Wigderson
Sum-of-Squares Lower Bounds for Sparse PCA. CoRR (2015)
Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson
A deterministic polynomial time algorithm for non-commutative rational identity testing. CoRR (2015)
Avi Wigderson, Phokion G. Kolaitis
Invited Articles Foreword. J. ACM 62 (5) (2015)
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
Towards Optimal Deterministic Coding for Interactive Communication. Electron. Colloquium Comput. Complex. 22 (2015)
Oded Goldreich, Emanuele Viola, Avi Wigderson
On Randomness Extraction in AC0. Computational Complexity Conference (2015)
Raghu Meka, Aaron Potechin, Avi Wigderson
Sum-of-squares lower bounds for planted clique. CoRR (2015)
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
Reed-Muller codes for random erasures and errors. CoRR (2014)
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. STOC (2014)
Oded Goldreich, Avi Wigderson
On derandomizing algorithms that err extremely rarely. STOC (2014)
Pavel Hrubes, Avi Wigderson
Non-commutative arithmetic circuits with division. ITCS (2014)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Breaking the quadratic barrier for 3-LCC's over the reals. STOC (2014)
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. Electron. Colloquium Comput. Complex. 20 (2013)
Guy N. Rothblum, Salil P. Vadhan, Avi Wigderson
Interactive proofs of proximity: delegating computation in sublinear time. STOC (2013)

Avi Wigderson.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Avi Wigderson