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

3 papers · 2 filters

cs.CC2014★ 2 cited

Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries

Xi Chen, Anindya De, Rocco A. Servedio +1

We prove a lower bound of $Ω (n^{1/2 - c})$ , for all $c > 0$ , on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an $n$ -variable Boolean function…

cs.CC2014★ 22 cited

New algorithms and lower bounds for monotonicity testing

Xi Chen, Rocco A. Servedio, Li-Yang Tan

We consider the problem of testing whether an unknown Boolean function $f$ is monotone versus $ε$ -far from every monotone function. The two main results of this paper are a new low…

cs.CC2014

Learning circuits with few negations

Eric Blais, Clément L. Canonne, Igor C. Oliveira +2

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean…

Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries

New algorithms and lower bounds for monotonicity testing

Learning circuits with few negations

Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries