A basic lower bound for property testing

Eldar Fischer

A basic lower bound for property testing

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2403.04999 v2 pith:4RYZCCTX submitted 2024-03-08 cs.DS

Eldar Fischer This is my paper · ORCID

classification cs.DS

keywords propertyepsiloninputsknowledgeprooftherebasicbest

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

abstract

An $\epsilon$-test for any non-trivial property (one for which there are both satisfying inputs and inputs of large distance from the property) should use a number of queries that is at least inversely proportional in $\epsilon$. However, to the best of our knowledge there is no reference proof for this intuition. Such a proof is provided here. It is written so as to not require any prior knowledge of the related literature, and in particular does not use Yao's method.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On Optimal Testing of Linearity
cs.CC 2024-11 conditional novelty 7.0 of 10

Near-optimal query bounds for linearity testing under online adversarial corruptions, and an O(1/ε) query tester for real-valued linearity, improving prior O(1/ε log(1/ε)) bounds.

Pith tools