k-Approximating Circuits

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},
 }