Avishay Tal

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

In 2015, I received my Ph.D. from the Weizmann Institute of Science, under the guidance of Ran Raz. Prior to that, I was an MSc 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:
  • Computational Complexity, 
  • Analysis of Boolean Functions, 
  • Circuit and Formula Lower Bounds, 
  • Query Complexity, 
  • Pseudorandomness, 
  • Learning, 
  • Quantum Computing,
  • Combinatorics, 
  • and the connections between Algorithms and Lower Bounds. 

My Curriculum Vitae (updated: February 2019).


Contact Information

Address: University of California, Berkeley. Department of Electrical Engineering and Computer Sciences, 635 SODA Hall, Berkeley, CA 94720.

E-mail: atal "at" berkeley.edu


Program Committees

FOCS'19, SODA'20, CCC'20


Publications

Time-Space Lower Bounds for Two-Pass Learning
PDF
joint with Sumegha Garg and Ran Raz.
CCC, 2019.

AC0[p] Lower Bounds against MCSP via the Coin Problem
PDF
joint with Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova.
ICALP, 2019.

Oracle Separation of BQP and PH
PDF
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
PDF
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
PDF
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.
PDF
ITCS, 2019.

Cubic Formula Size Lower Bounds Based on Compositions with Majority
joint with Anna Gal and Adrian Trejo Nuñez.
PDF
ITCS, 2019.

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity
PDF
joint with Eshan Chattopadhyay, Pooya Hatami and Omer Reingold.
STOC, 2018.

Extractor-Based Time-Space Lower Bounds for Learning
PDF
joint with Sumegha Garg and Ran Raz.
STOC, 2018.

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
PDF
joint with Oded Goldreich.

The Choice and Agreement Problems of a Random Function
PDF
joint with Or Meir.
Information Processing Letters, Volume 133, 2018.

Pseudorandom Generators for Low Sensitivity Functions
PDF
joint with Pooya Hatami.
ITCS, 2018.

Robust Sensitivity
PDF
joint with Shachar Lovett and Jiapeng Zhang.
SODA, 2018.

Lower Bounds for 2-Query LCCs over Large Alphabet
PDF
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
PDF
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
PDF
joint with Shalev Ben-David and Pooya Hatami.
ITCS, 2017.

Degree and Sensitivity: Tails of Two Distributions
PDF
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
PDF

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
PDF
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]