Rethinking lipschitz neural networks and certified robustness: A boolean function perspective
Designing neural networks with bounded Lipschitz constant is a promising way to obtain
certifiably robust classifiers against adversarial examples. However, the relevant progress …
certifiably robust classifiers against adversarial examples. However, the relevant progress …
[图书][B] Boolean function complexity: advances and frontiers
S Jukna - 2012 - Springer
Boolean circuit complexity is the combinatorics of computer science and involves many
intriguing problems that are easy to state and explain, even for the layman. This book is a …
intriguing problems that are easy to state and explain, even for the layman. This book is a …
Tight bounds on the Fourier spectrum of AC0
A Tal - 32nd Computational Complexity Conference (CCC …, 2017 - drops.dagstuhl.de
We show that AC^ 0 circuits on n variables with depth d and size m have at most 2^{-Omega
(k/log^{d-1} m)} of their Fourier mass at level k or above. Our proof builds on a previous …
(k/log^{d-1} m)} of their Fourier mass at level k or above. Our proof builds on a previous …
A polynomial lower bound for testing monotonicity
We show that every algorithm for testing n-variate Boolean functions for monotonicityhas
query complexity Ω (n 1/4). All previous lower bounds for this problem were designed for …
query complexity Ω (n 1/4). All previous lower bounds for this problem were designed for …
The coin problem and pseudorandomness for branching programs
J Brody, E Verbin - 2010 IEEE 51st Annual Symposium on …, 2010 - ieeexplore.ieee.org
The Coin Problem is the following problem: a coin is given, which lands on head with
probability either 1/2+ β or 1/2-β. We are given the outcome of n independent tosses of this …
probability either 1/2+ β or 1/2-β. We are given the outcome of n independent tosses of this …
Lower bounds for convexity testing
We consider the problem of testing whether an unknown and arbitrary set S⊆ ℝ n (given as
a black-box membership oracle) is convex, versus ε-far from every convex set, under the …
a black-box membership oracle) is convex, versus ε-far from every convex set, under the …
An average-case depth hierarchy theorem for boolean circuits
B Rossman, RA Servedio… - 2015 IEEE 56th Annual …, 2015 - ieeexplore.ieee.org
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard
basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d≥ 2, there is …
basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d≥ 2, there is …
Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas
We give the first super-polynomial (in fact, mildly exponential) lower bounds for tolerant
testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a …
testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a …
Gaussian approximation of convex sets by intersections of halfspaces
A De, S Nadimpalli, RA Servedio - 2024 IEEE 65th Annual …, 2024 - ieeexplore.ieee.org
We study the approximability of general convex sets in R^n by intersections of halfspaces,
where the approximation quality is measured with respect to the standard Gaussian …
where the approximation quality is measured with respect to the standard Gaussian …
An average-case depth hierarchy theorem for boolean circuits
J Håstad, B Rossman, RA Servedio… - Journal of the ACM (JACM), 2017 - dl.acm.org
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard
basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d≥ 2, there is …
basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d≥ 2, there is …