default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAvishay Tal
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j11]Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices from Rectangular PCPs. SIAM J. Comput. 53(2): 480-523 (2024)- [c42]Uma Girish
, Makrand Sinha, Avishay Tal, Kewen Wu:
The Power of Adaptivity in Quantum Query Algorithms. STOC 2024: 1488-1497 - 2023
- [c41]Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu:
Fourier Growth of Communication Protocols for XOR Functions. FOCS 2023: 721-732 - [c40]Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang:
Tight Time-Space Lower Bounds for Constant-Pass Learning. FOCS 2023: 1195-1202 - [c39]Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu:
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. FOCS 2023: 1224-1239 - [c38]Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu:
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. ICALP 2023: 39:1-39:20 - [c37]Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell:
Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. STOC 2023: 895-904 - [c36]William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal:
Quantum Cryptography in Algorithmica. STOC 2023: 1589-1602 - [i55]Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu:
Fourier Growth of Communication Protocols for XOR Functions. CoRR abs/2307.13926 (2023) - [i54]Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang:
Tight Time-Space Lower Bounds for Constant-Pass Learning. CoRR abs/2310.08070 (2023) - [i53]Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu:
The Power of Adaptivity in Quantum Query Algorithms. CoRR abs/2311.16057 (2023) - [i52]Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu:
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j10]Uma Girish, Ran Raz, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. Comput. Complex. 31(2): 17 (2022) - [j9]Ran Raz, Avishay Tal:
Oracle Separation of BQP and PH. J. ACM 69(4): 30:1-30:21 (2022) - [j8]Zeev Dvir, Avishay Tal:
Guest Editors' Foreword to the CCC 2020 Special Issue. Theory Comput. 18: 1-4 (2022) - [i51]William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal:
Quantum Cryptography in Algorithmica. CoRR abs/2212.00879 (2022) - [i50]Pooya Hatami, William Hoza, Avishay Tal, Roei Tell:
Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c35]Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan:
Pseudorandom Generators for Read-Once Monotone Branching Programs. APPROX-RANDOM 2021: 58:1-58:21 - [c34]Vishnu Iyer, Avishay Tal, Michael Whitmeyer:
Junta Distance Approximation with Sub-Exponential Queries. CCC 2021: 24:1-24:38 - [c33]Uma Girish, Avishay Tal, Kewen Wu:
Fourier Growth of Parity Decision Trees. CCC 2021: 39:1-39:36 - [c32]Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell:
Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS 2021: 104-115 - [c31]Uma Girish, Ran Raz, Avishay Tal:
Quantum Versus Randomized Communication Complexity, with Efficient Players. ITCS 2021: 54:1-54:20 - [c30]Yuval Filmus, Or Meir, Avishay Tal:
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). ITCS 2021: 89:1-89:7 - [c29]Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal:
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. STOC 2021: 1330-1342 - [i49]Uma Girish, Avishay Tal, Kewen Wu:
Fourier Growth of Parity Decision Trees. CoRR abs/2103.11604 (2021) - [i48]Vishnu Iyer, Avishay Tal, Michael Whitmeyer:
Junta Distance Approximation with Sub-Exponential Queries. CoRR abs/2106.00287 (2021) - [i47]Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan:
Monotone Branching Programs: Pseudorandomness and Circuit Complexity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i46]Uma Girish, Avishay Tal, Kewen Wu:
Fourier Growth of Parity Decision Trees. Electron. Colloquium Comput. Complex. TR21 (2021) - [i45]Pooya Hatami, William Hoza, Avishay Tal, Roei Tell:
Fooling Constant-Depth Threshold Circuits. Electron. Colloquium Comput. Complex. TR21 (2021) - [i44]Vishnu Iyer, Avishay Tal, Michael Whitmeyer:
Junta Distance Approximation with Sub-Exponential Queries. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c28]Avishay Tal:
Towards Optimal Separations between Quantum and Randomized Query Complexities. FOCS 2020: 228-239 - [c27]Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. FOCS 2020: 858-869 - [p1]Oded Goldreich, Avishay Tal:
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. Computational Complexity and Property Testing 2020: 306-325 - [i43]Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal:
Quantum Implications of Huang's Sensitivity Theorem. CoRR abs/2004.13231 (2020) - [i42]Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices From Rectangular PCPs. CoRR abs/2005.03123 (2020) - [i41]Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal:
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem. CoRR abs/2010.12629 (2020) - [i40]Yuval Filmus, Or Meir, Avishay Tal:
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. CoRR abs/2012.02210 (2020) - [i39]Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal:
Quantum Implications of Huang's Sensitivity Theorem. Electron. Colloquium Comput. Complex. TR20 (2020) - [i38]Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices From Rectangular PCPs. Electron. Colloquium Comput. Complex. TR20 (2020) - [i37]Yuval Filmus, Or Meir, Avishay Tal:
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [c26]Sumegha Garg, Ran Raz, Avishay Tal:
Time-Space Lower Bounds for Two-Pass Learning. CCC 2019: 22:1-22:39 - [c25]Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal:
AC0[p] Lower Bounds Against MCSP via the Coin Problem. ICALP 2019: 66:1-66:15 - [c24]Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal:
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. ITCS 2019: 22:1-22:15 - [c23]Anna Gál, Avishay Tal, Adrian Trejo Nuñez:
Cubic Formula Size Lower Bounds Based on Compositions with Majority. ITCS 2019: 35:1-35:13 - [c22]Ran Raz, Avishay Tal:
Oracle separation of BQP and PH. STOC 2019: 13-23 - [c21]Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal:
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC 2019: 515-526 - [c20]Raghu Meka, Omer Reingold, Avishay Tal:
Pseudorandom generators for width-3 branching programs. STOC 2019: 626-637 - [c19]Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal:
On the Computational Power of Radio Channels. DISC 2019: 8:1-8:17 - [i36]Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal:
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. CoRR abs/1906.08890 (2019) - [i35]Uma Girish, Ran Raz, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. CoRR abs/1911.02218 (2019) - [i34]Avishay Tal:
Towards Optimal Separations between Quantum and Randomized Query Complexities. CoRR abs/1912.12561 (2019) - [i33]Sumegha Garg, Ran Raz, Avishay Tal:
Time-Space Lower Bounds for Two-Pass Learning. Electron. Colloquium Comput. Complex. TR19 (2019) - [i32]Uma Girish, Ran Raz, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. Electron. Colloquium Comput. Complex. TR19 (2019) - [i31]Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal:
AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. TR19 (2019) - [i30]Avishay Tal:
Towards Optimal Separations between Quantum and Randomized Query Complexities. Electron. Colloquium Comput. Complex. TR19 (2019) - [i29]Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal:
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j7]Oded Goldreich, Avishay Tal:
Matrix rigidity of random Toeplitz matrices. Comput. Complex. 27(2): 305-350 (2018) - [j6]Or Meir, Avishay Tal:
The choice and agreement problems of a random function. Inf. Process. Lett. 133: 16-20 (2018) - [c18]Pooya Hatami, Avishay Tal:
Pseudorandom Generators for Low Sensitivity Functions. ITCS 2018: 29:1-29:13 - [c17]Shachar Lovett, Avishay Tal, Jiapeng Zhang:
The Robust Sensitivity of Boolean Functions. SODA 2018: 1822-1833 - [c16]Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal:
Improved pseudorandomness for unordered branching programs through local monotonicity. STOC 2018: 363-375 - [c15]Sumegha Garg, Ran Raz, Avishay Tal:
Extractor-based time-space lower bounds for learning. STOC 2018: 990-1002 - [i28]Raghu Meka, Omer Reingold, Avishay Tal:
Pseudorandom Generators for Width-3 Branching Programs. CoRR abs/1806.04256 (2018) - [i27]Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal:
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. Electron. Colloquium Comput. Complex. TR18 (2018) - [i26]Anna Gál, Avishay Tal, Adrian Trejo Nuñez:
Cubic Formula Size Lower Bounds Based on Compositions with Majority. Electron. Colloquium Comput. Complex. TR18 (2018) - [i25]Raghu Meka, Omer Reingold, Avishay Tal:
Pseudorandom Generators for Width-3 Branching Programs. Electron. Colloquium Comput. Complex. TR18 (2018) - [i24]Ran Raz, Avishay Tal:
Oracle Separation of BQP and PH. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j5]Amir Shpilka, Avishay Tal, Ben lee Volk:
On the Structure of Boolean Functions with Small Spectral Norm. Comput. Complex. 26(1): 229-273 (2017) - [j4]Gil Cohen, Amir Shpilka, Avishay Tal:
On the degree of univariate polynomials over the integers. Comb. 37(3): 419-464 (2017) - [j3]Ilan Komargodski, Ran Raz, Avishay Tal:
Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound. SIAM J. Comput. 46(1): 37-57 (2017) - [c14]Arnab Bhattacharyya, Sivakanth Gopi, Avishay Tal:
Lower Bounds for 2-Query LCCs over Large Alphabet. APPROX-RANDOM 2017: 30:1-30:20 - [c13]Avishay Tal:
Tight Bounds on the Fourier Spectrum of AC0. CCC 2017: 15:1-15:31 - [c12]Shalev Ben-David, Pooya Hatami, Avishay Tal:
Low-Sensitivity Functions from Unambiguous Certificates. ITCS 2017: 28:1-28:23 - [c11]Gillat Kol, Ran Raz, Avishay Tal:
Time-space hardness of learning sparse parities. STOC 2017: 1067-1080 - [c10]Avishay Tal:
Formula lower bounds via the quantum method. STOC 2017: 1256-1268 - [i23]Sumegha Garg, Ran Raz, Avishay Tal:
Extractor-Based Time-Space Lower Bounds for Learning. CoRR abs/1708.02639 (2017) - [i22]Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal:
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. Electron. Colloquium Comput. Complex. TR17 (2017) - [i21]Sumegha Garg, Ran Raz, Avishay Tal:
Extractor-Based Time-Space Lower Bounds for Learning. Electron. Colloquium Comput. Complex. TR17 (2017) - [i20]Oded Goldreich, Avishay Tal:
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - [i19]Pooya Hatami, Avishay Tal:
Pseudorandom Generators for Low-Sensitivity Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - [i18]Or Meir, Avishay Tal:
The Choice and Agreement Problems of a Random Function. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j2]Raghav Kulkarni, Avishay Tal:
On Fractional Block Sensitivity. Chic. J. Theor. Comput. Sci. 2016 (2016) - [c9]Avishay Tal:
On the Sensitivity Conjecture. ICALP 2016: 38:1-38:13 - [c8]Oded Goldreich, Avishay Tal:
Matrix rigidity of random toeplitz matrices. STOC 2016: 91-104 - [i17]Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson:
Degree and Sensitivity: tails of two distributions. CoRR abs/1604.07432 (2016) - [i16]Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson:
Degree and Sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex. TR16 (2016) - [i15]Gillat Kol, Ran Raz, Avishay Tal:
Time-Space Hardness of Learning Sparse Parities. Electron. Colloquium Comput. Complex. TR16 (2016) - [i14]Avishay Tal:
On The Sensitivity Conjecture. Electron. Colloquium Comput. Complex. TR16 (2016) - [i13]Avishay Tal:
Computing Requires Larger Formulas than Approximating. Electron. Colloquium Comput. Complex. TR16 (2016) - [i12]Avishay Tal:
The Bipartite Formula Complexity of Inner-Product is Quadratic. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c7]Gil Cohen, Avishay Tal:
Two Structural Results for Low Degree Polynomials and Applications. APPROX-RANDOM 2015: 680-709 - [i11]Oded Goldreich, Avishay Tal:
Matrix Rigidity of Random Toeplitz Matrices. Electron. Colloquium Comput. Complex. TR15 (2015) - [i10]Avishay Tal:
#SAT Algorithms from Shrinkage. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j1]Amir Shpilka, Avishay Tal:
On the minimal fourier degree of symmetric Boolean functions. Comb. 34(3): 359-377 (2014) - [c6]Avishay Tal:
Shrinkage of De Morgan Formulae by Spectral Techniques. FOCS 2014: 551-560 - [c5]Amir Shpilka, Avishay Tal, Ben lee Volk:
On the structure of boolean functions with small spectral norm. ITCS 2014: 37-48 - [i9]Gil Cohen, Avishay Tal:
Two Structural Results for Low Degree Polynomials and Applications. CoRR abs/1404.0654 (2014) - [i8]Avishay Tal:
Shrinkage of De Morgan Formulae from Quantum Query Complexity. Electron. Colloquium Comput. Complex. TR14 (2014) - [i7]Avishay Tal:
Tight bounds on The Fourier Spectrum of AC0. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c4]Ilan Komargodski, Ran Raz, Avishay Tal:
Improved Average-Case Lower Bounds for DeMorgan Formula Size. FOCS 2013: 588-597 - [c3]Avishay Tal:
Properties and applications of boolean function composition. ITCS 2013: 441-454 - [i6]Gil Cohen, Avishay Tal:
Two Structural Results for Low Degree Polynomials and Applications. Electron. Colloquium Comput. Complex. TR13 (2013) - [i5]Ilan Komargodski, Ran Raz, Avishay Tal:
Improved Average-Case Lower Bounds for DeMorgan Formula Size. Electron. Colloquium Comput. Complex. TR13 (2013) - [i4]Raghav Kulkarni, Avishay Tal:
On Fractional Block Sensitivity. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [c2]Gil Cohen, Amir Shpilka, Avishay Tal:
On the degree of univariate polynomials over the integers. ITCS 2012: 409-427 - [i3]Avishay Tal:
Properties and Applications of Boolean Function Composition. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c1]Amir Shpilka, Avishay Tal:
On the Minimal Fourier Degree of Symmetric Boolean Functions. CCC 2011: 200-209 - [i2]Gil Cohen, Amir Shpilka, Avishay Tal:
On the Degree of Univariate Polynomials Over the Integers. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i1]Amir Shpilka, Avishay Tal:
On the Minimal Fourier Degree of Symmetric Boolean Functions. Electron. Colloquium Comput. Complex. TR10 (2010)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 20:24 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
