papers
Publications (8)
cs.CC2018
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, Avishay Tal
cs.CC2016
Degree and Sensitivity: tails of two distributions
Parikshit Gopalan, Rocco Servedio, Avishay Tal +1
cs.CC2017
Low-Sensitivity Functions from Unambiguous Certificates
Shalev Ben-David, Pooya Hatami, Avishay Tal
cs.CC2013
On the Structure of Boolean Functions with Small Spectral Norm
Amir Shpilka, Avishay Tal, Ben lee Volk
quant-ph2019
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer +1
cs.LG2017
Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, Avishay Tal
cs.CC2017
Lower bounds for 2-query LCCs over large alphabet
Arnab Bhattacharyya, Sivakanth Gopi, Avishay Tal
cs.CC2014
Two Structural Results for Low Degree Polynomials and Applications
Gil Cohen, Avishay Tal