k-Approximating Circuits

IEEE Transactions on Computers

In this paper we investigate the problem of, given a circuit representing a bool ean function, analyzing the circuit accepting all inputs of the original circuit plus all points whose Hamming distance from the previous set is at most k. In particular, we investigate whether its size increases exponentially with k.

 @article{cado-etal-06-c,
 title = {k-Approximating Circuits},
 year = {2006},
 author = {Cadoli, Marco and Donini, Francesco M. and Liberatore, Paolo and
 Schaerf, Marco},
 journal = {IEEE Transactions on Computers},
 pages = {913-917},
 number = {7},
 volume = {55},
 }