Avishay Tal

Hi, I'm Avishay, an Assistant Professor at the Department of Electrical Engineering and Computer Sciences at UC Berkeley. I am honored to be part of Berkeley's Theory Group.

I received my Ph.D. in 2015 from the Weizmann Institute of Science, under the guidance of Ran Raz. Prior to that, I was an M.Sc. student at the Technion under the guidance of Amir Shpilka. I feel very fortunate to have had both Amir and Ran as my mentors.

I held postdoctoral appointments at the Institute for Advanced Study (hosted by Avi Wigderson), Simons Institute (as part of the Lower Bounds in Computational Complexity program), and Stanford University (hosted by Omer Reingold).

Main Research Interests

Motivating questions that guide my research:

Contact Information


635 Soda Hall

Department of Electrical Engineering and Computer Sciences

University of California, Berkeley

Berkeley, CA, 94720

E-mail: atal "at" berkeley.edu


Workshop on Derandomizing Space-Bounded Computation (Part of STOC 2020)

Advances in Boolean Function Analysis Lecture Series @ The Simons Institute (Summer 2020)

Program on Analysis and TCS : New Frontiers @ The Simons Institute (Summer 2023)


CS 294-92 - Analysis of Boolean Functions - Spring 2020

CS 170 - Efficient Algorithms and Intractable Problems - Fall 2020

CS 278 - Computational Complexity Theory - Spring 2021

CS 294-202 - Pseudorandomness - Fall 2021

CS 172 - Computability and Complexity - Spring 2022

CS 172 - Computability and Complexity - Fall 2022

CS 294-92 - Analysis of Boolean Functions - Spring 2023

CS 70 - Discrete Mathematics and Probability Theory - Fall 2023

CS 278 - Computational Complexity Theory - Spring 2024

Program Committees

FOCS 2019SODA 2020CCC 2020RANDOM 2020ITCS 2021STOC 2021, ITCS 2023, STOC 2024

Group Information

Current Ph.D. Students

Current Postdocs

Former Students

Former Postdocs


Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting


joint with Lijie Chen, William Hoza, Xin Lyu, and Hongxun Wu

FOCS, 2023.

Fourier Growth of Communication Protocols for XOR Functions


joint with Uma Girish, Makrand Sinha, and Kewen Wu

FOCS, 2023.

Quantum Cryptography in Algorithmica


joint with William Kretschmer, Luowen Qian, and Makrand Sinha.

Presented at the 26th Annual Conference on Quantum Information Processing (QIP 2023).

STOC, 2023.

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


joint with Pooya Hatami, William Hoza, and Roei Tell.

STOC, 2023.

On Certified Randomness from Quantum Advantage Experiments


joint with Roozbeh Bassirian, Adam Bouland, Bill Fefferman, and Sam Gunn.

Fourier Growth of Parity Decision Trees


joint with Uma Girish and Kewen Wu.

CCC, 2021.

Pseudorandom Generators for Read-Once Monotone Branching Programs


joint with Dean Doron, Raghu Meka, Omer Reingold, and Salil Vadhan.

RANDOM, 2021.

Fooling Constant-Depth Threshold Circuits


joint with Pooya Hatami, William Hoza, and Roei Tell.

FOCS, 2021.

Junta Distance Approximation with Sub-Exponential Queries


joint with Vishnu Iyer and Michael Whitmeyer.

CCC, 2021.

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0


joint with Yuval Filmus and Or Meir.

ITCS, 2021.

Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem


joint with Scott Aaronson, Shalev Ben-David, Robin Kothari, and Shravas Rao.

(Subsumes an earlier version named "Quantum Implications of Huang's Sensitivity Theorem")

Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021) as a short plenary talk.

STOC, 2021.

Rigid Matrices From Rectangular PCPs


joint with Amey Bhangale, Prahladh Harsha, and Orr Paradise.

FOCS, 2020.

Towards Optimal Separations between Quantum and Randomized Query Complexities

PDF FOCS Long Talk

FOCS, 2020.

Quantum versus Randomized Communication Complexity, with Efficient Players


joint with Uma Girish and Ran Raz.

Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020).

ITCS, 2021.

On the Computational Power of Radio Channels


joint with Mark Braverman, Gillat Kol, and Rotem Oshman.

DISC, 2019.

Time-Space Lower Bounds for Two-Pass Learning


joint with Sumegha Garg and Ran Raz.

CCC, 2019.

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


joint with Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova.

ICALP, 2019.

Oracle Separation of BQP and PH


joint with Ran Raz.

STOC, 2019. (Best Paper Award)

