Polynomial query complexity for permutation property testing
Open Problem (better query complexity bounds for property testing) · arXiv:1611.01270
Status open medium confidence
Fox and Wei (arXiv:1611.01270) established a universal polynomial-in-1/ε query complexity bound for two-sided testing of hereditary permutation properties under rectangular distance, improving prior Ackermann-type bounds from Klimošová--Kráļ. The open problem asks whether similarly improved (polynomial or better) bounds hold for other metrics (e.g., Kendall's tau) and other testing regimes. A 2025 survey by Gishboliner and Shapira on polynomial property testing (arXiv:2508.16878) includes a section on permutations covering this area, but no paper found in the indexed literature definitively resolves the full open problem.
Cited literature (1)
-
A 2025 survey on polynomial property testing includes a dedicated section on permutations (Section 6) covering hereditary permutation property testing under Kendall's tau distance and citing Fox-Wei's polynomial bounds, situating the open problem in the broader landscape of which properties admit poly(1/ε) testers.
Reviewer notes. The open problem as stated is deliberately broad ('various property testing results'), making definitive resolution hard to pinpoint. Fox-Wei itself already established polynomial bounds for rectangular distance; the remaining question concerns other metrics and tighter bounds. The Gishboliner-Shapira 2025 survey (arXiv:2508.16878) covers this landscape but its full content on permutations was not accessible to verify whether it proves new results beyond surveying. No counterexample or full resolution was found.
Context
General results in combinatorial property testing show that natural properties can be tested with constant query complexity depending only on $\varepsilon$ and the property, but the upper bounds arising from proofs are often enormous: wowzer-type or Ackermann-type in $1/\varepsilon$, or established only via compactness with no explicit bound at all. The paper makes progress on this problem for permutations by establishing a universal polynomial-in-$1/\varepsilon$ query complexity bound for two-sided testing of hereditary properties with respect to the rectangular distance.
Notes. PDF source — paper text is truncated (ends mid-sentence in the introduction); this open problem is presented as a known community-level motivation rather than a fresh conjecture introduced by the paper's authors. No formal labelled environment. Any conjectures or questions posed in later sections of the paper are not visible in the supplied extract.
Source paper
Fast property testing and metrics for permutations
Jacob Fox, Fan Wei · 2018-04-04
https://arxiv.org/abs/1611.01270
PDF source