Polynomial Property Testing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909750744055808 |
|---|---|
| author | Gishboliner, Lior Shapira, Asaf |
| author_facet | Gishboliner, Lior Shapira, Asaf |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16878 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial Property Testing Gishboliner, Lior Shapira, Asaf Data Structures and Algorithms Combinatorics 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. |
| title | Polynomial Property Testing |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2508.16878 |