Avishay Tal

Cited by

	All	Since 2019
Citations	1582	1269
h-index	24	22
i10-index	34	31

300

150

225

2013201420152016201720182019202020212022202320246 23 26 75 68 104 135 203 229 181 218 293

Public access

View all

27 articles

1 article

available

not available

Based on funding mandates

Co-authors

Ran RazPrinceton UniversityVerified email at princeton.edu
Pooya HatamiThe Ohio State UniversityVerified email at osu.edu
Robin KothariStaff Research Scientist, Google Quantum AIVerified email at robinkothari.com
Omer ReingoldStanford UniversityVerified email at stanford.edu
Shalev Ben-DavidAssociate Professor, University of WaterlooVerified email at uwaterloo.ca
Sumegha GargAssistant Professor, Rutgers UniversityVerified email at rutgers.edu
Eshan ChattopadhyayAssociate Professor at Cornell UniversityVerified email at cs.cornell.edu
Shachar LovettAssociate Professor of Computer Science, University of California San DiegoVerified email at eng.ucsd.edu
Ilan KomargodskiHebrew UniversityVerified email at cs.huji.ac.il
Makrand SinhaAssistant Professor, Computer Science, University of Illinois Urbana-ChampaignVerified email at illinois.edu
Raghu MekaUniversity of California, Los AngelesVerified email at cs.ucla.edu
Gil CohenSenior lecturer at Tel Aviv UniversityVerified email at tauex.tau.ac.il
Adam Bene WattsInstitute for Quantum Computing, University of WaterlooVerified email at mit.edu
Gillat KolPrinceton UniversityVerified email at princeton.edu
Oded GoldreichProfessor of Computer Science, Weizmann Institute of ScienceVerified email at weizmann.ac.il
William KretschmerUniversity of California, BerkeleyVerified email at berkeley.edu
Luowen QianNTT Research, Inc.Verified email at bu.edu
Kewen WuUC BerkeleyVerified email at berkeley.edu
William M. HozaUniversity of ChicagoVerified email at uchicago.edu
Hongxun WuUniversity of California, BerkeleyVerified email at berkeley.edu

Avishay Tal

UC Berkeley

Verified email at berkeley.edu - Homepage

Theoretical Computer Science Computational Complexity Pseudorandomness Circuit Lower Bounds Analysis of Boolean Functions


Title Sort by citations Sort by year Sort by title	Cited by Cited by	Year
Oracle Separation of BQP and PH R Raz, A Tal Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019	142	2019
Tight bounds on the Fourier spectrum of AC0 A Tal 32nd Computational Complexity Conference (CCC 2017), 2017	119	2017
Shrinkage of De Morgan formulae by spectral techniques A Tal 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 551-560, 2014	89*	2014
Properties and applications of boolean function composition A Tal Proceedings of the 4th conference on Innovations in Theoretical Computer …, 2013	84	2013
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits AB Watts, R Kothari, L Schaeffer, A Tal Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019	78	2019
Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem S Aaronson, S Ben-David, R Kothari, S Rao, A Tal Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021	73*	2021
Extractor-based time-space lower bounds for learning S Garg, R Raz, A Tal Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018	72	2018
Improved average-case lower bounds for demorgan formula size I Komargodski, R Raz, A Tal 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 588-597, 2013	66*	2013
Time-space hardness of learning sparse parities G Kol, R Raz, A Tal Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017	64	2017
Quantum cryptography in algorithmica W Kretschmer, L Qian, M Sinha, A Tal Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 1589-1602, 2023	57	2023
Pseudorandom generators for width-3 branching programs R Meka, O Reingold, A Tal Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019	51	2019
Degree and sensitivity: tails of two distributions P Gopalan, R Servedio, A Tal, A Wigderson arXiv preprint arXiv:1604.07432, 2016	47	2016
On the structure of boolean functions with small spectral norm A Shpilka, A Tal, BL Volk computational complexity 26 (1), 229-273, 2017	45	2017
Two structural results for low degree polynomials and applications G Cohen, A Tal arXiv preprint arXiv:1404.0654, 2014	42	2014
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates E Chattopadhyay, P Hatami, S Lovett, A Tal 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 2018	40	2018
Improved pseudorandomness for unordered branching programs through local monotonicity E Chattopadhyay, P Hatami, O Reingold, A Tal Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018	39	2018
On fractional block sensitivity R Kulkarni, A Tal Chicago J. Theor. Comput. Sci 8, 1-16, 2016	39	2016
AC0 [p] lower bounds against MCSP via the coin problem A Golovnev, R Ilango, R Impagliazzo, V Kabanets, A Kolokolova, A Tal ICALP, 2019	35	2019
Low-sensitivity functions from unambiguous certificates S Ben-David, P Hatami, A Tal arXiv preprint arXiv:1605.07084, 2016	35	2016
Rigid matrices from rectangular PCPs A Bhangale, P Harsha, O Paradise, A Tal SIAM Journal on Computing 53 (2), 480-523, 2024	32	2024

The system can't perform the operation now. Try again later.

Articles 1–20

Citations per year

Duplicate citations

Merged citations

Add co-authorsCo-authors

Follow

Cited by

Co-authors