Janardhan Kulkarni

Hi! I got Ph.D. from the department of Computer Science at Duke University. My adviser was (is) Kamesh Munagala. I am now at Microsoft Research (MSR), Redmond.

I am interested in the design of algorithms with provable performance guarantees. My focus in recent years has been on understanding theoretical challenges in building efficient data centers. My research involves using concepts and techniques from the fields of approximation algorithms, online algorithms and game theory. I am also broadly interested in the intersection of online algorithms and online learning theory. Much of my work is theoretical, but I spend non-trivial amount of time converting my equations into code.

If you want to know more about my work, take a look at my papers below or my research statement or these slides or the abstract of my thesis.

Contact: kulkarni at cs dot duke dot edu

Here is my CV.

Read my thesis The Design of Scheduling Algorithms Using Game Theoretic Ideas. It won the Duke Best Thesis Award 2015.

Research Interests:

Professional Activities:


Selected Academic Awards:

Research Themes:

Selected Invited Talks:


  1. A Unified Rounding Algorithm For Unrelated Machine Scheduling.
    with Nikhil Devanur
    (The first approximation algorithm for tardiness and deadline scheduling on unrelated machines.)

  2. Flow-time Optimization When Jobs Have Dependencies.
    with Shi Li.


  3. Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
    with Sungjin Im and Kamesh Munagala
    J. ACM 2017

  4. Collecting Telemetry Data Privately.
    with Bolin Ding, Sergey Yekhanin.
    NIPS 2017.

  5. Truth and Regret in Online Scheduling.
    with Shuchi Chawla, Nikhil Devanur, Rad Niazadeh
    EC 2017.

  6. Minimum Birkhoff-von Neumann Decompositions
    with Euiwoong Lee, Mohit Singh
    Integer Programming and Combinatorial Optimization (IPCO) 2017.

  7. GRAPHENE: Packing and Dependency-Aware Scheduling for Data-Parallel Clusters
    with Robert Grandl, Srikanth Kandula, Sriram Rao, Aditya Akella
    OSDI 2016

  8. A Competitive Flow Time Algorithm for Heterogeneous Clusters under Polytope Constraints
    with Sungjin Im, Ben Moseley, Kamesh Munagala
    APPROX 2016

  9. Competitive Analysis of Constrained Queueing Systems
    with Sungjin Im, Kamesh Munagala
    ICALP 2016

  10. Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines
    with Sungjin Im
    SPAA 2016

  11. Morpheus: Towards Automated SLOs for Enterprise Clusters
    with Sangeetha Abdu Jyothi, Carlo Curino, Ishai Menache, Shravan Matthur Narayanamurthy, Alexey Tumanov, Jonathan Yaniv, Ruslan Mavlyutov, Inigo Goiri, Subru Krishnan, Sriram Rao
    OSDI 2016

  12. ProjecTor: Agile Reconfigurable Datacenter Interconnect
    with Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil R. Devanur, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, Daniel C. Kilper
    SIGCOMM 2016

  13. Competitive Flow-Time Algorithms For Polyhedral Scheduling
    with Sungjin Im and Kamesh Munagala
    FOCS 2015

  14. Tight Bounds For Online Vector Scheduling
    with Sungjin Im, Nathaniel Kell, Debmalya Panigrahi
    FOCS 2015

  15. Minimizing Flow-Time for Unrelated Machines
    with Nikhil Bansal
    STOC 2015
    (The first approximation algorithm for flow-time on unrelated machines.)

  16. Robust Price of Anarchy Bounds via LP and Fenchel Duality
    with Vahab Mirrokni
    SODA 2015
    (Explains PoA analysis using Duality )

  17. Dynamic Coordination Games
    with Vahab Mirrokni
    SIGMETRICS Performance Evaluation Review 2015

  18. Temporal Fairness of Round Robin
    with Sungjin Im and Ben Moseley
    SPAA 2015

  19. SELFISHMIGRATE:A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
    with Sungjin Im, Kamesh Munagala, and Kirk Pruhs
    FOCS 2014
    (The first dual-fitting framework for non-clairvoyant scheduling.)

  20. Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
    with Sungjin Im and Kamesh Munagala
    STOC 2014

  21. Coordination Mechanisms for Selfish Routing Over Time on a Tree
    with Sayan Bhattacharya, Vahab Mirrokni
    ICALP 2014

  22. Coordination Mechanisms from (almost) all Scheduling Policies
    with Sayan Bhattacharya, Sungjin Im, and Kamesh Munagala
    ITCS 2014
    (First application of duality to bound PoA)

  23. Near-optimal Multi-unit Auctions with Ordered Bidders
    Sayan Bhattacharya, Elias Koutsoupias, Stefano Leonardi, Tim Roughgarden, Xiaoming Xu
    EC 2013

  24. Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
    with Kyle Fox, Sungjin Im, and Benjamin Moseley
    APPROX 2013

  25. Cost Aware scheduling
    with Kamesh Munagala.
    WAOA 2011

  26. On Allocations with Negative Externalities
    with Sayan Bhattacharya, Kamesh Munagala and Xiaoming Xu
    WINE 2012

  27. Small Strong Epsilon-nets
    with Pradeesha Ashok, Sathish Govindarajan
    CCCG 2010

  28. New Epsilon-net Constructions
    with Satish Govindarajan
    CCCG 2010

  29. On the Decidability of Model-Checking Information Flow Properties
    with Deepak D'Souza, Raveendra Holla, Raghavendra K. Ramesh, Barbara Sprick
    ICISS 2010

Internships and Visits: