Borel oracles. An analytical approach to constanttime algorithms
Authors:
Gábor Elek and Gábor Lippner
Journal:
Proc. Amer. Math. Soc. 138 (2010), 29392947
MSC (2000):
Primary 03E15; Secondary 68R10
Published electronically:
April 15, 2010
MathSciNet review:
2644905
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In 2008 Nguyen and Onak constructed the first constanttime 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 constanttime algorithms. In this paper we illustrate the power of this tool to prove the existence of the above mentioned constanttime approximation algorithm.
 1.
David
Aldous and Russell
Lyons, Processes on unimodular random networks, Electron. J.
Probab. 12 (2007), no. 54, 1454–1508. MR 2354165
(2008m:60012), 10.1214/EJP.v12463
 2.
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
(99e:05121)
 3.
Itai
Benjamini and Oded
Schramm, Recurrence of distributional limits of finite planar
graphs, Electron. J. Probab. 6 (2001), no. 23, 13 pp.
(electronic). MR
1873300 (2002m:82025), 10.1214/EJP.v696
 4.
A. BOGDANOV, K. OBATA AND L. TREVISAN, A Lower Bound for Testing 3Colorability in BoundedDegree Graphs, 43rd Annual IEEE Symposium on Foundations of Computer Science (2002) 93102.
 5.
Béla
Bollobás, The independence ratio of regular
graphs, Proc. Amer. Math. Soc.
83 (1981), no. 2,
433–436. MR
624948 (82m:05079), 10.1090/S00029939198106249486
 6.
G. ELEK, Parameter testing in bounded degree graphs of subexponential growth (to appear). http://arxiv.org/abs/0711.2800
 7.
Alexander
S. Kechris and Benjamin
D. Miller, Topics in orbit equivalence, Lecture Notes in
Mathematics, vol. 1852, SpringerVerlag, Berlin, 2004. MR 2095154
(2005f:37010)
 8.
A.
S. Kechris, S.
Solecki, and S.
Todorcevic, Borel chromatic numbers, Adv. Math.
141 (1999), no. 1, 1–44. MR 1667145
(2000e:03132), 10.1006/aima.1998.1771
 9.
M.
Laczkovich, Closed sets without measurable
matching, Proc. Amer. Math. Soc.
103 (1988), no. 3,
894–896. MR
947676 (89f:28018), 10.1090/S00029939198809476762
 10.
H. N. NGUYEN AND K. ONAK, Constanttime approximation algorithms via local improvements, 49th Annual IEEE Symposium on Foundations of Computer Science (2008) 327336.
 11.
Ronitt
Rubinfeld, Sublinear time algorithms, International Congress
of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006,
pp. 1095–1110. MR 2275720
(2007m:68124)
 1.
 D. ALDOUS AND R. LYONS, Processes on Unimodular Random Networks. Electron. J. Probab. 12 (2007), no. 54, 14541508. MR 2354165 (2008m:60012)
 2.
 A.S. ASRATIAN, T.M.J. DENLEY AND R. H¨AGGKVIST, Bipartite graphs and their applications. Cambridge Tracts in Mathematics, Cambridge University Press (1998). MR 1639013 (99e:05121)
 3.
 I. BENJAMINI AND O. SCHRAMM, Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 no. 23 (2001) 13 pp. (electronic). MR 1873300 (2002m:82025)
 4.
 A. BOGDANOV, K. OBATA AND L. TREVISAN, A Lower Bound for Testing 3Colorability in BoundedDegree Graphs, 43rd Annual IEEE Symposium on Foundations of Computer Science (2002) 93102.
 5.
 B. BOLLOBÁS, The independence ratio of regular graphs. Proc. Amer. Math. Soc. 83 no. 2 (1981) 433436. MR 624948 (82m:05079)
 6.
 G. ELEK, Parameter testing in bounded degree graphs of subexponential growth (to appear). http://arxiv.org/abs/0711.2800
 7.
 A. KECHRIS AND B. D. MILLER, Topics in orbit equivalence theory. Lecture Notes in Mathematics, 1852. SpringerVerlag, Berlin, 2004. MR 2095154 (2005f:37010)
 8.
 A. KECHRIS, S. SOLECKI AND S. TODORCEVIC, Borel chromatic numbers, Advances in Mathematics 141 no. 1 (1999) 144. MR 1667145 (2000e:03132)
 9.
 M. LACZKOVICH, Closed sets without measurable matchings, Proc. of the AMS 103 no. 3 (1988) 894896. MR 947676 (89f:28018)
 10.
 H. N. NGUYEN AND K. ONAK, Constanttime approximation algorithms via local improvements, 49th Annual IEEE Symposium on Foundations of Computer Science (2008) 327336.
 11.
 R. RUBINFELD, Sublinear time algorithms, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich (2006) 10951110. MR 2275720 (2007m:68124)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2000):
03E15,
68R10
Retrieve articles in all journals
with MSC (2000):
03E15,
68R10
Additional Information
Gábor Elek
Affiliation:
Alfred Renyi Institute of the Hungarian Academy of Sciences, P.O. Box 127, H1364, Budapest, Hungary
Email:
elek@renyi.hu
Gábor Lippner
Affiliation:
Department of Computer Science, Eötvös University, Pázmány Péter sétány 1/C, H117, Budapest, Hungary
Email:
lipi@cs.elte.hu
DOI:
http://dx.doi.org/10.1090/S0002993910102913
Keywords:
Constant time algorithms,
graph limits,
Borel graphs,
invariant measures,
maximum matching
Received by editor(s):
July 18, 2009
Received by editor(s) in revised form:
November 14, 2009
Published electronically:
April 15, 2010
Additional Notes:
The first author’s research was sponsored by OTKA Grant 67867
The second author’s research was sponsored by OTKA Grant 69062
Communicated by:
Julia Knight
Article copyright:
© Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
