Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with boolan functions:
TR02-067 | 5th October 2002
Marco Cadoli, Francesco Donini, Paolo Liberatore, Marco Schaerf

k-Approximating Circuits

In this paper we study the problem of approximating a boolean
function using the Hamming distance as the approximation measure.
Namely, given a boolean function f, its k-approximation is the
function f^k returning true on the same points in which f does,
plus all points whose Hamming distance from the ... more >>>

TR18-005 | 9th January 2018
C. Seshadhri, Deeparnab Chakrabarty

Adaptive Boolean Monotonicity Testing in Total Influence Time

The problem of testing monotonicity
of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention
recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester
of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence
of $f$. We give an adaptive tester whose running ... more >>>

ISSN 1433-8092 | Imprint