Home

This is the personal site of Dimitris Achlioptas.

Dimitris Achlioptas

Short bio

Dimitris Achlioptas is a Professor of Computer Science. Prior to that, he was with Microsoft Research, Redmond. He received his Ph.D. from the University of Toronto in 1999.

His research interests explore the role of randomness both to as an aid and as an obstacle to efficient computation. His work on this area has appeared in journals including Nature, Science, and the Annals of Mathematics. He has received an NSF CAREER award, an Alfred P. Sloan Research Fellowship, and an ERC Starting Grant.

Besides theoretical questions, he also likes to think about scalability questions and holds 18 US Patents ranging from load balancing and cache optimization to search personalization. He consults with a number of Bay Area companies.

You can read more about Dimitris Achlioptas in the section About Me.

A list of Dimitris Achlioptas’ publications is under section Publications.


Achlioptas Processes

What are Achlioptas Processes

An Achlioptas process is a generalization of a common procedure of forming an Erdös-Rényi (ER) random graph that adds a rule for choosing amongst a set of candidate links to add to the network and thereby may allow for percolation transitions that differ in character from the transition in the ER model.

Suppose we begin with a graph of 𝑁 isolated nodes and then incrementally build a network from there.

In one common procedure for generating an Erdös-Rényi (ER) random graph, we choose two nodes at random and add a link between them.

To get an ER random graph where the mean degree is 2𝑟, we simply repeat this procedure until we’ve added 𝑟𝑁 links to our network.

In an Achlioptas process, we instead randomly choose 𝑘 pairs of nodes.

The most common and simplest choice is 𝑘=2. With two randomly chosen links in hand, we then use some rule to decide between them.

If we make this decision randomly, we would again recover an ER random graph.

However, we can also consider a variety of non-random selection rules.

Many of these are formulated in terms of the component sizes connected by each proposed link.

For example, we can choose to:

  • minimize the sum of the component sizes connected by the links (a.k.a. a sum rule).
  • minimize the production of the component sizes connected by the links (a.k.a. a product rule).
  • choose the first randomly selected pair if it connects two components of size 𝐾 or smaller, otherwise, choose the second randomly selected pair (a.k.a. a bounded-size rule).

You can read about Achlioptas Processes in details here.


Talks (videos)

In the section Talks (videos), you can see Dimitris Achlioptas’ talks, regarding some aspects of his work, including TedX, etc.

Dimitris Achlioptas in TedX Athens

Search is precisely what makes the web useful to us

Dimitris Achlioptas at TEDxAthens, 2010

You can find News about Dimitris Achlioptas under News section, contact Dimitris, read about Publications, view more Talks, etc.