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 2015 · cs.CCShow all

2 papers · 2 filters

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.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…