ECCC-Report TR02-067https://eccc.weizmann.ac.il/report/2002/067Comments and Revisions published for TR02-067en-usTue, 10 Dec 2002 19:39:15 +0200
Paper TR02-067
| k-Approximating Circuits |
Marco Cadoli,
Francesco Donini,
Paolo Liberatore,
Marco Schaerf
https://eccc.weizmann.ac.il/report/2002/067In 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 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.
Tue, 10 Dec 2002 19:39:15 +0200https://eccc.weizmann.ac.il/report/2002/067