Open Problems:38 - Revision history

Krzysztof Onak: Progress update

2013-03-12T14:58:33Z

Progress update

Krzysztof Onak: updated header

2013-03-07T01:53:41Z

updated header

Krzysztof Onak: 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..."

2012-11-17T03:13:39Z

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..."

New page

{{Header
|title=Query Complexity of Local Partitioning Oracles
|source=bertinoro11
|who=Krzysztof Onak
}}
A local partitioning oracle is defined in the paper of Hassidim, Kelner, Nguyen, and Onak {{cite|HassidimKNO-09}}, and an implicit construction of a partitioning oracle is shown in the earlier paper of Benjamini, Schramm, and Shapira {{cite|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 {{cite|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. {{cite|BenjaminiSS-08}}.

← Older revision		Revision as of 14:58, 12 March 2013
Line 8:		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.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Krzysztof Onak