37 citations · 101 across the 43 of their papers we have counts for
5 papers · 1 filter
Boolean function monotonicity testing requires (almost) non-adaptive queries
Xi Chen, Anindya De, Rocco A. Servedio +1
We prove a lower bound of , for all , on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an -variable Boolean function…
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 is monotone versus -far from every monotone function. The two main results of this paper are a new low…
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…
Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
Itai Benjamini, Siu-On Chan, Ryan O'Donnell +2
In majority dynamics, agents located at the vertices of an undirected simple graph update their binary opinions synchronously by adopting those of the majority of their neighbors.…
Approximate resilience, monotonicity, and the complexity of agnostic learning
Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan +2
A function is -resilient if all its Fourier coefficients of degree at most are zero, i.e., is uncorrelated with all low-degree parities. We study the notion of $\mat…