Mika Göös/Mon 2 Apr 1315hrs

[Kaski Petteri]

FYI

Cheers,

Petteri.

Begin forwarded message:

From: Seth Sohan <sohan...@aalto.fi>

Date: March 26, 2012 3:49:30 PM GMT+03:00

To: "st...@hiit.fi" <st...@hiit.fi>

Cc: "st...@ics.tkk.fi" <st...@ics.tkk.fi>

Subject: [Kumpula-ada] [Kumpula-staff] =?iso-8859-1?Q?HIIT_Otaniemi_Seminar, _Mon_Apr_2_13:15, _Mika_G=F6=F6s?=

Our next speaker for HIIT Otaniemi seminar series is Mika Göös from the Helsinki Institute for Information Technology.

All ICS@Aalto researchers are also warmly welcome to attend the seminar!

HIIT Otaniemi Seminar, Monday April 2nd, 13:15

Location: Computer Science Building, Hall T2

Speaker: Mika Göös

Title: Lower Bounds for Local Approximation

Abstract: 

In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique $O(\log n)$-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient.

Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks. 

As a corollary of our result and by prior work, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem. 

Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is $(\alpha,r)$-homogeneous if its nodes are linearly ordered so that an $\alpha$ fraction of nodes have pairwise isomorphic radius-$r$ neighbourhoods. We show that there exists a finite $(\alpha,r)$-homogeneous $2k$-regular graph of girth at least $g$ for any $\alpha < 1$ and any $r$, $k$, and $g$.

Joint work with Juho Hirvonen and Jukka Suomela.

A manuscript of this work is available online at http://arxiv.org/abs/1201.6675.

Bio:

 

Mika Göös is currently a PhD student in the "New Paradigms in Computing" group at Helsinki Intitute for Information Technology.

_______________________________________________
Kumpula-staff mailing list
Kumpul...@hiit.fi
https://list.it.hiit.fi/mailman/listinfo/kumpula-staff_______________________________________________
Kumpula-ada mailing list
Kumpu...@hiit.fi
https://list.it.hiit.fi/mailman/listinfo/kumpula-ada