Alexandre Stauffer

SODA Conference 2013 Conference Paper

Balls into Bins via Local Search

• Paul Bogdan
• Thomas Sauerwald
• Alexandre Stauffer
• He Sun 0001

STOC Conference 2013 Conference Paper

Random lattice triangulations: structure and algorithms

• Pietro Caputo
• Fabio Martinelli
• Alistair Sinclair
• Alexandre Stauffer

SODA Conference 2011 Conference Paper

Mobile Geometric Graphs: Detection, Coverage and Percolation

• Yuval Peres
• Alistair Sinclair
• Perla Sousi
• Alexandre Stauffer

Static wireless networks are by now quite well understood mathematically through the random geometric graph model. By contrast, there are relatively few rigorous results on the practically important case of mobile networks. In this paper we consider a natural extension of the random geometric graph model to the mobile setting by allowing nodes to move in space according to Brownian motion. We study three fundamental questions in this model: detection (the time until a given target point—which may be either fixed or moving—is detected by the network), coverage (the time until all points inside a finite box are detected by the network), and percolation (the time until a given node is able to communicate with the giant component of the network). We derive precise asymptotics for these problems by combining ideas from stochastic geometry, coupling and multi-scale analysis. We also give an application of our results to analyze the time to broadcast a message in a mobile network.

SODA Conference 2011 Conference Paper

Rumor Spreading and Vertex Expansion on Regular Graphs

• Thomas Sauerwald
• Alexandre Stauffer

SODA Conference 2010 Conference Paper

Efficient Broadcast on Random Geometric Graphs

• Milan Bradonjic
• Robert Elsässer
• Tobias Friedrich 0001
• Thomas Sauerwald
• Alexandre Stauffer

A Random Geometric Graph (RGG) in two dimensions is constructed by distributing n nodes independently and uniformly at random in and creating edges between every pair of nodes having Euclidean distance at most r, for some prescribed r. We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability 1 – ( n −1 ) this algorithm informs every node in the largest connected component of an RGG within rounds. This holds for any value of r larger than the critical value for the emergence of a connected component with Ω( n ) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in, the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is, which surprisingly has been an open problem so far.