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 Polynomial Time Constant Factor Approximation Algorithm For Weighted Flow-Time
    with Uriel Feige and Shi Li
    (Along with Batra et al paper, resolves a long standing conjecture.)

  2. Deterministically Maintaining a (2+ε)-Approximate Minimum Vertex Cover in O(1/ε2) Amortized Update Time
    with Sayan Bhattacharya


  3. A Unified Rounding Algorithm For Unrelated Machine Scheduling.
    with Nikhil Devanur
    SPAA 2018
    (The first constant approximation algorithm for l_p norm of weighted completion time)

  4. Flow-time Optimization When Jobs Have Dependencies.
    with Shi Li.
    APPROX 2018

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

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

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

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

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

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

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

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

  13. 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

  14. 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

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

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

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

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

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

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

  21. 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.)

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

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

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

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

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

  27. Cost Aware scheduling
    with Kamesh Munagala.
    WAOA 2011

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

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

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

  31. 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: