×
Author ID: tal.avishay Recent zbMATH articles by "Tal, Avishay"
Published as: Tal, Avishay

Publications by Year

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 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

Citations by Year