Avishay Tal

Hi, I'm Avishay, a postdoctoral researcher in the Theoretical Computer Science and Discrete Mathematics group (CSDM) at the Institute for Advanced Study (IAS).
 
In September 2015,  I received my PhD from the Weizmann Institute of Science, under the guidance of Ran RazBefore 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.


Contact Info:
Address: School of Mathematics, Institute for Advanced StudyPrinceton, NJ 08540, USA
E-mail: firstname.lastname@gmail.com







Publications

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.

Tight Bounds on The Fourier Spectrum of AC0
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
STOC, 2017 (merged with "The Bipartite Formula Complexity of Inner-Product is Quadratic").

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

Robust Sensitivity
joint with Shachar Lovett and Jiapeng Zhang.

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.

On the Sensitivity Conjecture
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
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
joint with Ilan Komargodski and Ran Raz. 
SICOMP, 2017 (preliminary version in FOCS, 2013). 

Properties and Applications of Boolean Function Composition
ITCS, 2013. (Best Student Paper)

On the Degree of Univariate Polynomials Over the Integers
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).