Difference between revisions of "Open Problems:38"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |title=Query Complexity of Local Partitioning Oracles |source=bertinoro11 |who=Krzysztof Onak }} A local partitioning oracle is defined in the paper of Hassidim, Keln...")
 
(Progress update)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Query Complexity of Local Partitioning Oracles
 
 
|source=bertinoro11
 
|source=bertinoro11
 
|who=Krzysztof Onak
 
|who=Krzysztof Onak
Line 9: Line 8:
  
 
'''Question:''' Can one design an oracle that makes only $\operatorname{poly}(d/\epsilon)$ queries? If so, then among other things, this would lead to a tester for planarity in the bounded-degree model that makes only $\operatorname{poly}(1/\epsilon)$ queries, resolving an open question of Benjamini et al. {{cite|BenjaminiSS-08}}.
 
'''Question:''' Can one design an oracle that makes only $\operatorname{poly}(d/\epsilon)$ queries? If so, then among other things, this would lead to a tester for planarity in the bounded-degree model that makes only $\operatorname{poly}(1/\epsilon)$ queries, resolving an open question of Benjamini et al. {{cite|BenjaminiSS-08}}.
 +
 +
== Update ==
 +
Levi and Ron {{cite|LeviR-13}} showed a partitioning oracle for bounded-degree minor-free graphs that makes only $(d/\epsilon)^{O(\log(1/\epsilon))}$ queries to the input graph for each query about the partition.

Latest revision as of 14:58, 12 March 2013

Suggested by Krzysztof Onak
Source Bertinoro 2011
Short link https://sublinear.info/38

A local partitioning oracle is defined in the paper of Hassidim, Kelner, Nguyen, and Onak [HassidimKNO-09], and an implicit construction of a partitioning oracle is shown in the earlier paper of Benjamini, Schramm, and Shapira [BenjaminiSS-08]. Partitioning oracles are a useful abstraction for approximation and testing algorithms in the bounded degree model.

The best known oracle for bounded-degree planar graphs makes at most $d^{\operatorname{poly}(1/\epsilon)}$ queries to the underlying graph to answer each query about the resulting partition, where $d$ is the bound on the maximum vertex degree in the graph. See [Onak-10] for a description of the method.

Question: Can one design an oracle that makes only $\operatorname{poly}(d/\epsilon)$ queries? If so, then among other things, this would lead to a tester for planarity in the bounded-degree model that makes only $\operatorname{poly}(1/\epsilon)$ queries, resolving an open question of Benjamini et al. [BenjaminiSS-08].

Update[edit]

Levi and Ron [LeviR-13] showed a partitioning oracle for bounded-degree minor-free graphs that makes only $(d/\epsilon)^{O(\log(1/\epsilon))}$ queries to the input graph for each query about the partition.