Dept Banner
Dept Banner


Download as iCal file

DIMACS Theory of Computing Seminar

A tale of two local models of computation

Location:  CoRE 301
Date & time: Wednesday, 28 September 2016 at 11:00AM -

Guy Even , Tel-Aviv University


"A tale of two local models of computation"

Time: 11:00 AM
Location: CoRE 301
Abstract: We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in \(log^* n\), where \(n\) is the number of vertices of the input graph.

The recursive centralized local improvement technique by Nguyen and Onak is employed to obtain an improved distributed approximation scheme for maximum (weighted) matching. The improvement is twofold: we reduce the number of rounds from \(O(log n)\) to \(O(log^* n)\) and our algorithms are deterministic.

Time permitting, a centralized local algorithm for generating random preferential attachment graphs will be presented. Per query, the algorithms uses polylogarithmic random bits, time, and space.

Talk based on joint work with Reut Levy, Moti Medina, Dana Ron, and Adi Rosen.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530