https://avishaytal.org

Avishay TalAvishay TalSearch this siteEmbedded FilesSkip to main contentSkip to navigationAvishay TalAvishay TalCS 172 Computability and Complexity (Fall 2024)Lecture Schedule Fall 2024Course Policies and Information (Fall 2024)CS 294-202 PseudorandomnessCS 278 Computational Complexity Theory (Spring 2024)CS 294-92: Analysis of Boolean Functions (Spring 2025)STOC 2020 Workshop: Derandomizing Space-Bounded ComputationAvishay TalAvishay TalHi, I'm Avishay, an Assistant Professor at the Department of Electrical Engineering and Computer Sciences at UC Berkeley. I am honored to be part of Berkeley's Theory Group.I received my Ph.D. in 2015 from the Weizmann Institute of Science, under the guidance of Ran Raz. Prior to that, I was an M.Sc. 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 InterestsComputational 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?Contact InformationAddress:635 Soda HallDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA, 94720E-mail: atal "at" berkeley.eduEventsWorkshop on Derandomizing Space-Bounded Computation (Part of STOC 2020)Advances in Boolean Function Analysis Lecture Series @ The Simons Institute (Summer 2020)Program on Analysis and TCS : New Frontiers @ The Simons Institute (Summer 2023) -- and its reunion (July 2024)TeachingCS 294-92 - Analysis of Boolean Functions - Spring 2020CS 170 - Efficient Algorithms and Intractable Problems - Fall 2020CS 278 - Computational Complexity Theory - Spring 2021CS 294-202 - Pseudorandomness - Fall 2021CS 172 - Computability and Complexity - Spring 2022CS 172 - Computability and Complexity - Fall 2022CS 294-92 - Analysis of Boolean Functions - Spring 2023CS 70 - Discrete Mathematics and Probability Theory - Fall 2023CS 278 - Computational Complexity Theory - Spring 2024CS 172 - Computability and Complexity - Fall 2024CS 294-92 - Analysis of Boolean Functions - Spring 2025Program CommitteesFOCS 2019,  SODA 2020,  CCC 2020,  RANDOM 2020,  ITCS 2021,  STOC 2021, ITCS 2023, STOC 2024, ITCS 2025, CCC 2025, FOCS 2025Group InformationCurrent Ph.D. StudentsOrr Paradise (co-advised with Shafi Goldwasser)Kewen WuZoë Bell (co-advised with Shafi Goldwasser)Xin Lyu (co-advised with Jelani Nelson)Hongxun Wu (co-advised with Jelani Nelson)Current PostdocsLijie Chen - Miller FellowFormer StudentsMichael Whitmeyer - M.Sc.  (now a PhD student @ UW)Vishnu Iyer - Undergraduate researcher (now a PhD student @ UT Austin)Nagaganesh Jaladanki - M.Sc. (now Software Engineer @ Stripe)Former PostdocsWilliam M. Hoza - Simons-Berkeley postdoc (now Faculty at U Chicago)Makrand Sinha - Simons-Berkeley postdoc (now Faculty at UIUC)PublicationsQuantum Computable One-Way Functions without One-Way FunctionsPDFjoint with William Kretschmer and Luowen QianQIP, 2025. STOC, 2025.The Power of Adaptivity in Quantum Query AlgorithmsPDFjoint with Uma Girish, Makrand Sinha, and Kewen WuPresented at the 27th Annual Conference on Quantum Information Processing (QIP 2024).STOC, 2024.Tight Time-Space Lower Bounds for Constant-Pass LearningPDFjoint with Xin Lyu, Hongxun Wu, and Junzhao YangFOCS, 2023.Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and ShortcuttingPDF William@IASjoint with Lijie Chen, William Hoza, Xin Lyu, and Hongxun WuFOCS, 2023.Fourier Growth of Communication Protocols for XOR FunctionsPDFjoint with Uma Girish, Makrand Sinha, and Kewen WuFOCS, 2023.New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs PDFjoint with Lijie Chen, Xin Lyu,  and Hongxun WuICALP, 2023.Quantum Cryptography in AlgorithmicaPDFjoint with William Kretschmer, Luowen Qian, and Makrand Sinha.Presented at the 26th Annual Conference on Quantum Information Processing (QIP 2023).STOC, 2023.Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees PDFjoint with Pooya Hatami, William Hoza, and Roei Tell.STOC, 2023.On Certified Randomness from Quantum Advantage ExperimentsPDFjoint with Roozbeh Bassirian, Adam Bouland, Bill Fefferman, and Sam Gunn.Fourier Growth of Parity Decision TreesPDFjoint with Uma Girish and Kewen Wu.CCC, 2021.Pseudorandom Generators for Read-Once Monotone Branching ProgramsPDFjoint with Dean Doron, Raghu Meka, Omer Reingold, and Salil Vadhan.RANDOM, 2021.Fooling Constant-Depth Threshold CircuitsPDFjoint with Pooya Hatami, William Hoza, and Roei Tell.FOCS, 2021.Junta Distance Approximation with Sub-Exponential QueriesPDFjoint with Vishnu Iyer and Michael Whitmeyer.CCC, 2021.Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0PDFjoint with Yuval Filmus and Or Meir.ITCS, 2021.Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity TheoremPDFjoint with Scott Aaronson, Shalev Ben-David, Robin Kothari, and Shravas Rao.(Subsumes an earlier version named "Quantum Implications of Huang's Sensitivity Theorem")Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021) as a short plenary talk.STOC, 2021.Rigid Matrices From Rectangular PCPsPDF  Prahladh@IASjoint with Amey Bhangale, Prahladh Harsha, and Orr Paradise.FOCS, 2020. SICOMP, 2024.Towards Optimal Separations between Quantum and Randomized Query ComplexitiesPDF FOCS Long TalkFOCS, 2020.Quantum versus Randomized Communication Complexity, with Efficient PlayersPDFjoint with Uma Girish and Ran Raz.Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020).ITCS, 2021. Computational Complexity Journal 2022.On the Computational Power of Radio ChannelsPDFjoint with Mark Braverman, Gillat Kol, and Rotem Oshman.DISC, 2019.Time-Space Lower Bounds for Two-Pass LearningPDFjoint with Sumegha Garg and Ran Raz.CCC, 2019.AC0[p] Lower Bounds against MCSP via the Coin ProblemPDFjoint with Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova.ICALP, 2019.Oracle Separation of BQP and PHPDFjoint with Ran Raz.STOC, 2019. (Best Paper Award). JACM, 2022.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 circuitsPDFjoint 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 ProgramsPDFjoint with Raghu Meka and Omer Reingold.STOC, 2019.[Oded's choices]Pseudorandom generators from the second Fourier level and applications to AC0 with parity gatesPDFjoint with Eshan Chattopadhyay, Pooya Hatami, and Shachar Lovett.ITCS, 2019.Cubic Formula Size Lower Bounds Based on Compositions with MajorityPDFjoint with Anna Gal and Adrian Trejo Nuñez.ITCS, 2019.Improved Pseudorandomness for Unordered Branching Programs through Local MonotonicityPDFjoint with Eshan Chattopadhyay, Pooya Hatami and Omer Reingold.STOC, 2018.Extractor-Based Time-Space Lower Bounds for LearningPDFjoint with Sumegha Garg and Ran Raz.STOC, 2018.On Constant-Depth Canonical Boolean Circuits for Computing Multilinear FunctionsPDFjoint with Oded Goldreich.Book chapter in "Computational Complexity and Property Testing", 2020.The Choice and Agreement Problems of a Random FunctionPDFjoint with Or Meir.Information Processing Letters, Volume 133, 2018.Pseudorandom Generators for Low Sensitivity FunctionsPDFjoint with Pooya Hatami.ITCS, 2018.Robust SensitivityPDFjoint with Shachar Lovett and Jiapeng Zhang.SODA, 2018.Lower Bounds for 2-Query LCCs over Large AlphabetPDFjoint with Arnab Bhattacharyya and Sivakanth Gopi.RANDOM, 2017.Tight Bounds on The Fourier Spectrum of AC0PDF SlidesCCC, 2017.[Oded's choices]The Bipartite Formula Complexity of Inner-Product is QuadraticPDFSTOC, 2017 (merged with "Computing Requires Larger Formulas than Approximating").Computing Requires Larger Formulas than ApproximatingPDF Slides TCS+ TalkSTOC, 2017 (merged with "The Bipartite Formula Complexity of Inner-Product is Quadratic").[Oded's choices]Time-Space Hardness of Learning Sparse ParitiesPDF Slidesjoint with Gillat Kol and Ran Raz.STOC, 2017.Low-Sensitivity Functions from Unambiguous CertificatesPDFjoint with Shalev Ben-David and Pooya Hatami.ITCS, 2017.Degree and Sensitivity: Tails of Two DistributionsPDFjoint 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 SlidesICALP, 2016.#SAT Algorithms from ShrinkagePDFMatrix Rigidity of Random Toeplitz MatricesPDF Journal-version Slides (STOC) Slides (longer version)joint with Oded Goldreich.STOC, 2016. Computational Complexity, 2016.Shrinkage of De Morgan Formulae by Spectral TechniquesPDF SlidesFOCS, 2014.On Fractional Block SensitivityPDF Journal-versionjoint 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 NormPDFjoint with Amir Shpilka and Ben lee Volk.ITCS, 2014. Computational Complexity Journal, 2015.Improved Average-Case Lower Bounds for De Morgan Formula SizePDF Journal-version Slidesjoint with Ilan Komargodski and Ran Raz.FOCS, 2013. SICOMP, 2017.Properties and Applications of Boolean Function CompositionPDF SlidesITCS, 2013. (Best Student Paper)[Oded's choices]On the Degree of Univariate Polynomials Over the IntegersPDF Journal-versionjoint with Gil Cohen and Amir Shpilka.ITCS, 2012. Combinatorica, 2016On The Minimal Fourier Degree of Symmetric Boolean FunctionsPDF Journal-version Slides Amir@MSRjoint with Amir Shpilka.CCC, 2011. Combinatorica, 2014.[Richard Lipton's Blog Post] [2]Google SitesReport abusePage detailsPage updated Google SitesReport abuseenusen-US1739255402https://avishaytal.org

Sahypaňyzy redaktirläňmi?

Näme edýärsiň?