Properties constant-query testable classically in the bidirectional bounded-degree directed graph model admit n^{1/2 - Ω(1)} quantum query testers in the unidirectional model, with an almost-matching lower bound.
[Fis24] Eldar Fischer
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
years
2026 3verdicts
UNVERDICTED 3roles
background 1polarities
background 1representative citing papers
Presents a tester for abelian group property testing in the PS-model with time Õ(√|G| + 1/ε), improving on prior linear-time testers.
k-juntas, low-degree Fourier functions, and sparse polynomials are testable with O(1/ε) queries independent of n for small ε.
citing papers explorer
-
Quantum Property Testing for Bounded-Degree Directed Graphs
Properties constant-query testable classically in the bidirectional bounded-degree directed graph model admit n^{1/2 - Ω(1)} quantum query testers in the unidirectional model, with an almost-matching lower bound.
-
Sublinear Time Algorithms for Abelian Group Property Testing
Presents a tester for abelian group property testing in the PS-model with time Õ(√|G| + 1/ε), improving on prior linear-time testers.
-
Classes Testable with $O(1/\epsilon)$ Queries for Small $\epsilon$ Independent of the Number of Variables
k-juntas, low-degree Fourier functions, and sparse polynomials are testable with O(1/ε) queries independent of n for small ε.