72 citations · 399 across the 60 of their papers we have counts for
4 papers · 1 filter
Near-optimal small-depth lower bounds for small distance connectivity
Xi Chen, Igor C. Oliveira, Rocco A. Servedio +1
We show that any depth- circuit for determining whether an -node graph has an -to- path of length at most must have size . The previous best circu…
Addition is exponentially harder than counting for shallow monotone circuits
Xi Chen, Igor C. Oliveira, Rocco A. Servedio
Let denote the Boolean function which takes as input strings of bits each, representing numbers in , and output…
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Parikshit Gopalan, Noam Nisan, Rocco A. Servedio +2
A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure…
An average-case depth hierarchy theorem for Boolean circuits
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of , , and gates. Our hierarchy theorem says…