On the Minimal Fourier Degree of Symmetric Boolean Functions. - Amir Shpilka; Avishay Tal (Electron. Colloquium Comput. Complex., 2010)

On the Degree of Univariate Polynomials Over the Integers. - Gil Cohen; Amir Shpilka; Avishay Tal (Electron. Colloquium Comput. Complex., 2011)

Properties and Applications of Boolean Function Composition. - Avishay Tal (Electron. Colloquium Comput. Complex., 2012)

Two Structural Results for Low Degree Polynomials and Applications. - Gil Cohen; Avishay Tal (Electron. Colloquium Comput. Complex., 2013)

Improved Average-Case Lower Bounds for DeMorgan Formula Size. - Ilan Komargodski; Ran Raz; Avishay Tal (Electron. Colloquium Comput. Complex., 2013)

Shrinkage of De Morgan Formulae by Spectral Techniques. - Avishay Tal (FOCS, 2014)

Shrinkage of De Morgan Formulae from Quantum Query Complexity. - Avishay Tal (Electron. Colloquium Comput. Complex., 2014)

Tight bounds on The Fourier Spectrum of AC0. - Avishay Tal (Electron. Colloquium Comput. Complex., 2014)

#SAT Algorithms from Shrinkage. - Avishay Tal (Electron. Colloquium Comput. Complex., 2015)

On Fractional Block Sensitivity. - Raghav Kulkarni; Avishay Tal (Chic. J. Theor. Comput. Sci., 2016)

Degree and Sensitivity: tails of two distributions. - Parikshit Gopalan; Rocco A. Servedio; Avishay Tal; Avi Wigderson (Electron. Colloquium Comput. Complex., 2016)

Time-Space Hardness of Learning Sparse Parities. - Gillat Kol; Ran Raz; Avishay Tal (Electron. Colloquium Comput. Complex., 2016)

On The Sensitivity Conjecture. - Avishay Tal (Electron. Colloquium Comput. Complex., 2016)

Computing Requires Larger Formulas than Approximating. - Avishay Tal (Electron. Colloquium Comput. Complex., 2016)

The Bipartite Formula Complexity of Inner-Product is Quadratic. - Avishay Tal (Electron. Colloquium Comput. Complex., 2016)

Lower Bounds for 2-Query LCCs over Large Alphabet. - Arnab Bhattacharyya 001; Sivakanth Gopi; Avishay Tal (APPROX-RANDOM, 2017)

Tight Bounds on the Fourier Spectrum of AC0. - Avishay Tal (CCC, 2017)

Low-Sensitivity Functions from Unambiguous Certificates. - Shalev Ben-David; Pooya Hatami; Avishay Tal (ITCS, 2017)

Formula lower bounds via the quantum method. - Avishay Tal (STOC, 2017)

On the Structure of Boolean Functions with Small Spectral Norm. - Amir Shpilka; Avishay Tal; Ben lee Volk (Comput. Complex., 2017)

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. - Eshan Chattopadhyay; Pooya Hatami; Omer Reingold; Avishay Tal (Electron. Colloquium Comput. Complex., 2017)

Extractor-Based Time-Space Lower Bounds for Learning. - Sumegha Garg; Ran Raz; Avishay Tal (Electron. Colloquium Comput. Complex., 2017)

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. - Oded Goldreich 001; Avishay Tal (Electron. Colloquium Comput. Complex., 2017)

