We prove that any 43-fold covering of the plane with translates of a triangle can be decomposed into two coverings.

Given a data stream of length n over an alphabet [m] where n is greater than m, we consider the problem of finding a duplicate in a single pass. We give a randomized algorithm for this problem that uses O((log m)3) space. This answers a question of Muthukrishnan [Mut05] and Tarui [Tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. Our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. Our main tool is an Isolation Lemma that reduces this problem to the task of detecting and identifying a Dictatorial variable in a Boolean halfspace.

I will be describing the "nearest neighbor" (NN) scheme that can be used to design efficient distributed approximation algorithms for minimum spanning tree (MST) and related problems. This talk is a follow up of the recent talk by Gopal Pandurangan at the Computer Science colloquium. There have been various publications on this topic; a detailed technical report can be found here.

In 1979 Erdos, Rubin, and Taylor conjectured that every planar graph has a list chromatic number of at most 5. In 1994, Carsten Thomassen gave a beautiful and extremely simple proof of this conjecture. I will present Thomassen's proof.

A large group of autonomous, mobile entities e.g. robots initially placed at some arbitrary node of the graph has to jointly visit all nodes (not necessarily all edges) and finally return to the initial position. The graph is not known in advance (an online setting) and robots have to traverse an edge in order to discover new parts (edges) of the graph. The team can locally exchange information, using wireless communication devices.
We compare cost of the online and optimal offline algorithm which knows the graph beforehand (competitive ratio). If the cost is the total time of exploraiton, we prove the lower bound of (log k/log log k) for competitive ratio of any deterministic algorithm (using global communication). This significantly improves the best known constant lower bound. For the cost being the maximal number of edges traversed by a robot (the energy) we present an improved (4 − 2/k)-competitive online algorithm for trees.

PTAS for Maximum Independent Set and Hitting Set Problems using local search techniques.

This paper is divided into two parts. In the first part of this paper, we present a 2-approximation algorithm for the soft-capacitated facility location problem. This achieves the integrality gap of the natural LP relaxation of the problem. The algorithm is based on an improved analysis of an algorithm for the linear facility location problem, and a bifactor approximate-reduction from this problem to the soft-capacitated facility location problem. We will define and use the concept of bifactor approximate reductions to improve the approximation factor of several other variants of the facility location problem. In the second part of the paper, we present an alternative analysis of the authors’ 1.52- approximation algorithmfor the uncapacitated facility location problem, using a single factor-revealing LP. This answers an open question of [18]. Furthermore, this analysis, combined with a recent result of Thorup [25] shows that our algorithm can be implemented in quasi-linear time, achieving the best known approximation factor in the best possible running time.

Human networks have a number of distinctive properties which they all exhibit: small-world property, power-law degree distributions, and network transitivity. Another property that has seen recent attention is the property of community structure, where nodes form tightly knit groups with very few inter-group connections. There are two problems surrounding community structure: the ability to find community structure in a network, and a way of evaluating the quality of such a community structure. Unfortunately the problem of determining community structure is not easily solvable by traditional graph partitioning algorithms seen in computer science. Work in this area done by Girven and Newman has produced new algorithms for determining community structure along with a measure of community structure quality known as "modularity". While the algorithms produced by Girven and Newman have been shown to determine the correct community structure for well-known graphs, their running time is O(m**2 n) for a graph with m edges and n nodes, and O(n**3) for a sparse graph. Recent work by Clauset, Newman, and Moore improves this running time, greedy algorithm based on graph "modularity" that runs O(n log**2 n), suitable for large networks. In this talk I will discuss the motivation behind the use of community structure as well as recent methods for determining and evaluating the community structure of a network.

In my previous two ARG talks, I presented results of geometric k-fold coverings which are cover decomposable. That is, given a collection of points in the plane and a collection of geometric objects such that each point is contained within at least k objects, we are able to partition the objects into two sets such that each point is contained within an object in each set of the partition. In this talk, I will describe proofs for certain classes of objects which are indecomposable. That is, for any k, we can construct an example of a k-fold covering which cannot be decomposed into 2 coverings.

This paper presents a new constructive (algorithmic) proof of the Lovasz Local Lemma (LLL). The result allows for poly-time algorithms wherever LLL applies, with virtually no additional constraints. This paper seems to be an extension of Moser's paper in STOC 09.