 Avishay Tal
Hi, I'm Avishay, a postdoctoral scholar hosted by Omer Reingold at Stanford's theory group.
During the Fall Semester of 2018, I was a research fellow in the Lower Bounds in Computational Complexity at the Simons Institute for the Theory of Computing.
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 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. Main Research Interests:
My Curriculum Vitae (updated: February 2019). 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
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] |