Avishay Tal

According to our database, Avishay Tal authored at least 62 papers between 2011 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019).

Yuval Filmus, Debmalya Panigrahi, Daniel Stefankovic, Avishay Tal

SIAM J. Comput., 2025

Quantum-Computable One-Way Functions without One-Way Functions.

William Kretschmer, Luowen Qian, Avishay Tal

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

The Power of Adaptivity in Quantum Query Algorithms.

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Quantum Cryptography in Algorithmica.

William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees.

Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs.

Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Fourier Growth of Communication Protocols for XOR Functions.

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Tight Time-Space Lower Bounds for Constant-Pass Learning.

Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting.

Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Guest Editors' Foreword to the CCC 2020 Special Issue.

Zeev Dvir, Avishay Tal

Theory Comput., 2022

2021

Fooling Constant-Depth Threshold Circuits.

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Electron. Colloquium Comput. Complex., 2021

Monotone Branching Programs: Pseudorandomness and Circuit Complexity.

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2021

Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem.

Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Quantum Versus Randomized Communication Complexity, with Efficient Players.

Uma Girish, Ran Raz, Avishay Tal

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract).

Yuval Filmus, Or Meir, Avishay Tal

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Fooling Constant-Depth Threshold Circuits (Extended Abstract).

Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Junta Distance Approximation with Sub-Exponential Queries.

Vishnu Iyer, Avishay Tal, Michael Whitmeyer

Proceedings of the 36th Computational Complexity Conference, 2021

Fourier Growth of Parity Decision Trees.

Uma Girish, Avishay Tal, Kewen Wu

Proceedings of the 36th Computational Complexity Conference, 2021

Pseudorandom Generators for Read-Once Monotone Branching Programs.

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan

Proceedings of the Approximation, 2021

2020

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.

Oded Goldreich, Avishay Tal

Proceedings of the Computational Complexity and Property Testing, 2020

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC⁰.

Yuval Filmus, Or Meir, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

Rigid Matrices From Rectangular PCPs.

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

Quantum Implications of Huang's Sensitivity Theorem.

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

Towards Optimal Separations between Quantum and Randomized Query Complexities.

Avishay Tal

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs.

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

AC0[p] Lower Bounds against MCSP via the Coin Problem.

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Electron. Colloquium Comput. Complex., 2019

On the Computational Power of Radio Channels.

Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Oracle separation of BQP and PH.

Ran Raz, Avishay Tal

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Pseudorandom generators for width-3 branching programs.

Raghu Meka, Omer Reingold, Avishay Tal

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Cubic Formula Size Lower Bounds Based on Compositions with Majority.

Anna Gál, Avishay Tal, Adrian Trejo Nuñez

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates.

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

AC⁰[p] Lower Bounds Against MCSP via the Coin Problem.

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Time-Space Lower Bounds for Two-Pass Learning.

Sumegha Garg, Ran Raz, Avishay Tal

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Extractor-based time-space lower bounds for learning.

Sumegha Garg, Ran Raz, Avishay Tal

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Improved pseudorandomness for unordered branching programs through local monotonicity.

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Robust Sensitivity of Boolean Functions.

Shachar Lovett, Avishay Tal, Jiapeng Zhang

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Pseudorandom Generators for Low Sensitivity Functions.

Pooya Hatami, Avishay Tal

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound.

Ilan Komargodski, Ran Raz, Avishay Tal

SIAM J. Comput., 2017

The Choice and Agreement Problems of a Random Function.

Or Meir, Avishay Tal

Electron. Colloquium Comput. Complex., 2017

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.

Oded Goldreich, Avishay Tal

Electron. Colloquium Comput. Complex., 2017

Formula lower bounds via the quantum method.

Avishay Tal

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Time-space hardness of learning sparse parities.

Gillat Kol, Ran Raz, Avishay Tal

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Low-Sensitivity Functions from Unambiguous Certificates.

Shalev Ben-David, Pooya Hatami, Avishay Tal

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Tight Bounds on the Fourier Spectrum of AC0.

Avishay Tal

Proceedings of the 32nd Computational Complexity Conference, 2017

Lower Bounds for 2-Query LCCs over Large Alphabet.

Arnab Bhattacharyya, Sivakanth Gopi, Avishay Tal

Proceedings of the Approximation, 2017

2016

The Bipartite Formula Complexity of Inner-Product is Quadratic.

Avishay Tal

Electron. Colloquium Comput. Complex., 2016

Computing Requires Larger Formulas than Approximating.

Avishay Tal

Electron. Colloquium Comput. Complex., 2016

Degree and Sensitivity: tails of two distributions.

Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson

Electron. Colloquium Comput. Complex., 2016

Matrix rigidity of random toeplitz matrices.

Oded Goldreich, Avishay Tal

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On the Sensitivity Conjecture.

Avishay Tal

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

#SAT Algorithms from Shrinkage.

Avishay Tal

Electron. Colloquium Comput. Complex., 2015

Two Structural Results for Low Degree Polynomials and Applications.

Gil Cohen, Avishay Tal

Proceedings of the Approximation, 2015

2014

Tight bounds on The Fourier Spectrum of AC⁰.

Avishay Tal

Electron. Colloquium Comput. Complex., 2014

Shrinkage of De Morgan Formulae from Quantum Query Complexity.

Avishay Tal

Electron. Colloquium Comput. Complex., 2014

On the structure of boolean functions with small spectral norm.

Amir Shpilka, Avishay Tal, Ben lee Volk

Proceedings of the Innovations in Theoretical Computer Science, 2014

Shrinkage of De Morgan Formulae by Spectral Techniques.

Avishay Tal

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

On Fractional Block Sensitivity.

Raghav Kulkarni, Avishay Tal

Electron. Colloquium Comput. Complex., 2013

Properties and applications of boolean function composition.

Avishay Tal

Proceedings of the Innovations in Theoretical Computer Science, 2013

Improved Average-Case Lower Bounds for DeMorgan Formula Size.

Ilan Komargodski, Ran Raz, Avishay Tal

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

On the degree of univariate polynomials over the integers.

Gil Cohen, Amir Shpilka, Avishay Tal

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

On the Minimal Fourier Degree of Symmetric Boolean Functions.

Amir Shpilka, Avishay Tal

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011