Alex Slivkins: publications

My main page is here. For connections between my papers, see publications by topic.
  • Contextual bandits with similarity information (2009)
    In the 'contextual bandits' setting, in each round nature reveals a 'context' x, algorithm chooses an 'arm' y, and the expected payoff is &mu(x,y). Similarity info is expressed by a metric space over the (x,y) pairs such that &mu is a Lipschitz function. Our algorithms are based on adaptive (rather than uniform) partitions of the metric space which are adjusted to the popular and high-payoff regions.
  • Approximate Matching for Peer-to-Peer Overlays with Cubit (2009)
    Bernard Wong, Aleksandrs Slivkins and Emin G. Sirer
    Cubit is a system that provides fully decentralized approximate keyword search capabilities to a peer-to-peer network. Approximate search means that you can use Cubit to find a movie, song or artist even if you misspell the title or the name.
  • Sharp Dichotomies for Regret Minimization in Metric Spaces
    Robert Kleinberg and Aleksandrs Slivkins
    SODA 2010: ACM-SIAM Symp. on Discrete Algorithms
    We further study multi-armed bandit problems in metric spaces, focusing on the connections between online learning and metric topology. The main result is that the worst-case regret is either O(log t) or at least sqrt{t}, depending on whether the completion of the metric space is compact and countable. We prove a number of other dichotomy-style results, and extend them to the full-feedback (experts) version.
  • Adapting to the Shifting Intent of Search Queries
    Umar Syed, Nina Mishra and Aleksandrs Slivkins
    NIPS'09: Annual Conf. on Neural Information Processing Systems
  • Triangulation and Embedding using Small Sets of Beacons
    Jon Kleinberg, Aleksandrs Slivkins and Tom Wexler.
    J. of the ACM, 56(6), Sept 2009.
    Significantly revised, merged full version of papers from FOCS 2004 and SODA 2005.
    We consider metric embeddings and triangulation-based distance estimation in a distributed framework with low load on all (or all but a few) participating nodes. Our results provide theoretical insight into the empirical success of several recent Internet-related projects.
  • Characterizing Truthful Multi-Armed Bandit Mechanisms (full version: rev. Sept'09)
    Moshe Babaioff, Yogeshwer Sharma and Aleksandrs Slivkins
    EC 2009: ACM Symp. on Electronic Commerce
    We consider a multi-round auction setting motivated by pay-per-click auctions in the Internet advertising. Our setting can be viewed as a strategic version of the MAB problem. We investigate how the design of MAB algorithms is affected by the restriction of truthfulness. We show striking differences in terms of both structure and regret.
  • 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 stochastic 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 (full version)
    Robert Kleinberg, Aleksandrs Slivkins and Eli Upfal.
    STOC 2008: ACM Symp. on Theory of Computing
    We introduce the 'Lipschitz MAB problem': a stochastic MAB problem, possibly with a very large set of arms, such that the expected payoffs obey a Lipschitz condition with respect to a given metric space. The goal is to minimize regret as a function of time, both in the worst case and for 'nice' problem instances.
  • Towards Fast Decentralized Construction of Locality-Aware Overlay Networks (full version)
    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 (full version)
    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 (journal version: rev. Aug'08)
    T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg and Aleksandrs Slivkins
    SIAM J. on Computing, 38(6): 2303-2329, March 2009.
    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 Lp, 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
    Bernard Wong, Aleksandrs Slivkins and Emin G. Sirer.
    [extended full version (Nov'05) and journal submission (Aug'06)]
    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 (full version)
    PODC 2005: ACM Symp. on Principles of Distributed Computing [slides]
    • Best Student Paper Award (eligibility rule: at least one 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 (full version)
    SODA 2005: ACM-SIAM Symp. on Discrete Algorithms
    [recommended version: merged journal version of the FOCS'04 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 (journal version)
    Jon Kleinberg, Aleksandrs Slivkins and Tom Wexler.
    FOCS 2004: The IEEE Symp. on Foundations of Computer Science [slides]
    [The journal version includes results from the SODA'05 paper.]
    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 (full version)
    Jon Kleinberg, Mark Sandler and Aleksandrs Slivkins.
    SIAM J. on Computing, 38(4): 1330-1346, Aug 2008.
    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 (journal version: rev. Sept'08)
    SIAM J. on Discrete Math, to appear in 2009.
    ESA 2003: The European Symp. on Algorithms [slides]
    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.
  • Interleaving Schemes on Circulant Graphs with Two Offsets (2001, rev. Oct'08)
    Aleksandrs Slivkins and Shuki Bruck.
    Discrete Mathematics 309(13): 4384-4398, July 2009.
    An undergrad research project with Prof. Shuki Bruck at Caltech (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.
_________________________________________________________________________________________