Avishay Tal
Titel
Zitiert von
Zitiert von
Jahr
Tight bounds on the Fourier spectrum of AC0
A Tal
32nd Computational Complexity Conference (CCC 2017), 2017
722017
Properties and applications of Boolean function composition
A Tal
Proceedings of the 4th conference on Innovations in Theoretical Computer …, 2013
562013
Shrinkage of De Morgan formulae by spectral techniques
A Tal
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 551-560, 2014
53*2014
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
53*2013
Oracle Separation of BQP and PH
R Raz, A Tal
372018
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
332018
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
332017
On the structure of boolean functions with small spectral norm
A Shpilka, A Tal, B lee Volk
computational complexity 26 (1), 229-273, 2017
322017
Degree and sensitivity: tails of two distributions
P Gopalan, R Servedio, A Tal, A Wigderson
arXiv preprint arXiv:1604.07432, 2016
312016
Two structural results for low degree polynomials and applications
G Cohen, A Tal
arXiv preprint arXiv:1404.0654, 2014
252014
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
242019
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
232018
On fractional block sensitivity
R Kulkarni, A Tal
Chicago J. Theor. Comput. Sci 2016, 2, 2016
232016
Low-sensitivity functions from unambiguous certificates
S Ben-David, P Hatami, A Tal
arXiv preprint arXiv:1605.07084, 2016
212016
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
202018
Matrix rigidity of random toeplitz matrices
O Goldreich, A Tal
computational complexity 27 (2), 305-350, 2018
202018
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
162019
Formula lower bounds via the quantum method
A Tal
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017
162017
# SAT Algorithms from Shrinkage.
A Tal
Electronic Colloquium on Computational Complexity (ECCC) 22, 114, 2015
162015
On the minimal fourier degree of symmetric boolean functions
A Shpilka, A Tal
2011 IEEE 26th Annual Conference on Computational Complexity, 200-209, 2011
162011
Das System kann den Vorgang jetzt nicht ausführen. Versuchen Sie es später erneut.
Artikel 1–20