Query-Number Preserving Reductions and Linear Lower Bounds for Testing

Yuichi YOSHIDA  Hiro ITO  

IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.2   pp.233-240
Publication Date: 2010/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.233
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
property testing,  lower bounds,  

Full Text: PDF(289.1KB)>>
Buy this Article

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.