| 2026 | STOC | Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits. | Lijie Chen, Avishay Tal, Yichuan Wang |
| 2026 | STOC | Improved Lower Bounds for QAC0. | Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John Wright |
| 2025 | STOC | Quantum-Computable One-Way Functions without One-Way Functions. | William Kretschmer, Luowen Qian, Avishay Tal |
| 2024 | STOC | The Power of Adaptivity in Quantum Query Algorithms. | Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu |
| 2023 | FOCS | Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. | Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu |
| 2023 | FOCS | Tight Time-Space Lower Bounds for Constant-Pass Learning. | Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang |
| 2023 | FOCS | Fourier Growth of Communication Protocols for XOR Functions. | Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu |
| 2023 | ICALP | New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. | Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu |
| 2023 | STOC | Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. | Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell |
| 2023 | STOC | Quantum Cryptography in Algorithmica. | William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal |
| 2021 | FOCS | Fooling Constant-Depth Threshold Circuits (Extended Abstract). | Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell |
| 2021 | STOC | Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. | Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal |
| 2020 | FOCS | Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. | Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal |
| 2020 | FOCS | Towards Optimal Separations between Quantum and Randomized Query Complexities. | Avishay Tal |
| 2019 | ICALP | AC | Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal |
| 2019 | STOC | Pseudorandom generators for width-3 branching programs. | Raghu Meka, Omer Reingold, Avishay Tal |
| 2019 | STOC | Oracle separation of BQP and PH. | Ran Raz, Avishay Tal |
| 2019 | STOC | Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. | Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal |
| 2018 | SODA | The Robust Sensitivity of Boolean Functions. | Shachar Lovett, Avishay Tal, Jiapeng Zhang |
| 2018 | STOC | Improved pseudorandomness for unordered branching programs through local monotonicity. | Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal |
| 2018 | STOC | Extractor-based time-space lower bounds for learning. | Sumegha Garg, Ran Raz, Avishay Tal |
| 2017 | STOC | Time-space hardness of learning sparse parities. | Gillat Kol, Ran Raz, Avishay Tal |
| 2017 | STOC | Formula lower bounds via the quantum method. | Avishay Tal |
| 2016 | ICALP | On the Sensitivity Conjecture. | Avishay Tal |
| 2016 | STOC | Matrix rigidity of random toeplitz matrices. | Oded Goldreich, Avishay Tal |
| 2014 | FOCS | Shrinkage of De Morgan Formulae by Spectral Techniques. | Avishay Tal |
| 2013 | FOCS | Improved Average-Case Lower Bounds for DeMorgan Formula Size. | Ilan Komargodski, Ran Raz, Avishay Tal |