Tal, Avishay
- Quantum Cryptography in Algorithmica
2022/12/01 by Kretschmer, William, Qian, Luowen, Sinha, Makrand +1 · 6 citations
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
- Degree vs. Approximate Degree and Quantum Implications of Huang's\n Sensitivity Theorem
2020/10/23 by Scott Aaronson, Shalev Ben-David, Aaronson, Scott +7 · 4 citations
Computer Science · #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Complexity and Algorithms in Graphs
- Quantum versus Randomized Communication Complexity, with Efficient Players
2019/11/06 by Girish, Uma, Raz, Ran, Tal, Avishay · 3 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
- Pseudorandom Generators for Width-3 Branching Programs
2018/06/11 by Meka, Raghu, Reingold, Omer, Tal, Avishay · 2 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
- Towards Optimal Separations between Quantum and Randomized Query\n Complexities
2019/12/28 by Avishay Tal, Tal, Avishay · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
- Quantum-Computable One-Way Functions without One-Way Functions
2024/11/04 by Kretschmer, William, Qian, Luowen, Tal, Avishay · 6 citations
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
- On Certified Randomness from Fourier Sampling or Random Circuit Sampling
2021/11/29 by Bassirian, Roozbeh, Bouland, Adam, Fefferman, Bill +2 · 2 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)
- Junta Distance Approximation with Sub-Exponential Queries
2021/06/01 by Iyer, Vishnu, Tal, Avishay, Whitmeyer, Michael · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
- Lower bounds for 2-query LCCs over large alphabet
2016/11/21 by Bhattacharyya, Arnab, Gopi, Sivakanth, Tal, Avishay · 1 citation
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
- The Power of Adaptivity in Quantum Query Algorithms
2023/11/27 by Uma Girish, Girish, Uma, Makrand Sinha +5 · 3 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum and electron transport phenomena
- Tight Time-Space Lower Bounds for Constant-Pass Learning
2023/10/12 by Xin Lyu, Avishay Tal, Lyu, Xin +5 · 1 citation
Computer Science · #Machine Learning and Algorithms #Optimization and Search Problems #Imbalanced Data Classification Techniques
- Improved Lower Bounds for QAC0
2025/12/16 by Malvika Raj Joshi, Joshi, Malvika Raj, Avishay Tal +5 · 1 voice · 2 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Complexity and Algorithms in Graphs #Advanced Graph Theory Research