Alex Slivkins

Researcher, Microsoft Research, Silicon Valley Campus. My research interests include design and analysis of algorithms, metric embeddings and the theory of large distributed networks. Recently I became interested in online learning problems such as the multi-armed bandits. papers   manuscripts   misc   contact info For connections between some of my papers, see publications by topic.

Education

• Postdoc at Brown University, 2006-2007, with Eli Upfal.
• Ph.D. Computer Science, Cornell University, 2000-2006.
  Thesis committee: Jon Kleinberg (advisor), Gun Sirer and Eva Tardos.
  Thesis: Embedding, Distance Estimation and Object Location in Networks.
• B.S. Mathematics (with distinction), California Institute of Technology, 1996-2000.

Professional

• Junior Program Committee Member, PODC 2007.

Publications

• Adapting to a Changing Environment: the Brownian Restless Bandits
  Aleksandrs Slivkins and Eli Upfal.
  COLT 2008: Conf. on Learning Theory.
  We study a version of the i.i.d. multi-armed bandit problem in which the expected reward of each arm evolves stochastically and gradually in time, following an independent Brownian motion or a similar process. Our benchmark is a hypothetical policy that chooses the best arm in each round.
• Multi-armed Bandits in Metric Spaces
  Robert Kleinberg, Aleksandrs Slivkins and Eli Upfal.
  STOC 2008: ACM Symp. on Theory of Computing
  We consider an i.i.d. multi-armed bandit problem with a very large set of arms such that the expected payoffs obey a Lipschitz condition with respect to a given metric. We minimize regret as a function of time: R(t) &le O(t^&gamma) for some &gamma<1 that depends on the problem instance. Our algorithm achieves optimal &gamma for any given metric.
• Towards Fast Decentralized Construction of Locality-Aware Overlay Networks
  PODC 2007: ACM Symp. on Principles of Distributed Computing [slides]
  We provide fast (polylog-time) distributed constructions for various locality-aware (low-stretch) distributed data structures, such as distance labeling schemes, name-independent routing schemes, and multicast trees.
• Oscillations with TCP-like Flow Control in Networks of Queues
  Matthew Andrews and Aleksandrs Slivkins
  INFOCOM 2006 IEEE Conf. on Computer Communications
  For a wide range of TCP-like fluid-based congestion control models, we construct a network of sessions and (almost) FIFO routers such that starting from a certain initial state, the system returns to the same state eventually. Contrasting the prior work, in our example the total sending rate of all sessions that come through any given router never exceeds its capacity.
• Metric Embeddings with Relaxed Guarantees
  T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg and Aleksandrs Slivkins
  Accepted to SIAM J. on Computing (revised version coming).
  FOCS 2005: IEEE Symp. on Foundations of Computer Science [slides]
  • the focs05 version is merged with an independent submission by I.Abraham, Y.Bartal and O.Neiman.
  Given any x, any metric admits a low-dim embedding into L_p, p>=1 with disortion D(x) = O(log 1/x) on all but an x-fraction of edges. Moreover, any decomposable metric (e.g. any doubling metric) admits a low-dim embedding such that D(x) = O(log 1/x)^1/p for all x.
• Meridian: A Lightweight Network Location Service without Virtual Coordinates
  ACM SIGCOMM 2005 [conference version]
  Bernard Wong, Aleksandrs Slivkins and Emin G. Sirer.
  [expanded journal submission Aug'06] [Meridian project]
  Meridian is a scalable overlay network for performing locality-aware node selection without using virtual coordinates. Our project features a live PlanetLab deployement.
• Distance Estimation and Object Location via Rings of Neighbors
  PODC 2005: ACM Symp. on Principles of Distributed Computing [slides]
  • Best Student Paper Award (eligibility rule: &ge 1 student author)
  Special issue of "Distributed Computing": Vol. 19, No. 4. (March 2007), pp. 313-333.
  We approach several problems on distance estimation and object location with a unified technique called "rings of neighbors". Using this technique on metrics of low doubling dimension, we obtain significant improvements for low-stretch routing schemes, searchable small-world networks, distance labeling, and triangulation-based distance estimation.
• Distributed Approaches to Triangulation and Embedding
  SODA 2005: ACM-SIAM Symp. on Discrete Algorithms
  [recommended version: journal submission merged with the focs04 paper]
  We consider metric embeddings and triangulation-based distance estimation in a distributed framework with low load on all participating nodes. This is motivated by the empirical success of several recent Internet-related projects.
• Triangulation and Embedding using Small Sets of Beacons
  Jon Kleinberg, Aleksandrs Slivkins and Tom Wexler.
  FOCS 2004: The IEEE Symp. on Foundations of Computer Science [slides]
  [recommended version: journal submission: merged with the soda05 paper].
  • For a full story that includes results from soda05 and focs05, see Chapter 3 of my thesis.
  We consider metric embeddings and triangulation-based distance estimation in a distributed framework where nodes measure distances only to a small set of beacons. Our results provide theoretical insight into the empirical success of several recent Internet-related projects.
• Network Failure Detection and Graph Connectivity
  Jon Kleinberg, Mark Sandler and Aleksandrs Slivkins.
  To appear in SIAM J. on Computing.
  SODA 2004: The ACM-SIAM Symp. on Discrete Algorithms [slides]
  We detect network partitions -- with strong provable guarantees -- using a small set of 'agents' placed randomly on nodes of the network. We parameterize our guarantees by edge- and node-connectivity of the underlying graph.
• Parameterized Tractability of Edge-Disjoint Paths on DAGs
  Accepted to SIAM J. on Discrete Math (revised version coming).
  ESA 2003: The European Symp. on Algorithms [slides]
  • Some preliminary results appeared as a technical report with Martin Pal.
  We resolve a long-standing open question about the complexity of the k-edge-disjoint paths problem: we show that on DAGs it is W[1]-hard, hence unlikely to admit running time f(k)*poly(n). However, such running time can be achieved if the input+demands graph is almost Eulerian.

Manuscripts

• Interleaving Schemes on Circulant Graphs with Two Offsets (2001, rev. 2006)
  This is what came out of my undergraduate research project with Prof. Shuki Bruck at Caltech in 1999-2000. We construct optimal interleaving schemes on infinite circulant graphs with offsets {1,d}. Interleaving is used for error-correcting on a bursty noisy channel.

• I lived in Riga, Latvia till 1996. I finished Riga Secondary School #40.
• My Erdös number is 3: me => Anupam Gupta => Michel Deza => Paul Erdös.