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

3 papers · 2 filters

cs.CC2017

Adaptivity is exponentially powerful for testing monotonicity of halfspaces

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

We give a $poly (lo g n, 1/ ε)$ -query adaptive algorithm for testing whether an unknown Boolean function $f : {- 1, 1}^{n} \to {- 1, 1}$ , which is promised to be a halfspace, i…

cs.CC2017★ 1 cited

Settling the query complexity of non-adaptive junta testing

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

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function $f : {0, 1}^{n} \to {0, 1}$ is a $k$ -junta or $ε$ -far from every $k$ -junta must make $\widet…

cs.CC2017★ 1 cited

Fooling intersections of low-weight halfspaces

Rocco A. Servedio, Li-Yang Tan

A weight- $t$ halfspace is a Boolean function $f (x) =$ sign $(w_{1} x_{1} + \dots + w_{n} x_{n} - θ)$ where each $w_{i}$ is an integer in ${- t, \dots, t} .$ We give an explicit pseudorandom gene…