Pseudorandom Generators for Low-Sensitivity Functions. - Pooya Hatami; Avishay Tal (Electron. Colloquium Comput. Complex., 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 Robust Sensitivity of Boolean Functions. - Shachar Lovett; Avishay Tal; Jiapeng Zhang (SODA, 2018)

Matrix rigidity of random Toeplitz matrices. - Oded Goldreich 001; Avishay Tal (Comput. Complex., 2018)

Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. - Eshan Chattopadhyay; Pooya Hatami; Shachar Lovett; Avishay Tal (Electron. Colloquium Comput. Complex., 2018)

Cubic Formula Size Lower Bounds Based on Compositions with Majority. - Anna Gál; Avishay Tal; Adrian Trejo Nuñez (Electron. Colloquium Comput. Complex., 2018)

Pseudorandom Generators for Width-3 Branching Programs. - Raghu Meka; Omer Reingold; Avishay Tal (Electron. Colloquium Comput. Complex., 2018)

Oracle Separation of BQP and PH. - Ran Raz; Avishay Tal (Electron. Colloquium Comput. Complex., 2018)

The choice and agreement problems of a random function. - Or Meir; Avishay Tal (Inf. Process. Lett., 2018)

AC0[p] Lower Bounds Against MCSP via the Coin Problem. - Alexander Golovnev; Rahul Ilango; Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova; Avishay Tal (ICALP, 2019)

On the Computational Power of Radio Channels. - Mark Braverman; Gillat Kol; Rotem Oshman; Avishay Tal (DISC, 2019)

Time-Space Lower Bounds for Two-Pass Learning. - Sumegha Garg; Ran Raz; Avishay Tal (Electron. Colloquium Comput. Complex., 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)

Towards Optimal Separations between Quantum and Randomized Query Complexities. - Avishay Tal (Electron. Colloquium Comput. Complex., 2019)

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. - Adam Bene Watts; Robin Kothari; Luke Schaeffer; Avishay Tal (Electron. Colloquium Comput. Complex., 2019)

Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. - Amey Bhangale; Prahladh Harsha; Orr Paradise; Avishay Tal (FOCS, 2020)

Quantum Implications of Huang's Sensitivity Theorem. - Scott Aaronson; Shalev Ben-David; Robin Kothari; Avishay Tal (Electron. Colloquium Comput. Complex., 2020)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. - Yuval Filmus; Or Meir; Avishay Tal (Electron. Colloquium Comput. Complex., 2020)

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. - Oded Goldreich 001; Avishay Tal (Computational Complexity and Property Testing, 2020)

Pseudorandom Generators for Read-Once Monotone Branching Programs. - Dean Doron; Raghu Meka; Omer Reingold; Avishay Tal; Salil P. Vadhan (APPROX-RANDOM, 2021)

Fooling Constant-Depth Threshold Circuits (Extended Abstract). - Pooya Hatami; William M. Hoza; Avishay Tal; Roei Tell (FOCS, 2021)

Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). - Yuval Filmus; Or Meir; Avishay Tal (ITCS, 2021)

Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. - Scott Aaronson; Shalev Ben-David; Robin Kothari; Shravas Rao; Avishay Tal (STOC, 2021)

Monotone Branching Programs: Pseudorandomness and Circuit Complexity. - Dean Doron; Raghu Meka; Omer Reingold; Avishay Tal; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2021)

Fourier Growth of Parity Decision Trees. - Uma Girish; Avishay Tal; Kewen Wu 001 (Electron. Colloquium Comput. Complex., 2021)

Fooling Constant-Depth Threshold Circuits. - Pooya Hatami; William Hoza; Avishay Tal; Roei Tell (Electron. Colloquium Comput. Complex., 2021)

Junta Distance Approximation with Sub-Exponential Queries. - Vishnu Iyer; Avishay Tal; Michael Whitmeyer (Electron. Colloquium Comput. Complex., 2021)

Quantum versus Randomized Communication Complexity, with Efficient Players. - Uma Girish; Ran Raz; Avishay Tal (Comput. Complex., 2022)

Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees. - Pooya Hatami; William Hoza; Avishay Tal; Roei Tell (Electron. Colloquium Comput. Complex., 2022)

Guest Editors' Foreword to the CCC 2020 Special Issue. - Zeev Dvir; Avishay Tal (Adv. Math. Commun., 2022)

Tight Time-Space Lower Bounds for Constant-Pass Learning. - Xin Lyu 002; Avishay Tal; Hongxun Wu; Junzhao Yang (FOCS, 2023)

Fourier Growth of Communication Protocols for XOR Functions. - Uma Girish; Makrand Sinha; Avishay Tal; Kewen Wu 001 (FOCS, 2023)

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. - Lijie Chen 001; Xin Lyu 002; Avishay Tal; Hongxun Wu (ICALP, 2023)

Quantum Cryptography in Algorithmica. - William Kretschmer; Luowen Qian; Makrand Sinha; Avishay Tal (STOC, 2023)

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. - Lijie Chen 001; William Hoza; Xin Lyu 002; Avishay Tal; Hongxun Wu (Electron. Colloquium Comput. Complex., 2023)

The Power of Adaptivity in Quantum Query Algorithms. - Uma Girish; Makrand Sinha; Avishay Tal; Kewen Wu 001 (STOC, 2024)

Rigid Matrices from Rectangular PCPs. - Amey Bhangale; Prahladh Harsha; Orr Paradise; Avishay Tal (SIAM J. Comput., 2024)

Quantum-Computable One-Way Functions without One-Way Functions. - William Kretschmer; Luowen Qian; Avishay Tal (STOC, 2025)