Polynomial query complexity for permutation property testing
AX_permutation_property_testing_query_bounds
Source: arXiv:1611.01270 — Fast property testing and metrics for permutations
Open Problem (better query complexity bounds for property testing) · arXiv:1611.01270
Diagnostic tag ill-posed high confidence
The catalog item is a research programme rather than a quantified conjecture; moreover, one natural universal Kendall-tau formulation is false in the canonical sampling model.
Caveat. The negative result below concerns property-independent canonical induced-subpermutation testers, not fixed-property polynomial bounds or adaptive value-query models.
Attack verdicts are unrefereed model self-reports. An ill-posed label is a diagnostic of the catalog statement supplied to the model, not a literature-review status or a peer-reviewed result.
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