The search functionality is under construction.

The search functionality is under construction.

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

- 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

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 -