Követés
Avishay Tal
Cím
Hivatkozott rá
Hivatkozott rá
Év
Oracle Separation of BQP and PH
R Raz, A Tal
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
1442019
Tight bounds on the Fourier spectrum of AC0
A Tal
32nd Computational Complexity Conference (CCC 2017), 15: 1-15: 31, 2017
1192017
Shrinkage of De Morgan formulae by spectral techniques
A Tal
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 551-560, 2014
90*2014
Properties and applications of boolean function composition
A Tal
Proceedings of the 4th conference on Innovations in Theoretical Computer …, 2013
842013
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
822019
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
77*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
752018
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
672017
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
67*2013
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
622023
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
532019
Degree and sensitivity: tails of two distributions
P Gopalan, R Servedio, A Tal, A Wigderson
arXiv preprint arXiv:1604.07432, 2016
472016
On the structure of boolean functions with small spectral norm
A Shpilka, A Tal, BL Volk
computational complexity 26 (1), 229-273, 2017
462017
Two structural results for low degree polynomials and applications
G Cohen, A Tal
arXiv preprint arXiv:1404.0654, 2014
422014
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), 22 …, 2019
402019
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
402018
On fractional block sensitivity
R Kulkarni, A Tal
Chicago J. Theor. Comput. Sci 8, 1-16, 2016
402016
Low-sensitivity functions from unambiguous certificates
S Ben-David, P Hatami, A Tal
arXiv preprint arXiv:1605.07084, 2016
362016
AC0 [p] lower bounds against MCSP via the coin problem
A Golovnev, R Ilango, R Impagliazzo, V Kabanets, A Kolokolova, A Tal
ICALP, 2019
352019
Rigid matrices from rectangular PCPs
A Bhangale, P Harsha, O Paradise, A Tal
SIAM Journal on Computing 53 (2), 480-523, 2024
322024
A rendszer jelenleg nem tudja elvégezni a műveletet. Próbálkozzon újra később.
Cikkek 1–20