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 copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yuichi YOSHIDA, Hiro ITO, "Query-Number Preserving Reductions and Linear Lower Bounds for Testing" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 2, pp. 233-240, February 2010, doi: 10.1587/transinf.E93.D.233.
Abstract: 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
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.233/_p
Copy
@ARTICLE{e93-d_2_233,
author={Yuichi YOSHIDA, Hiro ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Query-Number Preserving Reductions and Linear Lower Bounds for Testing},
year={2010},
volume={E93-D},
number={2},
pages={233-240},
abstract={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
keywords={},
doi={10.1587/transinf.E93.D.233},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Query-Number Preserving Reductions and Linear Lower Bounds for Testing
T2 - IEICE TRANSACTIONS on Information
SP - 233
EP - 240
AU - Yuichi YOSHIDA
AU - Hiro ITO
PY - 2010
DO - 10.1587/transinf.E93.D.233
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2010
AB - 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
ER -