Avishay TalHi, 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,
- Computational Learning Theory,
- Quantum Computing,
- Combinatorics, and
- Connections between Algorithms and Lower Bounds.
Motivating questions that guide my research:
- What is the power and limitations of parallel computation?
- What is the role of randomness in computation?
- What is the role of memory in learning?
- For which tasks do quantum algorithms outperform classical algorithms?
My Curriculum Vitae (updated: February 2019). Contact Information Address:
635 Soda Hall Department of Electrical Engineering and Computer Sciences University of California, Berkeley Berkeley, CA, 94720 E-mail: atal "at" berkeley.eduEventsWorkshop on Derandomizing Space-Bounded Computation (Part of STOC 2020)
Advances in Boolean Function Analysis Lecture Series @ The Simons Institute
TeachingCS 294-92 - Analysis of Boolean Functions - Spring 2020.
CS 170 - Efficient Algorithms and Intractable Problems - Fall 2020.
CS 278 - Computational Complexity Theory - Spring 2021.
PublicationsFooling Constant-Depth Threshold Circuitsjoint with Pooya Hatami, William Hoza, and Roei Tell. Junta Distance Approximation with Sub-Exponential Queriesjoint with Vishnu Iyer and Michael Whitmeyer. Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0joint with Yuval Filmus and Or Meir ITCS, 2021. Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theoremjoint with Scott Aaronson, Shalev Ben-David, Robin Kothari, and Shravas Rao. (Subsumes an earlier version named "Quantum Implications of Huang's Sensitivity Theorem") To be presented at QIP 2021 as a short plenary talk. STOC, 2021.
Rigid Matrices From Rectangular PCPsjoint with Amey Bhangale, Prahladh Harsha, and Orr Paradise. FOCS, 2020. Towards Optimal Separations between Quantum and Randomized Query ComplexitiesPDF FOCS Long Talk FOCS, 2020. Quantum versus Randomized Communication Complexity, with Efficient Playersjoint with Uma Girish and Ran Raz. Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020). ITCS, 2021. On the Computational Power of Radio Channelsjoint with Mark Braverman, Gillat Kol, and Rotem Oshman. DISC, 2019. Time-Space Lower Bounds for Two-Pass Learningjoint with Sumegha Garg and Ran Raz. CCC, 2019. AC0[p] Lower Bounds against MCSP via the Coin Problemjoint with Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. ICALP, 2019. Oracle Separation of BQP and PHjoint 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 circuitsjoint 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 Programsjoint with Raghu Meka and Omer Reingold. STOC, 2019. [Oded's choices] Pseudorandom generators from the second Fourier level and applications to AC0 with parity gatesjoint with Eshan Chattopadhyay, Pooya Hatami, and Shachar Lovett. ITCS, 2019. Cubic Formula Size Lower Bounds Based on Compositions with Majorityjoint with Anna Gal and Adrian Trejo Nuñez. ITCS, 2019. Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicityjoint with Eshan Chattopadhyay, Pooya Hatami and Omer Reingold. STOC, 2018. Extractor-Based Time-Space Lower Bounds for Learningjoint with Sumegha Garg and Ran Raz. STOC, 2018. On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functionsjoint with Oded Goldreich. The Choice and Agreement Problems of a Random Functionjoint with Or Meir. Information Processing Letters, Volume 133, 2018. Pseudorandom Generators for Low Sensitivity Functionsjoint with Pooya Hatami. ITCS, 2018. Robust Sensitivityjoint with Shachar Lovett and Jiapeng Zhang. SODA, 2018. Lower Bounds for 2-Query LCCs over Large Alphabetjoint with Arnab Bhattacharyya and Sivakanth Gopi. RANDOM, 2017. Tight Bounds on The Fourier Spectrum of AC0PDF Slides CCC, 2017. [Oded's choices] The Bipartite Formula Complexity of Inner-Product is QuadraticSTOC, 2017 (merged with "Computing Requires Larger Formulas than Approximating"). Computing Requires Larger Formulas than ApproximatingPDF 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 ParitiesPDF Slides joint with Gillat Kol and Ran Raz. STOC, 2017. Low-Sensitivity Functions from Unambiguous Certificatesjoint with Shalev Ben-David and Pooya Hatami. ITCS, 2017. Degree and Sensitivity: Tails of Two Distributionsjoint 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 ConjecturePDF Slides ICALP, 2016. #SAT Algorithms from ShrinkageMatrix Rigidity of Random Toeplitz MatricesPDF 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 TechniquesPDF Slides FOCS, 2014. On Fractional Block SensitivityPDF Journal-version joint with Raghav Kulkarni. CJTCS, 2016. Two Structural Results for Low Degree Polynomials and ApplicationsPDF 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 Normjoint with Amir Shpilka and Ben lee Volk. Computational Complexity, 2015 (preliminary version in ITCS, 2014). Improved Average-Case Lower Bounds for De Morgan Formula SizePDF Journal-version Slides joint with Ilan Komargodski and Ran Raz. SICOMP, 2017 (preliminary version in FOCS, 2013). Properties and Applications of Boolean Function CompositionPDF Slides ITCS, 2013. (Best Student Paper) [Oded's choices] On the Degree of Univariate Polynomials Over the IntegersPDF Journal-version joint with Gil Cohen and Amir Shpilka. Combinatorica, 2016 (preliminary version in ITCS, 2012). On The Minimal Fourier Degree of Symmetric Boolean FunctionsPDF Journal-version Slides Amir@MSR joint with Amir Shpilka. Combinatorica, 2014 (preliminary version in CCC, 2011). [Richard Lipton's Blog Post] [2] |