Avishay Tal

115 papers A* 25A 15Journal 71Unranked 3
YearRankTypeTitle / Venue / Authors
2026 J jnl
On Certified Randomness from Fourier Sampling or Random Circuit Sampling.
Quantum
Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, Avishay Tal
2025 J jnl
Improved Lower Bounds for QAC0.
CoRR
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John Wright
2025 A* conf
Quantum-Computable One-Way Functions without One-Way Functions.
STOC
William Kretschmer, Luowen Qian, Avishay Tal
2025 J jnl
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019).
SIAM J. Comput.
Yuval Filmus, Debmalya Panigrahi, Daniel Stefankovic, Avishay Tal
2024 J jnl
Quantum-Computable One-Way Functions without One-Way Functions.
CoRR
William Kretschmer, Luowen Qian, Avishay Tal
2024 J jnl
Rigid Matrices from Rectangular PCPs.
SIAM J. Comput.
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
2024 A* conf
The Power of Adaptivity in Quantum Query Algorithms.
STOC
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
2023 A* conf
Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees.
STOC
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
2023 A* conf
Fourier Growth of Communication Protocols for XOR Functions.
FOCS
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
2023 J jnl
Fourier Growth of Communication Protocols for XOR Functions.
CoRR
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
2023 A* conf
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs.
ICALP
Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu
2023 A* conf
Quantum Cryptography in Algorithmica.
STOC
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
2023 J jnl
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC
Theory Comput.
Yuval Filmus, Or Meir, Avishay Tal
2023 J jnl
The Power of Adaptivity in Quantum Query Algorithms.
CoRR
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
2023 A* conf
Tight Time-Space Lower Bounds for Constant-Pass Learning.
FOCS
Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang
2023 J jnl
Tight Time-Space Lower Bounds for Constant-Pass Learning.
CoRR
Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang
2023 A* conf
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting.
FOCS
Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
2023 J jnl
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting.
Electron. Colloquium Comput. Complex.
Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
2022 J jnl
Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees.
Electron. Colloquium Comput. Complex.
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
2022 J jnl
Guest Editors' Foreword to the CCC 2020 Special Issue.
Theory Comput.
Zeev Dvir, Avishay Tal
2022 J jnl
Oracle Separation of BQP and PH.
J. ACM
Ran Raz, Avishay Tal
2022 J jnl
Quantum Cryptography in Algorithmica.
CoRR
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
2022 J jnl
Quantum versus Randomized Communication Complexity, with Efficient Players.
Comput. Complex.
Uma Girish, Ran Raz, Avishay Tal
2021 A* conf
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem.
STOC
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
2021 A* conf
Fooling Constant-Depth Threshold Circuits (Extended Abstract).
FOCS
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
2021 J jnl
Fooling Constant-Depth Threshold Circuits.
Electron. Colloquium Comput. Complex.
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
2021 A conf
Fourier Growth of Parity Decision Trees.
CCC
Uma Girish, Avishay Tal, Kewen Wu
2021 J jnl
Fourier Growth of Parity Decision Trees.
CoRR
Uma Girish, Avishay Tal, Kewen Wu
2021 J jnl
Fourier Growth of Parity Decision Trees.
Electron. Colloquium Comput. Complex.
Uma Girish, Avishay Tal, Kewen Wu
2021 A conf
Junta Distance Approximation with Sub-Exponential Queries.
CCC
Vishnu Iyer, Avishay Tal, Michael Whitmeyer
2021 J jnl
Junta Distance Approximation with Sub-Exponential Queries.
CoRR
Vishnu Iyer, Avishay Tal, Michael Whitmeyer
2021 J jnl
Junta Distance Approximation with Sub-Exponential Queries.
Electron. Colloquium Comput. Complex.
Vishnu Iyer, Avishay Tal, Michael Whitmeyer
2021 J jnl
Monotone Branching Programs: Pseudorandomness and Circuit Complexity.
Electron. Colloquium Comput. Complex.
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan
2021 — conf
Pseudorandom Generators for Read-Once Monotone Branching Programs.
APPROX-RANDOM
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan
2021 A conf
Quantum Versus Randomized Communication Complexity, with Efficient Players.
ITCS
Uma Girish, Ran Raz, Avishay Tal
2021 A conf
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract).
ITCS
Yuval Filmus, Or Meir, Avishay Tal
2020 J jnl
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem.
CoRR
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
2020 — ch.
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
Computational Complexity and Property Testing
Oded Goldreich, Avishay Tal
2020 J jnl
Quantum Implications of Huang's Sensitivity Theorem.
CoRR
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
2020 J jnl
Quantum Implications of Huang's Sensitivity Theorem.
Electron. Colloquium Comput. Complex.
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
2020 A* conf
Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs.
FOCS
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
2020 J jnl
Rigid Matrices From Rectangular PCPs.
CoRR
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
2020 J jnl
Rigid Matrices From Rectangular PCPs.
Electron. Colloquium Comput. Complex.
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
2020 J jnl
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC
CoRR
Yuval Filmus, Or Meir, Avishay Tal
2020 J jnl
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC
Electron. Colloquium Comput. Complex.
Yuval Filmus, Or Meir, Avishay Tal
2020 A* conf
Towards Optimal Separations between Quantum and Randomized Query Complexities.
FOCS
Avishay Tal
2019 A* conf
AC
ICALP
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019 J jnl
AC0[p] Lower Bounds against MCSP via the Coin Problem.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019 A conf
Cubic Formula Size Lower Bounds Based on Compositions with Majority.
ITCS
Anna Gál, Avishay Tal, Adrian Trejo Nuñez
2019 A* conf
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.
STOC
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019 J jnl
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.
CoRR
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019 J jnl
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.
Electron. Colloquium Comput. Complex.
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019 A conf
On the Computational Power of Radio Channels.
DISC
Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal
2019 A* conf
Oracle separation of BQP and PH.
STOC
Ran Raz, Avishay Tal
2019 A conf
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates.
ITCS
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
2019 A* conf
Pseudorandom generators for width-3 branching programs.
STOC
Raghu Meka, Omer Reingold, Avishay Tal
2019 J jnl
Quantum versus Randomized Communication Complexity, with Efficient Players.
CoRR
Uma Girish, Ran Raz, Avishay Tal
2019 J jnl
Quantum versus Randomized Communication Complexity, with Efficient Players.
Electron. Colloquium Comput. Complex.
Uma Girish, Ran Raz, Avishay Tal
2019 A conf
Time-Space Lower Bounds for Two-Pass Learning.
CCC
Sumegha Garg, Ran Raz, Avishay Tal
2019 J jnl
Time-Space Lower Bounds for Two-Pass Learning.
Electron. Colloquium Comput. Complex.
Sumegha Garg, Ran Raz, Avishay Tal
2019 J jnl
Towards Optimal Separations between Quantum and Randomized Query Complexities.
CoRR
Avishay Tal
2019 J jnl
Towards Optimal Separations between Quantum and Randomized Query Complexities.
Electron. Colloquium Comput. Complex.
Avishay Tal
2018 J jnl
Cubic Formula Size Lower Bounds Based on Compositions with Majority.
Electron. Colloquium Comput. Complex.
Anna Gál, Avishay Tal, Adrian Trejo Nuñez
2018 A* conf
Extractor-based time-space lower bounds for learning.
STOC
Sumegha Garg, Ran Raz, Avishay Tal
2018 A* conf
Improved pseudorandomness for unordered branching programs through local monotonicity.
STOC
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
2018 J jnl
Matrix rigidity of random Toeplitz matrices.
Comput. Complex.
Oded Goldreich, Avishay Tal
2018 J jnl
Oracle Separation of BQP and PH.
Electron. Colloquium Comput. Complex.
Ran Raz, Avishay Tal
2018 A conf
Pseudorandom Generators for Low Sensitivity Functions.
ITCS
Pooya Hatami, Avishay Tal
2018 J jnl
Pseudorandom Generators for Width-3 Branching Programs.
CoRR
Raghu Meka, Omer Reingold, Avishay Tal
2018 J jnl
Pseudorandom Generators for Width-3 Branching Programs.
Electron. Colloquium Comput. Complex.
Raghu Meka, Omer Reingold, Avishay Tal
2018 J jnl
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.
Electron. Colloquium Comput. Complex.
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
2018 A* conf
The Robust Sensitivity of Boolean Functions.
SODA
Shachar Lovett, Avishay Tal, Jiapeng Zhang
2018 J jnl
The choice and agreement problems of a random function.
Inf. Process. Lett.
Or Meir, Avishay Tal
2017 J jnl
Extractor-Based Time-Space Lower Bounds for Learning.
CoRR
Sumegha Garg, Ran Raz, Avishay Tal
2017 J jnl
Extractor-Based Time-Space Lower Bounds for Learning.
Electron. Colloquium Comput. Complex.
Sumegha Garg, Ran Raz, Avishay Tal
2017 A* conf
Formula lower bounds via the quantum method.
STOC
Avishay Tal
2017 J jnl
Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound.
SIAM J. Comput.
Ilan Komargodski, Ran Raz, Avishay Tal
2017 J jnl
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity.
Electron. Colloquium Comput. Complex.
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
2017 A conf
Low-Sensitivity Functions from Unambiguous Certificates.
ITCS
Shalev Ben-David, Pooya Hatami, Avishay Tal
2017 — conf
Lower Bounds for 2-Query LCCs over Large Alphabet.
APPROX-RANDOM
Arnab Bhattacharyya, Sivakanth Gopi, Avishay Tal
2017 J jnl
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avishay Tal
2017 J jnl
On the Structure of Boolean Functions with Small Spectral Norm.
Comput. Complex.
Amir Shpilka, Avishay Tal, Ben Lee Volk
2017 J jnl
On the degree of univariate polynomials over the integers.
Comb.
Gil Cohen, Amir Shpilka, Avishay Tal
2017 J jnl
Pseudorandom Generators for Low-Sensitivity Functions.
Electron. Colloquium Comput. Complex.
Pooya Hatami, Avishay Tal
2017 J jnl
The Choice and Agreement Problems of a Random Function.
Electron. Colloquium Comput. Complex.
Or Meir, Avishay Tal
2017 A conf
Tight Bounds on the Fourier Spectrum of AC0.
CCC
Avishay Tal
2017 A* conf
Time-space hardness of learning sparse parities.
STOC
Gillat Kol, Ran Raz, Avishay Tal
2016 J jnl
Computing Requires Larger Formulas than Approximating.
Electron. Colloquium Comput. Complex.
Avishay Tal
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 A* conf
Matrix rigidity of random toeplitz matrices.
STOC
Oded Goldreich, Avishay Tal
2016 J jnl
On Fractional Block Sensitivity.
Chic. J. Theor. Comput. Sci.
Raghav Kulkarni, Avishay Tal
2016 J jnl
On The Sensitivity Conjecture.
Electron. Colloquium Comput. Complex.
Avishay Tal
2016 A* conf
On the Sensitivity Conjecture.
ICALP
Avishay Tal
2016 J jnl
The Bipartite Formula Complexity of Inner-Product is Quadratic.
Electron. Colloquium Comput. Complex.
Avishay Tal
2016 J jnl
Time-Space Hardness of Learning Sparse Parities.
Electron. Colloquium Comput. Complex.
Gillat Kol, Ran Raz, Avishay Tal
2015 J jnl
#SAT Algorithms from Shrinkage.
Electron. Colloquium Comput. Complex.
Avishay Tal
2015 J jnl
Matrix Rigidity of Random Toeplitz Matrices.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avishay Tal
2015 — conf
Two Structural Results for Low Degree Polynomials and Applications.
APPROX-RANDOM
Gil Cohen, Avishay Tal
2014 J jnl
On the minimal fourier degree of symmetric Boolean functions.
Comb.
Amir Shpilka, Avishay Tal
2014 A conf
On the structure of boolean functions with small spectral norm.
ITCS
Amir Shpilka, Avishay Tal, Ben Lee Volk
2014 A* conf
Shrinkage of De Morgan Formulae by Spectral Techniques.
FOCS
Avishay Tal
2014 J jnl
Shrinkage of De Morgan Formulae from Quantum Query Complexity.
Electron. Colloquium Comput. Complex.
Avishay Tal
2014 J jnl
Tight bounds on The Fourier Spectrum of AC
Electron. Colloquium Comput. Complex.
Avishay Tal
2014 J jnl
Two Structural Results for Low Degree Polynomials and Applications.
CoRR
Gil Cohen, Avishay Tal
2013 A* conf
Improved Average-Case Lower Bounds for DeMorgan Formula Size.
FOCS
Ilan Komargodski, Ran Raz, Avishay Tal
2013 J jnl
Improved Average-Case Lower Bounds for DeMorgan Formula Size.
Electron. Colloquium Comput. Complex.
Ilan Komargodski, Ran Raz, Avishay Tal
2013 J jnl
On Fractional Block Sensitivity.
Electron. Colloquium Comput. Complex.
Raghav Kulkarni, Avishay Tal
2013 A conf
Properties and applications of boolean function composition.
ITCS
Avishay Tal
2013 J jnl
Two Structural Results for Low Degree Polynomials and Applications.
Electron. Colloquium Comput. Complex.
Gil Cohen, Avishay Tal
2012 A conf
On the degree of univariate polynomials over the integers.
ITCS
Gil Cohen, Amir Shpilka, Avishay Tal
2012 J jnl
Properties and Applications of Boolean Function Composition.
Electron. Colloquium Comput. Complex.
Avishay Tal
2011 J jnl
On the Degree of Univariate Polynomials Over the Integers.
Electron. Colloquium Comput. Complex.
Gil Cohen, Amir Shpilka, Avishay Tal
2011 A conf
On the Minimal Fourier Degree of Symmetric Boolean Functions.
CCC
Amir Shpilka, Avishay Tal
2010 J jnl
On the Minimal Fourier Degree of Symmetric Boolean Functions.
Electron. Colloquium Comput. Complex.
Amir Shpilka, Avishay Tal