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

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…