## k-Approximating Circuits

**Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and
Marco Schaerf**
*Technical Report, Electronic Colloquium on Computational
Complexity*

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 fk returning true on the same points in which f does,
plus all points whose Hamming distance from the previous set is
at most k. We investigate whether k-approximation generates an
exponential increase in size or not, when functions are
represented as circuits. We also briefly investigate the
increase in the size of the circuit for other forms of
approximation.

@techreport{cado-etal-02-b,
title = {k-Approximating Circuits},
year = {2002},
author = {Cadoli, Marco and Donini, Francesco M. and Liberatore,
Paolo and Schaerf, Marco},
institution = {Electronic Colloquium on Computational
Complexity},
number = {TR02-067},
}

FTP
download.