I. Oliveira

activity

20132023

most citedUnprovability of circuit upper bounds in Cook's theory PV

30 citations · 61 across the 15 of their papers we have counts for

collaborators

Showing 2015Show all

2 papers · 1 filter

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…