๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An O(n1/3) algorithm for distributed mutual exclusion

โœ Scribed by Pranay Chaudhuri; Mehmet Hakan Karaata

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
189 KB
Volume
45
Category
Article
ISSN
1383-7621

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An Oฬƒ(n314)-coloring algorithm for 3-col
An Oฬƒ(n314)-coloring algorithm for 3-colorable graphs
โœ Avrim Blum; David Karger ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 471 KB

We show how the results of Karger, Motwani, and Sudan ( 1994) and Blum ( 1994) can be combined in a natural manner to yield a polynomial-time algorithm for d(n3"4 )-coloring any n-node 3-colorable graph. This improves on the previous best bound of 6(n'14) colors (Karger et al., 1994).

An O(nlog log n) Learning Algorithm for
An O(nlog log n) Learning Algorithm for DNF under the Uniform Distribution
โœ Y. Mansour ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 571 KB

We show that a DNF with terms of size at most \(d\) can be approximated by a function at most \(d^{O(d \log 1 / \epsilon)}\) nonzero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most \(\epsilon\). This property is used to derive a learnin