article · ArXiv.org · 2025

Polynomial Property Testing

Gishboliner, Lior, Shapira, Asaf

Cited by 0Open access

Abstract

Property testers are fast, randomized "election polling"-type algorithms that determine if an input (e.g., graph or hypergraph) has a certain property or is $\varepsilon$-far from the property. In the dense graph model of property testing, it is known that many properties can be tested with query complexity that depends only on the error parameter $\varepsilon$ (and not on the size of the input), but the current bounds on the query complexity grow extremely quickly as a function of $1/\varepsilon$. Which properties can be tested efficiently, i.e., with $\mathrm{poly}(1/\varepsilon)$ queries? This survey presents the state of knowledge on this general question, as well as some key open problems.

Cite this paper

APA 7

Gishboliner, L., & Shapira, A. (2025). Polynomial Property Testing. ArXiv.org.

MLA 9

Gishboliner, Lior, and Asaf Shapira. “Polynomial Property Testing.” ArXiv.org, 2025.

Chicago

Gishboliner, Lior, and Asaf Shapira. 2025. “Polynomial Property Testing.” ArXiv.org.

Harvard

Gishboliner, L. and Shapira, A. (2025) ‘Polynomial Property Testing’, ArXiv.org.

BibTeX

@article{gishboliner2025polynomial,
  title = {{Polynomial Property Testing}},
  author = {Gishboliner, Lior and Shapira, Asaf},
  journal = {ArXiv.org},
  year = {2025}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.