Borel oracles. An analytical approach to constant-time algorithms
- 15 April 2010
- journal article
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 138 (8) , 2939-2947
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Constant-Time Approximation Algorithms via Local Improvements2008
- Sublinear time algorithms2007
- Processes on Unimodular Random NetworksElectronic Journal of Probability, 2007
- Topics in Orbit Equivalence2004
- A lower bound for testing 3-colorability in bounded-degree graphs2003
- Recurrence of Distributional Limits of Finite Planar GraphsElectronic Journal of Probability, 2001
- Borel Chromatic NumbersAdvances in Mathematics, 1999
- Bipartite Graphs and their Applications1998
- Closed Sets Without Measurable MatchingProceedings of the American Mathematical Society, 1988
- The Independence Ratio of Regular GraphsProceedings of the American Mathematical Society, 1981