Publications (24)
An inequality for the Fourier spectrum of parity decision trees
Eric Blais, Li-Yang Tan, Andrew Wan
Learning circuits with few negations
Eric Blais, Clément L. Canonne, Igor C. Oliveira +2
Adaptivity is exponentially powerful for testing monotonicity of halfspaces
Xi Chen, Rocco A. Servedio, Li-Yang Tan +1
Settling the query complexity of non-adaptive junta testing
Xi Chen, Rocco A. Servedio, Li-Yang Tan +2
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan +1
Approximate resilience, monotonicity, and the complexity of agnostic learning
Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan +2
Analysis of Boolean Functions
Li-Yang Tan
Deterministic search for CNF satisfying assignments in almost polynomial time
Rocco A. Servedio, Li-Yang Tan
Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, Siyao Guo +2
On the Distribution of the Fourier Spectrum of Halfspaces
Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio +2
A composition theorem for parity kill number
Ryan O'Donnell, Xiaorui Sun, Li-Yang Tan +2
A composition theorem for the Fourier Entropy-Influence conjecture
Ryan O'Donnell, Li-Yang Tan
Fooling Polytopes
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries
Xi Chen, Anindya De, Rocco A. Servedio +1
Improved pseudorandom generators from pseudorandom multi-switching lemmas
Rocco A. Servedio, Li-Yang Tan
Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
Itai Benjamini, Siu-On Chan, Ryan O'Donnell +2
Fooling intersections of low-weight halfspaces
Rocco A. Servedio, Li-Yang Tan
New algorithms and lower bounds for monotonicity testing
Xi Chen, Rocco A. Servedio, Li-Yang Tan
Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
Manuel Kauers, Ryan O'Donnell, Li-Yang Tan +1
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, Li-Yang Tan +1
Luby--VeliÄkoviÄ--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
Rocco A. Servedio, Li-Yang Tan
An average-case depth hierarchy theorem for Boolean circuits
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
Average sensitivity and noise sensitivity of polynomial threshold functions
Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio +1
Near-optimal small-depth lower bounds for small distance connectivity
Xi Chen, Igor C. Oliveira, Rocco A. Servedio +1