Xi Chen

activity

20092023

most citedNew algorithms and lower bounds for monotonicity testing

22 citations · 115 across the 31 of their papers we have counts for

collaborators

Showing 2015Show all

3 papers · 1 filter

cs.DM2015★ 9 cited

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

Xi Chen, Jinyu Xie

We improve both upper and lower bounds for the distribution-free testing of monotone conjunctions. Given oracle access to an unknown Boolean function $f:\{0,1\}^n \rightarrow \{0,1…

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

Addition is exponentially harder than counting for shallow monotone circuits

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

Let $U_{k, N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)}, \dots, a^{(k)}$ in ${0, 1, \dots, 2^{N} - 1}$ , and output…