Li-Yang Tan

activity

20092023

most citedConvergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs

37 citations · 101 across the 43 of their papers we have counts for

collaborators

Showing 2015Show all

3 papers · 1 filter

cs.CC2015

Near-optimal small-depth lower bounds for small distance connectivity

Xi Chen, Igor C. Oliveira, Rocco A. Servedio +1

We show that any depth- $d$ circuit for determining whether an $n$ -node graph has an $s$ -to- $t$ path of length at most $k$ must have size $n^{Ω (k^{1/ d} / d)}$ . The previous best circu…

cs.DM2015

An inequality for the Fourier spectrum of parity decision trees

Eric Blais, Li-Yang Tan, Andrew Wan

We give a new bound on the sum of the linear Fourier coefficients of a Boolean function in terms of its parity decision tree complexity. This result generalizes an inequality of O'…

cs.CC2015

An average-case depth hierarchy theorem for Boolean circuits

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of $AND$ , $OR$ , and $NOT$ gates. Our hierarchy theorem says…