Presented at the 22nd Annual Conference on Quantum Information Processing (QIP 2019) as a plenary talk.

[Computational Complexity Blog] [Shtetl-Optimized] [Windows on Theory]

[New Scientist] [Quanta] [The Hindu] [CACM] [Nature]

Video (CMO Oaxaca) Video (IAS)

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


joint with Adam Bene Watts, Robin Kothari, and Luke Schaeffer.

STOC, 2019.

Presented at the 22nd Annual Conference on Quantum Information Processing (QIP 2019).

Pseudorandom Generators for Width-3 Branching Programs


joint with Raghu Meka and Omer Reingold.

STOC, 2019.

[Oded's choices]

Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates


joint with Eshan Chattopadhyay, Pooya Hatami, and Shachar Lovett.

ITCS, 2019.

Cubic Formula Size Lower Bounds Based on Compositions with Majority


joint with Anna Gal and Adrian Trejo Nuñez.

ITCS, 2019.

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity


joint with Eshan Chattopadhyay, Pooya Hatami and Omer Reingold.

STOC, 2018.

Extractor-Based Time-Space Lower Bounds for Learning


joint with Sumegha Garg and Ran Raz.

STOC, 2018.

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions


joint with Oded Goldreich.

The Choice and Agreement Problems of a Random Function


joint with Or Meir.

Information Processing Letters, Volume 133, 2018.

Pseudorandom Generators for Low Sensitivity Functions


joint with Pooya Hatami.

ITCS, 2018.

Robust Sensitivity


joint with Shachar Lovett and Jiapeng Zhang.

SODA, 2018.

Lower Bounds for 2-Query LCCs over Large Alphabet


joint with Arnab Bhattacharyya and Sivakanth Gopi.

RANDOM, 2017.

Tight Bounds on The Fourier Spectrum of AC0

PDF Slides

CCC, 2017.

[Oded's choices]

The Bipartite Formula Complexity of Inner-Product is Quadratic


STOC, 2017 (merged with "Computing Requires Larger Formulas than Approximating").

Computing Requires Larger Formulas than Approximating

PDF Slides TCS+ Talk

STOC, 2017 (merged with "The Bipartite Formula Complexity of Inner-Product is Quadratic").

[Oded's choices]

Time-Space Hardness of Learning Sparse Parities

PDF Slides

joint with Gillat Kol and Ran Raz.

STOC, 2017.

Low-Sensitivity Functions from Unambiguous Certificates


joint with Shalev Ben-David and Pooya Hatami.

ITCS, 2017.

Degree and Sensitivity: Tails of Two Distributions


joint with Parikshit Gopalan, Rocco Servedio, and Avi Wigderson.

(a preliminary version of this paper by Gopalan, Servedio, and Wigderson appeared in CCC, 2016).

On the Sensitivity Conjecture

PDF Slides

ICALP, 2016.

#SAT Algorithms from Shrinkage


Matrix Rigidity of Random Toeplitz Matrices

PDF Journal-version Slides (STOC) Slides (longer version)

joint with Oded Goldreich.

Computational Complexity, 2016 (preliminary version in STOC, 2016).

Shrinkage of De Morgan Formulae by Spectral Techniques

PDF Slides

FOCS, 2014.

On Fractional Block Sensitivity

PDF Journal-version

joint with Raghav Kulkarni.

CJTCS, 2016.

Two Structural Results for Low Degree Polynomials and Applications

PDF Video (IAS) Slides (RANDOM)

joint with Gil Cohen.

RANDOM, 2015.

An implementation of the algorithm suggested in Theorem 4.1.

On the Structure of Boolean Functions with Small Spectral Norm


joint with Amir Shpilka and Ben lee Volk.

Computational Complexity, 2015 (preliminary version in ITCS, 2014).

Improved Average-Case Lower Bounds for De Morgan Formula Size

PDF Journal-version Slides

joint with Ilan Komargodski and Ran Raz.

SICOMP, 2017 (preliminary version in FOCS, 2013).

Properties and Applications of Boolean Function Composition

PDF Slides

ITCS, 2013. (Best Student Paper)

[Oded's choices]

On the Degree of Univariate Polynomials Over the Integers

PDF Journal-version

joint with Gil Cohen and Amir Shpilka.

Combinatorica, 2016 (preliminary version in ITCS, 2012).

On The Minimal Fourier Degree of Symmetric Boolean Functions

PDF Journal-version Slides Amir@MSR

joint with Amir Shpilka.

Combinatorica, 2014 (preliminary version in CCC, 2011).

[Richard Lipton's Blog Post] [2]