Alex Slivkins: publications

[home | publications by topic]
Hover the mouse above an item to see the description. All pdf links are to "full versions".

    Position papers and surveys

  1. Online Decision Making in Crowdsourcing Markets: Theoretical Challenges
    Aleksandrs Slivkins and Jennifer Wortman Vaughan
    SIGecom Exchanges, Dec 2013. (comments welcome!) In crowdsourcing markets, task requesters and the platform itself make repeated decisions about prices to set, workers to filter out, problems to assign to specific workers, etc. Designing algorithms for making these repeated decisions is a rich, emerging problem space. We survey this problem space, point out significant modeling difficulties, and identify directions to make progress.
  2. Crowdsourcing Gold-HIT Creation at Scale: Challenges and Adaptive Exploration Approaches
    Ittai Abraham, Omar Alonso, Vasilis Kandylas, Rajesh Patel, Steven Shelford, A. Slivkins, Hai Wu
    CrowdScale 2013: Workshop on Crowdsourcing at Scale Gold HITs --- Human Intelligence Tasks with known answers --- are commonly used to measure worker performance and data quality in industrial applications of crowdsourcing. We suggest adaptive exploration as a promising approach for automated, scalable Gold HIT creation. We substantiate this with initial experiments in a stylized model.

    Conference and journal publications

  1. Adaptive Contract Design for Crowdsourcing Markets:
    Bandit Algorithms for Repeated Principal-Agent Problems

    Chien-Ju Ho, Aleksandrs Slivkins and Jennifer Wortman Vaughan.
    EC 2014: ACM Symp. on Electronic Commerce
  2. Bandits and Experts in Metric Spaces
    Robert Kleinberg, Aleksandrs Slivkins and Eli Upfal.
    A merged (and heavily revised) version of papers in STOC'08 and SODA'10. 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.
  3. Bandits with Knapsacks
    Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins
    FOCS 2013: IEEE Symp. on Foundations of Computer Science. We define a broad class of explore-exploit problems with knapsack-style resource utilization constraints, which subsumes dynamic pricing, dynamic procurement, pay-per-click ad allocation, and many other problems. Our algorithms achieve optimal regret w.r.t. the optimal dynamic policy.
  4. Dynamic Ad Allocation: Bandits with Budgets (2013) This brief note is on dynamic allocation of pay-per-click ads with advertisers' budgets. We define and analyze a natural extension of UCB1 to per-arm budgets.
  5. Multi-parameter Mechanisms with Implicit Payment Computation
    Moshe Babaioff, Robert Kleinberg and Aleksandrs Slivkins
    EC 2013: ACM Symp. on Electronic Commerce We show that payment computation essentially does not present any obstacle in designing truthful mechanisms, even for multi-parameter domains, and even when we can only call the allocation rule once. Then we study a prominent example for a multi-parameter setting in which an allocation rule can only be called once, which arises in sponsored search auctions.
  6. Selection and Influence in Cultural Dynamics
    David Kempe, Jon Kleinberg, Sigal Oren and Aleksandrs Slivkins
    EC 2013: ACM Symp. on Electronic Commerce One of the fundamental principles driving diversity or homogeneity in a social network is the tension between two forces: influence (tendency to become similar to one's friends) and selection (tendency to interact with similar people). Influence tends to promote homogeneity within a society, while selection frequently causes fragmentation. We analyze which societal outcomes should be expected when both forces are in effect. We consider a natural class of models built upon active lines of work in political opinion formation, cultural diversity, and language evolution.
  7. Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem [poster]
    Ittai Abraham, Omar Alonso, Vasilis Kandylas and Aleksandrs Slivkins
    COLT 2013: Conf. on Learning Theory. We propose a simple model for adaptive quality control in crowdsourced multiple-choice tasks which we call the bandit survey problem. This model is related to, but technically different from the well-known multi-armed bandit problem. We present several algorithms for this problem, and support them with analysis and simulations.
  8. Low-distortion Inference of Latent Similarities from a Multiplex Social Network
    Ittai Abraham, Shiri Chechik, David Kempe and Aleksandrs Slivkins
    SODA 2013: ACM-SIAM Symp. on Discrete Algorithms
    A short version has appeared in It is commonly assumed that individuals tend to be more similar to their friends than to strangers. Thus, we can view an observed social network as a noisy signal about the latent underlying "social space": the way in which individuals are (dis)similar. We present near-linear time algorithms which - under reasonably standard models of social network generation - can infer the similarities from the observed network with provable guarantees.
  9. The best of both worlds: stochastic and adversarial bandits.
    Sébastien Bubeck and Aleksandrs Slivkins
    COLT 2012: Conf. on Learning Theory. We present a new bandit algorithm whose regret is optimal both for adversarial rewards and for stochastic rewards, achieving, resp., square-root regret and polylog regret. Adversarial rewards and stochastic rewards are the two main settings for (non-Bayesian) multi-armed bandits; prior work treats them separately, and does not attempt to jointly optimize for both.
  10. Dynamic pricing with limited supply (rev. Nov'13)
    Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg and Aleksandrs Slivkins
    EC 2012: ACM Symp. on Electronic Commerce
    To appear in the special issue of ACM TEAC: ACM Trans. on Economics and Computation. We consider dynamic pricing with limited supply and unknown demand distribution. We extend multi-armed bandit techniques to the limited supply setting, and obtain optimal regret rates.
  11. Multi-armed bandits on implicit metric spaces
    NIPS 2011: Conf. on Neural Information Processing Systems. Suppose an MAB algorithm is given a tree-based classification of arms. This tree implicitly defines a "similarity distance" between arms, but the numeric distances are not revealed to the algorithm. Our algorithm (almost) matches the best known guarantees for the setting (Lipschitz MAB) in which the distances are revealed.
  12. Contextual bandits with similarity information
    COLT 2011: Conf. on Learning Theory.
    To appear in JMLR: J. of Machine Learning Research. In each round nature reveals a 'context' x, algorithm chooses an 'arm' y, and the expected payoff is μ(x,y). Similarity info is given: a metric space over the (x,y) pairs such that μ is a Lipschitz function. Interpreting the current time as a part of the 'context', we obtain a very general bandit framework that includes slowly changing payoffs and variable sets of arms. The main algorithmic idea is to adapt the partitions of the metric space to frequent context arrivals and high-payoff regions.
  13. Ranked bandits in metric spaces: learning optimally diverse rankings over large document collections
    Aleksandrs Slivkins, Filip Radlinski and Sreenivas Gollapudi
    ICML 2010: Intl. Conf. on Machine Learning.
    JMLR: J. of Machine Learning Research, 14(Feb):399-436, 2013.
    Preliminary version: NIPS 2009 Ranking Workshop. We present a learning-to-rank framework for web search that incorporates similarity and correlation between documents and thus, unlike prior work, scales to large document collections.
  14. Truthful Mechanisms with Implicit Payment Computation (rev. Nov'12)
    Moshe Babaioff, Robert Kleinberg and Aleksandrs Slivkins
    J. of the ACM, to appear (2014).
    EC 2010: ACM Symp. on Electronic Commerce (Best paper award) We show that payment computation essentially does not present any obstacle in designing truthful mechanisms for single-parameter domains, even when we can only call the allocation rule once. Applying this to multi-armed bandits (MAB), we design truthful MAB mechanisms for stochastic payoffs. More generally, we open up a problem of designing monotone MAB allocation rules.
  15. Sharp Dichotomies for Regret Minimization in Metric Spaces
    Robert Kleinberg and Aleksandrs Slivkins
    SODA 2010: ACM-SIAM Symp. on Discrete Algorithms
    The original full version is superseded by this version (revised & merged with the STOC'08 paper). We further study multi-armed bandits 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 (essentially) on whether the metric space is countable.
  16. Adapting to the Shifting Intent of Search Queries
    Umar Syed, Aleksandrs Slivkins and Nina Mishra
    NIPS'09: Annual Conf. on Neural Information Processing Systems Query intent may shift over time. A classifier can use the available signals to predict a shift in intent. Then a bandit algorithm can be used to find the new relevant results. We present a meta-algorithm that combines such classifier with a bandit algorithm in a feedback loop, with favorable regret guarantees.
  17. Triangulation and Embedding using Small Sets of Beacons
    Jon Kleinberg, Aleksandrs Slivkins and Tom Wexler.
    J. of the ACM, 56(6), Sept 2009. We consider metric embeddings and triangulation-based distance estimation in a distributed framework with low load on the participating nodes. Our results provide theoretical insight into the empirical success of several recent Internet-related projects.
  18. Characterizing Truthful Multi-Armed Bandit Mechanisms (revised June'13)
    Moshe Babaioff, Yogeshwer Sharma and Aleksandrs Slivkins
    EC 2009: ACM Symp. on Electronic Commerce
    To appear in SICOMP: SIAM J. on Computing We consider a natural strategic version of the MAB problem motivated by pay-per-click auctions. We show that requiring an MAB algorithm to be incentive-compatible has striking consequences both for structure and regret.
  19. 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.
  20. Multi-armed Bandits in Metric Spaces
    Robert Kleinberg, Aleksandrs Slivkins and Eli Upfal.
    STOC 2008: ACM Symp. on Theory of Computing
    The original full version is superseded by this version (revised & merged with the SODA'10 paper). 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.
  21. Approximate Matching for Peer-to-Peer Overlays with Cubit
    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. You can use Cubit to find a movie, song or artist even if you misspell the title or the name.
  22. 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.
  23. 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.
  24. Metric Embeddings with Relaxed Guarantees
    T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg and A. Slivkins
    SIAM J. on Computing, 38(6): 2303-2329, March 2009.
    FOCS 2005: IEEE Symp. on Foundations of Computer Science [slides] 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.
  25. Meridian: A Lightweight Network Location Service without Virtual Coordinates
    ACM SIGCOMM 2005
    Bernard Wong, Aleksandrs Slivkins and Emin G. Sirer. Meridian is a scalable overlay network for performing locality-aware node selection. The project features a live PlanetLab deployement.
  26. Distance Estimation and Object Location via Rings of Neighbors
    PODC 2005: ACM Symp. on Principles of Distributed Computing [slides] Special issue of "Distributed Computing": Vol. 19, No. 4. (March 2007). 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.
  27. Distributed Approaches to Triangulation and Embedding
    SODA 2005: ACM-SIAM Symp. on Discrete Algorithms
    [recommended version: merged journal version of the FOCS'04 paper] Following up on the FOCS'04 paper, we consider metric embeddings and triangulation-based distance estimation in a distributed framework with low load on all participating nodes.
  28. 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 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.
  29. Network Failure Detection and Graph Connectivity
    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.
  30. Parameterized Tractability of Edge-Disjoint Paths on DAGs
    SIAM J. on Discrete Math, 24(1): 146-157, Feb 2010.
    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.
  31. Interleaving Schemes on Circulant Graphs with Two Offsets
    Aleksandrs Slivkins and Shuki Bruck.
    Discrete Mathematics 309(13): 4384-4398, July 2009.
    Undergraduate research project (1999-2000), tech report (2002). We construct optimal interleaving schemes on infinite circulant graphs with two offsets. Interleaving is used for error-correcting on a bursty noisy channel.
Contact Us Terms of Use Trademarks Privacy & Cookies ©2010 Microsoft Corporation. All rights reserved.Microsoft