Avishay Tal

Hi, I'm Avishay, a postdoctoral scholar hosted by Omer Reingold at Stanford's theory group

Between September 2015 and July 2017 I was a postdoctoral researcher in the CSDM group at the Institute for Advanced Study and a scientist in the Simons Collaboration on Algorithms and Geometry.

In September 2015, I received my PhD from the Weizmann Institute of Science, under the guidance of Ran Raz. Before that, I was an MSc student at the Technion under the guidance of Amir Shpilka. I feel fortunate to have had both Amir and Ran as my mentors.

Main Research Interests:
  • Computational Complexity, 
  • Analysis of Boolean Functions, 
  • Circuit and Formula Lower Bounds, 
  • Decision Tree Complexity, 
  • Pseudorandomness, 
  • Learning, 
  • Combinatorics, 
  • and the connections between Algorithms and Lower Bounds. 

My Curriculum Vitae.

Contact Information

Address: Stanford University, William Gates Building, 353 Serra Mall, Wing 4B MC: 9045, Stanford, CA 94305
E-mail: avishay "dot" tal "at" gmail.com


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

The Choice and Agreement Problems of a Random Function
joint with Or Meir.

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

Lower Bounds for 2-Query LCCs over Large Alphabet
joint with Arnab Bhattacharyya and Sivakanth Gopi.
RANDOM, 2017.

Pseudorandom Generators for Low Sensitivity Functions
joint with Pooya Hatami.
To appear in ITCS, 2018.

Tight Bounds on The Fourier Spectrum of AC0
PDF Slides
CCC, 2017.

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").

Time-Space Hardness of Learning Sparse Parities
PDF Slides
joint with Gillat Kol and Ran Raz.
STOC, 2017.

Robust Sensitivity
joint with Shachar Lovett and Jiapeng Zhang.
To appear in SODA, 2018.

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)

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 Video (of Amir @ MSR)
joint with Amir Shpilka.
Combinatorica, 2014 (preliminary version in CCC, 2011).