|
Borel oracles. An analytical approach to constant-time algorithms
Author(s):
Gábor
Elek;
Gábor
Lippner
Journal:
Proc. Amer. Math. Soc.
138
(2010),
2939-2947.
MSC (2000):
Primary 03E15;
Secondary 68R10
Posted:
April 15, 2010
MathSciNet review:
2644905
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
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:
-
- 1.
- D. ALDOUS AND R. LYONS, Processes on Unimodular Random Networks. Electron. J. Probab. 12 (2007), no. 54, 1454-1508. 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 3-Colorability in Bounded-Degree Graphs, 43rd Annual IEEE Symposium on Foundations of Computer Science (2002) 93-102.
- 5.
- B. BOLLOBÁS, The independence ratio of regular graphs. Proc. Amer. Math. Soc. 83 no. 2 (1981) 433-436. 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. Springer-Verlag, Berlin, 2004. MR 2095154 (2005f:37010)
- 8.
- A. KECHRIS, S. SOLECKI AND S. TODORCEVIC, Borel chromatic numbers, Advances in Mathematics 141 no. 1 (1999) 1-44. MR 1667145 (2000e:03132)
- 9.
- M. LACZKOVICH, Closed sets without measurable matchings, Proc. of the AMS 103 no. 3 (1988) 894-896. MR 947676 (89f:28018)
- 10.
- 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.
- 11.
- R. RUBINFELD, Sublinear time algorithms, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich (2006) 1095-1110. 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, H-1364, 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, H-117, Budapest, Hungary
Email:
lipi@cs.elte.hu
DOI:
10.1090/S0002-9939-10-10291-3
PII:
S 0002-9939(10)10291-3
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
Posted:
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
Copyright of article:
Copyright
2010,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
