Janardhan Kulkarni

Hi! I am an algorithmist. Currently, I am a researcher in the Algorithms group at Microsoft Research (MSR), Redmond.

I got Ph.D. from the department of Computer Science at Duke University, where my adviser was (is) Kamesh Munagala.

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:

Education:

Selected Academic Awards:

Research Themes:

Selected Invited Talks:

Publications

  1. An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
    with Sayan Bhattacharya

  2. Lift and Project Algorithms For Precedence Constrained Scheduling To Minimize Weighted Completion Time.
    with Shashwat Garg and Shi Li
    SODA 2019.

  3. A Polynomial Time Constant Factor Approximation Algorithm For Weighted Flow-Time
    with Uriel Feige and Shi Li
    SODA 2019.
    (Along with Batra et al paper, resolves a long standing conjecture.)

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

  5. Tight Bounds For Online Vector Scheduling
    with Sungjin Im, Nathaniel Kell, Debmalya Panigrahi
    SICOMP 2018

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

  7. Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models
    with Shi Li.
    APPROX 2018

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

  9. An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors
    with Joshua Allen, Bolin Ding, Harsha Nori, Olga Ohrimenko, Sergey Yekhanin
    Privacy Preserving Machine Learning, PPML 2018

  10. A Distributed Algorithm For Private Heavy Hitters
    with Bolin Ding, Sergey Yekhanin.
    Privacy Preserving Machine Learning, PPML 2018.
    (Implemented in Windows OS; arXiV version soon.)

  11. Collecting Telemetry Data Privately.
    with Bolin Ding, Sergey Yekhanin.
    NIPS 2017.
    (Implemented in Windows OS)

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

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

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

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

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

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

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

  19. 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
    (Invited To "best of theory" at STOC TheoryFest 2018.)

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

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

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

  23. Robust Price of Anarchy Bounds via LP and Fenchel Duality
    with Vahab Mirrokni
    SODA 2015
    (Develops primal-dual/dual-fitting technique to analyze PoA)

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

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

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

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

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

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

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

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

  32. Cost Aware scheduling
    with Kamesh Munagala.
    WAOA 2011

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

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

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

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