Avishay Tal

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 Publications Extractor-Based Time-Space Lower Bounds for Learning PDF joint with Sumegha Garg and Ran Raz. Lower Bounds for 2-Query LCCs over Large Alphabet PDF joint with Arnab Bhattacharyya and Sivakanth Gopi. RANDOM, 2017. Pseudorandom Generators for Low Sensitivity Functions PDF joint with Pooya Hatami. Tight Bounds on The Fourier Spectrum of AC0 PDF Slides CCC, 2017. 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 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 PDF joint with Shachar Lovett and Jiapeng Zhang. 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) 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).