Borel oracles. An analytical approach to constant-time algorithms
From MaRDI portal
Publication:3581114
DOI10.1090/S0002-9939-10-10291-3zbMath1200.68283arXiv0907.1805OpenAlexW2117195616MaRDI QIDQ3581114
Publication date: 16 August 2010
Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0907.1805
Descriptive set theory (03E15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Approximate Schreier decorations and approximate Kőnig's line coloring theorem, Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems, Ramanujan graphings and correlation decay in local algorithms, Factor of IID Percolation on Trees, Approximating Cayley Diagrams Versus Cayley Graphs, Matchings on infinite graphs, Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy, Matchings on trees and the adjacency matrix: A determinantal viewpoint, Controllability, matching ratio and graph convergence, Suboptimality of local algorithms for a class of max-cut problems, Spectral measures of factor of i.i.d. processes on vertex-transitive graphs, KŐNIG’S LINE COLORING AND VIZING’S THEOREMS FOR GRAPHINGS, Perfect matchings as IID factors on non-amenable groups, Limits of locally-globally convergent graph sequences, Tilings in graphons, Følner tilings for actions of amenable groups, Measurable versions of Vizing's theorem, Ultraproducts of measure preserving actions and graph combinatorics, Matchings in Benjamini–Schramm convergent graph sequences, A determinacy approach to Borel combinatorics, Measurable equidecompositions for group actions with an expansion property, On Baire measurable colorings of group actions, Orienting Borel graphs
Cites Work
