Borel oracles. An analytical approach to constant-time algorithms

Elek, Gábor; Lippner, Gábor

doi:10.1090/S0002-9939-10-10291-3

Borel oracles. An analytical approach to constant-time algorithms
HTML articles powered by AMS MathViewer

by Gábor Elek and Gábor Lippner PDF

Proc. Amer. Math. Soc. 138 (2010), 2939-2947 Request permission

Abstract:

In 2008 Nguyen and Onak constructed the first constant-time algorithm for the approximation of the size of the maximum matching in bounded degree graphs. The Borel oracle machinery is a tool that can be used to convert some statements in Borel graph theory to theorems in the field of constant-time algorithms. In this paper we illustrate the power of this tool to prove the existence of the above mentioned constant-time approximation algorithm.

References

David Aldous and Russell Lyons, Processes on unimodular random networks, Electron. J. Probab. 12 (2007), no. 54, 1454–1508. MR 2354165, DOI 10.1214/EJP.v12-463
Armen S. Asratian, Tristan M. J. Denley, and Roland Häggkvist, Bipartite graphs and their applications, Cambridge Tracts in Mathematics, vol. 131, Cambridge University Press, Cambridge, 1998. MR 1639013, DOI 10.1017/CBO9780511984068
Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300, DOI 10.1214/EJP.v6-96
A. Bogdanov, K. Obata and L. Trevisan, A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs, 43rd Annual IEEE Symposium on Foundations of Computer Science (2002) 93-102.
Béla Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83 (1981), no. 2, 433–436. MR 624948, DOI 10.1090/S0002-9939-1981-0624948-6
G. Elek, Parameter testing in bounded degree graphs of subexponential growth (to appear). http://arxiv.org/abs/0711.2800
Alexander S. Kechris and Benjamin D. Miller, Topics in orbit equivalence, Lecture Notes in Mathematics, vol. 1852, Springer-Verlag, Berlin, 2004. MR 2095154, DOI 10.1007/b99421
A. S. Kechris, S. Solecki, and S. Todorcevic, Borel chromatic numbers, Adv. Math. 141 (1999), no. 1, 1–44. MR 1667145, DOI 10.1006/aima.1998.1771
M. Laczkovich, Closed sets without measurable matching, Proc. Amer. Math. Soc. 103 (1988), no. 3, 894–896. MR 947676, DOI 10.1090/S0002-9939-1988-0947676-2
H. N. Nguyen and K. Onak, Constant-time approximation algorithms via local improvements, 49th Annual IEEE Symposium on Foundations of Computer Science (2008) 327-336.
Ronitt Rubinfeld, Sublinear time algorithms, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, pp. 1095–1110. MR 2275720