R. Servedio

activity

20002023

most citedImproved Bounds on Quantum Learning Algorithms

72 citations · 399 across the 60 of their papers we have counts for

collaborators

Showing 2014 · cs.CCShow all

3 papers · 2 filters

cs.CC2014★ 2 cited

Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries

Xi Chen, Anindya De, Rocco A. Servedio +1

We prove a lower bound of $Ω (n^{1/2 - c})$ , for all $c > 0$ , on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an $n$ -variable Boolean function…

cs.CC2014★ 22 cited

New algorithms and lower bounds for monotonicity testing

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

We consider the problem of testing whether an unknown Boolean function $f$ is monotone versus $ε$ -far from every monotone function. The two main results of this paper are a new low…

cs.CC2014

Learning circuits with few negations

Eric Blais, Clément L. Canonne, Igor C. Oliveira +2

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean…

Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries

New algorithms and lower bounds for monotonicity testing

Learning circuits with few negations

Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries