Existing poly(d ε^{-1})-query partition oracles for minor-closed bounded-degree graphs can be implemented with poly(d ε^{-1}) log n random bits; any such oracle for cycles requires ω(1) bits when vertices have labels from [N] with N ≥ n.
Distribution testing under the parity trace
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
Presents an algorithm for support size testing using O(n/(ε log n) log(1/ε)) samples that nearly matches the Ω(n/(ε log n)) lower bound and improves on histogram learning.
citing papers explorer
-
Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
Existing poly(d ε^{-1})-query partition oracles for minor-closed bounded-degree graphs can be implemented with poly(d ε^{-1}) log n random bits; any such oracle for cycles requires ω(1) bits when vertices have labels from [N] with N ≥ n.
-
Testing Support Size More Efficiently Than Learning Histograms
Presents an algorithm for support size testing using O(n/(ε log n) log(1/ε)) samples that nearly matches the Ω(n/(ε log n)) lower bound and improves on histogram learning.