The search functionality is under construction.
The search functionality is under construction.

Query-Number Preserving Reductions and Linear Lower Bounds for Testing

Yuichi YOSHIDA, Hiro ITO

  • Full Text Views

    0

  • Cite this

Summary :

In this paper, we study lower bounds on the query complexity of testing algorithms for various problems. Given an oracle that returns information of an input object, a testing algorithm distinguishes the case that the object has a given property P from the case that it has a large distance to having P with probability at least . The query complexity of an algorithm is measured by the number of accesses to the oracle. We introduce two reductions that preserve the query complexity. One is derived from the gap-preserving local reduction and the other is from the L-reduction. By using the former reduction, we show linear lower bounds on the query complexity for testing basic NP-complete properties, i.e., 3-edge-colorability, directed Hamiltonian path/cycle, undirected Hamiltonian path/cycle, 3-dimensional matching and NP-complete generalized satisfiability problems. Also, using the second reduction, we show a linear lower bound on the query complexity of approximating the size of the maximum 3-dimensional matching.

Publication
IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.233-240
Publication Date
2010/02/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E93.D.233
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science)
Category

Authors

Keyword