Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOOLAN FUNCTIONS:
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
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 >>>