Avishay Tal

ORCID

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 90

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

STOC

FOCS

Publications

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
Rigid Matrices from Rectangular PCPs. SIAM J. Comput. 53 (2) (2024)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
The Power of Adaptivity in Quantum Query Algorithms. STOC (2024)
Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. FOCS (2023)
Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. Electron. Colloquium Comput. Complex. (2023)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. STOC (2023)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
The Power of Adaptivity in Quantum Query Algorithms. CoRR (2023)
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
Quantum Cryptography in Algorithmica. STOC (2023)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
Fourier Growth of Communication Protocols for XOR Functions. CoRR (2023)
Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang
Tight Time-Space Lower Bounds for Constant-Pass Learning. FOCS (2023)
Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. ICALP (2023)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
Fourier Growth of Communication Protocols for XOR Functions. FOCS (2023)
Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang
Tight Time-Space Lower Bounds for Constant-Pass Learning. CoRR (2023)
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
Quantum Cryptography in Algorithmica. CoRR (2022)
Uma Girish, Ran Raz, Avishay Tal
Quantum versus Randomized Communication Complexity, with Efficient Players. Comput. Complex. 31 (2) (2022)
Ran Raz, Avishay Tal
Oracle Separation of BQP and PH. J. ACM 69 (4) (2022)
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees. Electron. Colloquium Comput. Complex. (2022)
Zeev Dvir, Avishay Tal
Guest Editors' Foreword to the CCC 2020 Special Issue. Theory Comput. 18 (2022)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS (2022)
Vishnu Iyer, Avishay Tal, Michael Whitmeyer
Junta Distance Approximation with Sub-Exponential Queries. Electron. Colloquium Comput. Complex. 28 (2021)
Uma Girish, Avishay Tal, Kewen Wu
Fourier Growth of Parity Decision Trees. Computational Complexity Conference (2021)
Yuval Filmus, Or Meir, Avishay Tal
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). ITCS (2021)
Uma Girish, Ran Raz, Avishay Tal
Quantum Versus Randomized Communication Complexity, with Efficient Players. ITCS (2021)
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits. Electron. Colloquium Comput. Complex. 28 (2021)
Uma Girish, Avishay Tal, Kewen Wu
Fourier Growth of Parity Decision Trees. Electron. Colloquium Comput. Complex. 28 (2021)
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan
Monotone Branching Programs: Pseudorandomness and Circuit Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan
Pseudorandom Generators for Read-Once Monotone Branching Programs. APPROX-RANDOM (2021)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. STOC (2021)
Vishnu Iyer, Avishay Tal, Michael Whitmeyer
Junta Distance Approximation with Sub-Exponential Queries. Computational Complexity Conference (2021)
Uma Girish, Avishay Tal, Kewen Wu
Fourier Growth of Parity Decision Trees. CoRR (2021)
Vishnu Iyer, Avishay Tal, Michael Whitmeyer
Junta Distance Approximation with Sub-Exponential Queries. CoRR (2021)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS (2021)
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. FOCS (2020)
Avishay Tal
Towards Optimal Separations between Quantum and Randomized Query Complexities. FOCS (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem. CoRR (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
Quantum Implications of Huang's Sensitivity Theorem. Electron. Colloquium Comput. Complex. 27 (2020)
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
Rigid Matrices From Rectangular PCPs. CoRR (2020)
Yuval Filmus, Or Meir, Avishay Tal
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathbf{AC}^0$. Electron. Colloquium Comput. Complex. 27 (2020)
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
Rigid Matrices From Rectangular PCPs. Electron. Colloquium Comput. Complex. 27 (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
Quantum Implications of Huang's Sensitivity Theorem. CoRR (2020)
Yuval Filmus, Or Meir, Avishay Tal
. CoRR (2020)
Ran Raz, Avishay Tal
Oracle separation of BQP and PH. STOC (2019)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC (2019)
Raghu Meka, Omer Reingold, Avishay Tal
Pseudorandom generators for width-3 branching programs. STOC (2019)
Avishay Tal
Towards Optimal Separations between Quantum and Randomized Query Complexities. Electron. Colloquium Comput. Complex. 26 (2019)
Anna Gál, Avishay Tal, Adrian Trejo Nuñez
Cubic Formula Size Lower Bounds Based on Compositions with Majority. ITCS (2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
[p] Lower Bounds Against MCSP via the Coin Problem. ICALP (2019)
Avishay Tal
Towards Optimal Separations between Quantum and Randomized Query Complexities. CoRR (2019)
Uma Girish, Ran Raz, Avishay Tal
Quantum versus Randomized Communication Complexity, with Efficient Players. CoRR (2019)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. CoRR (2019)
Uma Girish, Ran Raz, Avishay Tal
Quantum versus Randomized Communication Complexity, with Efficient Players. Electron. Colloquium Comput. Complex. 26 (2019)
Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal
On the Computational Power of Radio Channels. DISC (2019)
Sumegha Garg, Ran Raz, Avishay Tal
Time-Space Lower Bounds for Two-Pass Learning. Computational Complexity Conference (2019)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. 26 (2019)
Sumegha Garg, Ran Raz, Avishay Tal
Time-Space Lower Bounds for Two-Pass Learning. Electron. Colloquium Comput. Complex. 26 (2019)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. ITCS (2019)
Raghu Meka, Omer Reingold, Avishay Tal
Pseudorandom Generators for Width-3 Branching Programs. Electron. Colloquium Comput. Complex. 25 (2018)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. Electron. Colloquium Comput. Complex. 25 (2018)
Raghu Meka, Omer Reingold, Avishay Tal
Pseudorandom Generators for Width-3 Branching Programs. CoRR (2018)
Sumegha Garg, Ran Raz, Avishay Tal
Extractor-based time-space lower bounds for learning. STOC (2018)
Oded Goldreich, Avishay Tal
Matrix rigidity of random Toeplitz matrices. Comput. Complex. 27 (2) (2018)
Shachar Lovett, Avishay Tal, Jiapeng Zhang
The Robust Sensitivity of Boolean Functions. SODA (2018)
Ran Raz, Avishay Tal
Oracle Separation of BQP and PH. Electron. Colloquium Comput. Complex. 25 (2018)
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
Improved pseudorandomness for unordered branching programs through local monotonicity. STOC (2018)
Pooya Hatami, Avishay Tal
Pseudorandom Generators for Low Sensitivity Functions. ITCS (2018)
Anna Gál, Avishay Tal, Adrian Trejo Nuñez
Cubic Formula Size Lower Bounds Based on Compositions with Majority. Electron. Colloquium Comput. Complex. 25 (2018)
Or Meir, Avishay Tal
The choice and agreement problems of a random function. Inf. Process. Lett. 133 (2018)
Gil Cohen, Amir Shpilka, Avishay Tal
On the degree of univariate polynomials over the integers. Comb. 37 (3) (2017)
Arnab Bhattacharyya, Sivakanth Gopi, Avishay Tal
Lower Bounds for 2-Query LCCs over Large Alphabet. APPROX-RANDOM (2017)
Avishay Tal
Tight Bounds on the Fourier Spectrum of AC0. Computational Complexity Conference (2017)
Sumegha Garg, Ran Raz, Avishay Tal
Extractor-Based Time-Space Lower Bounds for Learning. Electron. Colloquium Comput. Complex. 24 (2017)
Pooya Hatami, Avishay Tal
Pseudorandom Generators for Low-Sensitivity Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Amir Shpilka, Avishay Tal, Ben lee Volk
On the Structure of Boolean Functions with Small Spectral Norm. Comput. Complex. 26 (1) (2017)
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. Electron. Colloquium Comput. Complex. 24 (2017)
Shalev Ben-David, Pooya Hatami, Avishay Tal
Low-Sensitivity Functions from Unambiguous Certificates. ITCS (2017)
Oded Goldreich, Avishay Tal
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Avishay Tal
Formula lower bounds via the quantum method. STOC (2017)
Ilan Komargodski, Ran Raz, Avishay Tal
Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound. SIAM J. Comput. 46 (1) (2017)
Sumegha Garg, Ran Raz, Avishay Tal
Extractor-Based Time-Space Lower Bounds for Learning. CoRR (2017)
Gillat Kol, Ran Raz, Avishay Tal
Time-space hardness of learning sparse parities. STOC (2017)
Or Meir, Avishay Tal
The Choice and Agreement Problems of a Random Function. Electron. Colloquium Comput. Complex. 24 (2017)
Avishay Tal
Computing Requires Larger Formulas than Approximating. Electron. Colloquium Comput. Complex. 23 (2016)
Gillat Kol, Ran Raz, Avishay Tal
Time-Space Hardness of Learning Sparse Parities. Electron. Colloquium Comput. Complex. 23 (2016)
Avishay Tal
The Bipartite Formula Complexity of Inner-Product is Quadratic. Electron. Colloquium Comput. Complex. 23 (2016)
Raghav Kulkarni, Avishay Tal
On Fractional Block Sensitivity. Chic. J. Theor. Comput. Sci. 2016 (2016)
Avishay Tal
On the Sensitivity Conjecture. ICALP (2016)
Oded Goldreich, Avishay Tal
Matrix rigidity of random toeplitz matrices. STOC (2016)
Avishay Tal
On The Sensitivity Conjecture. Electron. Colloquium Comput. Complex. 23 (2016)
Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
Degree and Sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex. 23 (2016)
Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
Degree and Sensitivity: tails of two distributions. CoRR (2016)
Avishay Tal
#SAT Algorithms from Shrinkage. Electron. Colloquium Comput. Complex. 22 (2015)
Gil Cohen, Avishay Tal
Two Structural Results for Low Degree Polynomials and Applications. APPROX-RANDOM (2015)
Oded Goldreich, Avishay Tal
Matrix Rigidity of Random Toeplitz Matrices. Electron. Colloquium Comput. Complex. 22 (2015)
Amir Shpilka, Avishay Tal, Ben lee Volk
On the structure of boolean functions with small spectral norm. ITCS (2014)
Avishay Tal
Shrinkage of De Morgan Formulae from Quantum Query Complexity. Electron. Colloquium Comput. Complex. 21 (2014)
Avishay Tal
. Electron. Colloquium Comput. Complex. 21 (2014)
Avishay Tal
Shrinkage of De Morgan Formulae by Spectral Techniques. FOCS (2014)
Gil Cohen, Avishay Tal
Two Structural Results for Low Degree Polynomials and Applications. CoRR (2014)
Amir Shpilka, Avishay Tal
On the minimal fourier degree of symmetric Boolean functions. Comb. 34 (3) (2014)
Raghav Kulkarni, Avishay Tal
On Fractional Block Sensitivity. Electron. Colloquium Comput. Complex. 20 (2013)

Avishay Tal.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Avishay Tal