| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
k-Approximating Circuits
July 2006 (vol. 55 no. 7)
pp. 913-917
In this paper, we define and study the k-approximating circuits. A circuit accepting a given set of inputs A is k-approximated by accepting inputs that differ from one of A by at most k bits. We show that the existence of polynomial-size k-approximating circuits depends on the relation between k and the number of inputs.
[1] 913 S. Arora, L. Babai, J. Stern, and Z. Sweedyk, “The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations,” J. Computer and System Sciences, vol. 54, pp. 317-331, 1997.[2] E. Berlekamp, R. McEliece, and H. van Tilborg, “On the Inherent Intractability of Certain Coding Problems,” IEEE Trans. Information Theory, vol. 24, pp. 384-386, 1978.[3] R. Boppana and M. Sipser, “The Complexity of Finite Functions,” Handbook of Theoretical Computer Science, J. van Leeuwen, ed., vol. A, chapter 14, pp. 757-804, Amsterdam: Elsevier Science Publishers, 1990.[4] M. Cadoli, F.M. Donini, P. Liberatore, and M. Schaerf, “Space Efficiency of Propositional Knowledge Representation Formalisms,” J. Artificial Intelligence Research, vol. 13, pp. 1-31, 2000.[5] M. Cadoli, F.M. Donini, P. Liberatore, and M. Schaerf, “Preprocessing of Intractable Problems,” Information and Computation, vol. 176, no. 2, pp. 89-120, 2002.[6] R. Downey, M. Fellows, A. Vardy, and G. Whittle, “The Parameterized Complexity of Some Fundamental Problems in Coding Theory,” SIAM J. Computing, vol. 29, no. 2, pp. 545-570, 1999.[7] I. Dumer, D. Micciancio, and M. Sudan, “Hardness of Approximating the Minimum Distance of a Linear Code,” IEEE Trans. Information Theory, vol. 49, pp. 22-37, 2003.[8] I. Eidhammer, I. Jonassen, S. Grindhaug, D. Gilbert, and M. Ratnayake, “A Constraint Based Structure Description Language for Biosequences,” Constraints, vol. 6, pp. 173-200, 2001.[9] H. Chen, “Parameterized Compilability,” Proc. 19th Int'l Joint Conf. Artificial Intelligence (IJCAI 2005), 2005.[10] D.S. Johnson, “A Catalog of Complexity Classes,” Handbook of Theoretical Computer Science, J. van Leeuwen, ed., vol. A, chapter 2, pp. 67-161, Amsterdam: Elsevier Science Publishers, 1990.[11] V. Levenshtein, “Binary Codes Capable of Correcting Deletions, Insertions, and Reversals,” Soviet Physics Doklady, vol. 10, 1966.[12] B. Manthey and R. Reischuk, “The Intractability of Computing the Hamming Distance,” Theoretical Computer Science, vol. 337, pp. 331-346, 2005.[13] G. Mehldau and G. Myers, “A System for Pattern Matching Applications on Biosequences,” Computer Applications in the Biosciences, vol. 9, pp. 299-314, 1993.[14] P. Penna, “Succinct Representations of Model Based Belief Revision,” Proc. 17th Ann. Symp. Theoretical Aspects of Computer Science (STACS 2000), pp. 205-216, 2000.[15] G. Pighizzini, “How Hard Is Computing the Edit Distance?” Information and Computation, vol. 165, pp. 1-13, 2001.[16] N. Pippenger, “Information Theory and the Complexity of Boolean Functions,” Math. Systems Theory, vol. 10, pp. 129-167, 1977.[17] A. Prasad Sistla, T. Hu, and V. Chowdhry, “Similarity Based Retrieval from Sequence Databases Using Automata As Queries,” Proc. 2002 ACM CIKM Int'l Conf. Information and Knowledge Management, pp. 237-244, 2002.[18] J. Stern, “A New Paradigm for Public Key Identification,” IEEE Trans. Information Theory, vol. 42, pp. 1757-1768, 1996.
Index Terms:
Reliability and testing, complexity measures and classes, models of computation.
Citation:
Marco Cadoli, Francesco M. Donini, Paolo Liberatore, Marco Schaerf, "k-Approximating Circuits," IEEE Transactions on Computers, vol. 55, no. 7, pp. 913-917, July 2006, doi:10.1109/TC.2006.105
