Edit Profile (opens in new tab) Tal, Avishay Co-Author Distance Author ID: tal.avishay Published as: Tal, Avishay Documents Indexed: 41 Publications since 1969 1 Contribution as Editor Co-Authors: 41 Co-Authors with 35 Joint Publications 958 Co-Co-Authors all top 5 Co-Authors 5 single-authored 7 Raz, Ran 5 Shpilka, Amir 4 Hatami, Pooya 3 Cohen, Gil 3 Goldreich, Oded 3 Reingold, Omer 2 Ben-David, Shalev 2 Chattopadhyay, Eshan 2 Garg, Sumegha 2 Girish, Uma 2 Kol, Gillat 2 Kothari, Robin 2 Lovett, Shachar 2 Meir, Or 2 Meka, Raghu 2 Volk, Ben Lee 1 Aaronson, Scott 1 Bhattacharyya, Arnab 1 Braverman, Mark 1 Doron, Dean 1 Dvir, Zeev 1 Filmus, Yuval 1 Fisch, L. 1 Gál, Anna 1 Golovnev, Alexander 1 Gopi, Sivakanth 1 Ilango, Rahul 1 Impagliazzo, Russell 1 Iyer, Vishnu 1 Kabanets, Valentine 1 Kolokolova, Antonina 1 Komargodski, Ilan 1 Kulkarni, Raghav 1 Kurizki, Gershon 1 Oshman, Rotem 1 Rao, Shravas K. 1 Schaeffer, Luke 1 Trejo, Nuñez Adrian 1 Vadhan, Salil P. 1 Watts, Adam Bene 1 Whitmeyer, Michael 1 Wu, Kewen 1 Zhang, Jiapeng all top 5 Serials 3 Computational Complexity 2 Combinatorica 2 Theory of Computing 1 International Journal of Modern Physics B 1 International Journal for Numerical Methods in Fluids 1 Information Processing Letters 1 Journal of the Association for Computing Machinery 1 SIAM Journal on Computing 1 Chicago Journal of Theoretical Computer Science 1 Journal of the ACM all top 5 Fields 39 Computer science (68-XX) 6 Information and communication theory, circuits (94-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Number theory (11-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Numerical analysis (65-XX) 1 Mathematical logic and foundations (03-XX) 1 Field theory and polynomials (12-XX) 1 Partial differential equations (35-XX) 1 Fluid mechanics (76-XX) 1 Quantum theory (81-XX) 1 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 34 Publications have been cited 198 times in 149 Documents Cited by ▼ Year ▼ Properties and applications of Boolean function composition. Zbl 1361.68094 Tal, Avishay 21 2013 Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\). Zbl 1440.68084 Tal, Avishay 20 2017 Pseudorandom generators for width-3 branching programs. Zbl 1433.68604 Meka, Raghu; Reingold, Omer; Tal, Avishay 14 2019 Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound. Zbl 1376.03043 Komargodski, Ilan; Raz, Ran; Tal, Avishay 11 2017 On fractional block sensitivity. Zbl 1365.68288 Kulkarni, Raghav; Tal, Avishay 9 2016 Extractor-based time-space lower bounds for learning. Zbl 1428.68238 Garg, Sumegha; Raz, Ran; Tal, Avishay 9 2018 On the structure of Boolean functions with small spectral norm. Zbl 1371.94704 Shpilka, Amir; Tal, Avishay; Volk, Ben lee 9 2017 Oracle separation of BQP and PH. Zbl 1433.68152 Raz, Ran; Tal, Avishay 8 2019 Improved pseudorandomness for unordered branching programs through local monotonicity. Zbl 1427.68058 Chattopadhyay, Eshan; Hatami, Pooya; Reingold, Omer; Tal, Avishay 8 2018 Time-space hardness of learning sparse parities. Zbl 1370.68132 Kol, Gillat; Raz, Ran; Tal, Avishay 8 2017 Formula lower bounds via the quantum method. Zbl 1370.68142 Tal, Avishay 8 2017 Two structural results for low degree polynomials and applications. Zbl 1375.11074 Cohen, Gil; Tal, Avishay 8 2015 Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. Zbl 07559065 Chattopadhyay, Eshan; Hatami, Pooya; Lovett, Shachar; Tal, Avishay 8 2019 Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Zbl 1434.68179 Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay 7 2019 On the structure of Boolean functions with small spectral norm. Zbl 1365.94682 Shpilka, Amir; Tal, Avishay; Volk, Ben Lee 7 2014 On the minimal Fourier degree of symmetric Boolean functions. Zbl 1340.68042 Shpilka, Amir; Tal, Avishay 7 2014 \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem. Zbl 1524.68133 Golovnev, Alexander; Ilango, Rahul; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina; Tal, Avishay 7 2019 Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. Zbl 07765252 Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay 4 2021 Low-sensitivity functions from unambiguous certificates. Zbl 1402.68082 Ben-David, Shalev; Hatami, Pooya; Tal, Avishay 4 2017 Matrix rigidity of random Toeplitz matrices. Zbl 1398.68237 Goldreich, Oded; Tal, Avishay 3 2018 Matrix rigidity of random Toeplitz matrices. Zbl 1373.68271 Goldreich, Oded; Tal, Avishay 3 2016 Pseudorandom generators for read-once monotone branching programs. Zbl 07768403 Doron, Dean; Meka, Raghu; Reingold, Omer; Tal, Avishay; Vadhan, Salil 3 2021 On the sensitivity conjecture. Zbl 1388.68136 Tal, Avishay 2 2016 A boundary collocation method for the solution of a flow problem in a complex three-dimensional porous medium. Zbl 0597.76097 Levin, D.; Tal, A. 2 1986 Lower bounds for 2-query LCCs over large alphabet. Zbl 1467.68050 Bhattacharyya, Arnab; Gopi, Sivakanth; Tal, Avishay 2 2017 Fourier growth of parity decision trees. Zbl 07711621 Girish, Uma; Tal, Avishay; Wu, Kewen 1 2021 The robust sensitivity of Boolean functions. Zbl 1403.68083 Lovett, Shachar; Tal, Avishay; Zhang, Jiapeng 1 2018 On the degree of univariate polynomials over the integers. Zbl 1348.11024 Cohen, Gil; Shpilka, Amir; Tal, Avishay 1 2012 Oracle separation of BQP and PH. Zbl 07679913 Raz, Ran; Tal, Avishay 1 2022 On the degree of univariate polynomials over the integers. Zbl 1399.11080 Cohen, Gil; Shpilka, Amir; Tal, Avishay 1 2017 On monotone decomposable operators. Zbl 0175.45902 Tal, A. 1 1969 Pseudorandom generators for low sensitivity functions. Zbl 1462.68051 Hatami, Pooya; Tal, Avishay 1 2018 Cubic formula size lower bounds based on compositions with majority. Zbl 07559078 Gál, Anna; Tal, Avishay; Trejo, Nuñez Adrian 1 2019 Time-space lower bounds for two-pass learning. Zbl 07564422 Garg, Sumegha; Raz, Ran; Tal, Avishay 1 2019 Oracle separation of BQP and PH. Zbl 07679913 Raz, Ran; Tal, Avishay 1 2022 Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. Zbl 07765252 Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay 4 2021 Pseudorandom generators for read-once monotone branching programs. Zbl 07768403 Doron, Dean; Meka, Raghu; Reingold, Omer; Tal, Avishay; Vadhan, Salil 3 2021 Fourier growth of parity decision trees. Zbl 07711621 Girish, Uma; Tal, Avishay; Wu, Kewen 1 2021 Pseudorandom generators for width-3 branching programs. Zbl 1433.68604 Meka, Raghu; Reingold, Omer; Tal, Avishay 14 2019 Oracle separation of BQP and PH. Zbl 1433.68152 Raz, Ran; Tal, Avishay 8 2019 Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. Zbl 07559065 Chattopadhyay, Eshan; Hatami, Pooya; Lovett, Shachar; Tal, Avishay 8 2019 Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Zbl 1434.68179 Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay 7 2019 \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem. Zbl 1524.68133 Golovnev, Alexander; Ilango, Rahul; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina; Tal, Avishay 7 2019 Cubic formula size lower bounds based on compositions with majority. Zbl 07559078 Gál, Anna; Tal, Avishay; Trejo, Nuñez Adrian 1 2019 Time-space lower bounds for two-pass learning. Zbl 07564422 Garg, Sumegha; Raz, Ran; Tal, Avishay 1 2019 Extractor-based time-space lower bounds for learning. Zbl 1428.68238 Garg, Sumegha; Raz, Ran; Tal, Avishay 9 2018 Improved pseudorandomness for unordered branching programs through local monotonicity. Zbl 1427.68058 Chattopadhyay, Eshan; Hatami, Pooya; Reingold, Omer; Tal, Avishay 8 2018 Matrix rigidity of random Toeplitz matrices. Zbl 1398.68237 Goldreich, Oded; Tal, Avishay 3 2018 The robust sensitivity of Boolean functions. Zbl 1403.68083 Lovett, Shachar; Tal, Avishay; Zhang, Jiapeng 1 2018 Pseudorandom generators for low sensitivity functions. Zbl 1462.68051 Hatami, Pooya; Tal, Avishay 1 2018 Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\). Zbl 1440.68084 Tal, Avishay 20 2017 Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound. Zbl 1376.03043 Komargodski, Ilan; Raz, Ran; Tal, Avishay 11 2017 On the structure of Boolean functions with small spectral norm. Zbl 1371.94704 Shpilka, Amir; Tal, Avishay; Volk, Ben lee 9 2017 Time-space hardness of learning sparse parities. Zbl 1370.68132 Kol, Gillat; Raz, Ran; Tal, Avishay 8 2017 Formula lower bounds via the quantum method. Zbl 1370.68142 Tal, Avishay 8 2017 Low-sensitivity functions from unambiguous certificates. Zbl 1402.68082 Ben-David, Shalev; Hatami, Pooya; Tal, Avishay 4 2017 Lower bounds for 2-query LCCs over large alphabet. Zbl 1467.68050 Bhattacharyya, Arnab; Gopi, Sivakanth; Tal, Avishay 2 2017 On the degree of univariate polynomials over the integers. Zbl 1399.11080 Cohen, Gil; Shpilka, Amir; Tal, Avishay 1 2017 On fractional block sensitivity. Zbl 1365.68288 Kulkarni, Raghav; Tal, Avishay 9 2016 Matrix rigidity of random Toeplitz matrices. Zbl 1373.68271 Goldreich, Oded; Tal, Avishay 3 2016 On the sensitivity conjecture. Zbl 1388.68136 Tal, Avishay 2 2016 Two structural results for low degree polynomials and applications. Zbl 1375.11074 Cohen, Gil; Tal, Avishay 8 2015 On the structure of Boolean functions with small spectral norm. Zbl 1365.94682 Shpilka, Amir; Tal, Avishay; Volk, Ben Lee 7 2014 On the minimal Fourier degree of symmetric Boolean functions. Zbl 1340.68042 Shpilka, Amir; Tal, Avishay 7 2014 Properties and applications of Boolean function composition. Zbl 1361.68094 Tal, Avishay 21 2013 On the degree of univariate polynomials over the integers. Zbl 1348.11024 Cohen, Gil; Shpilka, Amir; Tal, Avishay 1 2012 A boundary collocation method for the solution of a flow problem in a complex three-dimensional porous medium. Zbl 0597.76097 Levin, D.; Tal, A. 2 1986 On monotone decomposable operators. Zbl 0175.45902 Tal, A. 1 1969 all cited Publications top 5 cited Publications all top 5 Cited by 228 Authors 12 Tal, Avishay 8 Hatami, Pooya 6 Sanyal, Swagato 6 Srinivasan, Srikanth 5 Dvir, Zeev 5 Hoza, William M. 5 Lee, Troy 5 Oliveira, Igor Carboni 5 Raz, Ran 5 Santhanam, Rahul 5 Tell, Roei 4 Gopi, Sivakanth 4 Santha, Miklos 4 Shpilka, Amir 3 Allender, Eric W. 3 Ben-David, Shalev 3 Bun, Mark 3 Castro, Francis Noel 3 Chattopadhyay, Eshan 3 Filmus, Yuval 3 Find, Magnus Gausdal 3 Gál, Anna 3 Goldreich, Oded 3 Harsha, Prahladh 3 Kabanets, Valentine 3 Kothari, Robin 3 Lu, Zhenjian 3 Medina, Luis A. 3 Sanders, Tom 3 Thaler, Justin 3 Vadhan, Salil P. 3 Vihrovs, Jevgēnijs 3 Wigderson, Avi 3 Xie, Ning 3 Zuckerman, David 2 Ambainis, Andris 2 Bhandari, Siddharth 2 Boyar, Joan F. 2 Chaubal, Siddhesh 2 Chen, Lijie 2 Dodis, Yevgeniy 2 Doron, Dean 2 Garg, Sumegha 2 Gavinsky, Dmitry 2 Golovnev, Alexander 2 Gu, Yuzhou 2 Hatami, Hamed 2 Ilango, Rahul 2 Jain, Rahul 2 Kulikov, Alexander S. 2 Kundu, Srijita 2 Lee, Chin Ho 2 Li, Yaqiao 2 Liu, Allen P. 2 Lovett, Shachar 2 Molli, Tulasimohan 2 Mossel, Elchanan 2 Myrisiotis, Dimitrios 2 Pich, Ján 2 Prūsis, Krišjānis 2 Quach, Willy 2 Saks, Michael E. 2 Servedio, Rocco A. 2 Sherstov, Alexander A. 2 Tamaki, Suguru 2 Tan, Liyang 2 Tani, Seiichiro 2 Vidick, Thomas 2 Viola, Emanuele 2 Wichs, Daniel 2 Xu, Shuai 2 Xu, Yekun 1 Aaronson, Scott 1 Akbar, Sana 1 Ali, Tibra 1 Alman, Josh 1 Andoni, Alexandr 1 Anshu, Anurag 1 Asensio Ferrero, Sara 1 Baez, Maria Laura 1 Beame, Paul W. 1 Ben-David, Shai 1 Bhattacharyya, Arpan 1 Biswas, Aniruddha 1 Bogdanov, Andrej 1 Brakensiek, Joshua 1 Briët, Jop 1 Broll, Marek 1 Bürgisser, Peter 1 Canale, Federico 1 Carboni, Oliveira Igor 1 Carlet, Claude 1 Cavalar, Bruno Pasqualotto 1 Chapman, Robin J. 1 Chen, Ruiwen 1 Cheng, Kuan 1 Cheraghchi, Mahdi 1 Chiarelli, John 1 Chistopolskaya, Anastasiya 1 Choi, Minjin ...and 128 more Authors all top 5 Cited in 38 Serials 13 SIAM Journal on Computing 9 Theoretical Computer Science 9 Computational Complexity 8 Theory of Computing 4 Combinatorica 4 Theory of Computing Systems 3 Journal of Computer and System Sciences 3 SIAM Journal on Discrete Mathematics 3 Foundations and Trends in Theoretical Computer Science 2 Communications in Mathematical Physics 2 Discrete Applied Mathematics 2 Israel Journal of Mathematics 2 Random Structures & Algorithms 2 Annals of Mathematics. Second Series 2 Quantum Information Processing 2 Cryptography and Communications 1 Discrete Mathematics 1 Journal d’Analyse Mathématique 1 Mathematical Proceedings of the Cambridge Philosophical Society 1 The Annals of Statistics 1 Compositio Mathematica 1 Probability Theory and Related Fields 1 Algorithmica 1 Linear Algebra and its Applications 1 Proceedings of the National Academy of Sciences of the United States of America 1 Bulletin of the American Mathematical Society. New Series 1 New Zealand Journal of Mathematics 1 The Journal of Fourier Analysis and Applications 1 Chicago Journal of Theoretical Computer Science 1 Fundamenta Informaticae 1 Journal of High Energy Physics 1 Lobachevskii Journal of Mathematics 1 La Gaceta de la Real Sociedad Matemática Española 1 Oberwolfach Reports 1 Advances in Mathematics of Communications 1 LIPIcs – Leibniz International Proceedings in Informatics 1 Forum of Mathematics, Sigma 1 Computer Science Review all top 5 Cited in 23 Fields 120 Computer science (68-XX) 33 Information and communication theory, circuits (94-XX) 20 Order, lattices, ordered algebraic structures (06-XX) 17 Combinatorics (05-XX) 13 Quantum theory (81-XX) 8 Number theory (11-XX) 4 Mathematical logic and foundations (03-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 4 Abstract harmonic analysis (43-XX) 4 Operations research, mathematical programming (90-XX) 3 Field theory and polynomials (12-XX) 3 Group theory and generalizations (20-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 General and overarching topics; collections (00-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Statistics (62-XX) 2 Numerical analysis (65-XX) 1 History and biography (01-XX) 1 General algebraic systems (08-XX) 1 Functional analysis (46-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Relativity and gravitational theory (83-XX) Citations by Year