I am a Ph.D. student in the department of Computer Science
. My adviser is Kamesh Munagala
. I am interested design of algorithms with provable performance guarantee. In particular, I work in resource allocation and scheduling problems arising in large scale distributed data-centers with added constraints of energy minimization, fairness and strategyproofness. My research involves using concepts and techniques from the fields of approximation algorithms, online algorithms and game theory.
Contact: kulkarni at cs dot duke dot edu
Approximation algorithms, Online algorithms, Game theory, Differential privacy and Data-analytics.
- Ph.D, department of Computer Science, Duke University, Durham, 2010-2014 (expected).
- Master of Engineering, Computer Science and automation, Indian Institute of Science (IISc), Bangalore, India.
- Bachelor of Engineering, Sri Jayachamarajendra College of Engineering (SJCE), Mysore, India.
- Robust Price of Anarchy Bounds via LP and Fenchel Duality
with Vahab Mirrokni
- SELFISHMIGRATE:A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
with Sungjin Im, Kamesh Munagala, Kirk Pruhs
FOCS 2014. Paper available on arXiv.
- Coordination Mechanisms for Selfish Routing Over Time on a Tree
with Sayan Bhattacharya, Vahab Mirrokni
- Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
with Sungjin Im and Kamesh Munagla
- Coordination mechanisms from (almost) all scheduling policies
with Sayan Bhattacharya, Sungjin Im and Kamesh Munagala
Innovations in Theoretical Computer Science, ITCS '14
- Near-optimal Multi-unit Auctions with Ordered Bidders
with S.Bhattacharya, E. Koutsoupias, S. Leonardi, T. Roughgarden and X.Xu
Electronic Commerce, EC'13
- Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
with Sunjin Im, Kyle Fox and Benjamin Moseley
- Cost Aware scheduling
with Kamesh Munagala.
- On Allocations with Negative Externalities
with Sayan Bhattacharya, Kamesh Munagala and Xiaoming Xu
- Online Scheduling with General Cost Functions
with Pradeesha Ashok, Sathish Govindarajan
- New epsilon-net constructions
with Satish Govindarajan
- Minimizing Flow-Time for Unrelated Machines
with Nikhil Bansal
(Gives the first approximation algorithm for flow-time on unrelated machines. Will be submitted to STOC 2015. Paper available on arXiv.)
- A Geometric Approach to Diverse Group Formation
with Arindam Khan and Sreenivas Gollapudi
- Greedy dispatch meets greedy jobs: Online scheduling of selfish jobs for unrelated machines
with Sungjin Im
- Local Search Approach for Graph Deanonymization
with Wuzhou Zhang, Bharath Chelepalli and Ashwin Machanavajjhala
- Microsoft Research, Silicon Valley, CA. Summer 2013
Host: Sreenivas Gollapudi
- Visited professor Kirk Pruhs , University of Pittsburgh, April 2012
- Visited Vahab Mirrokni , Google Research, NYC, April 2014
Academic Awards (selected):
- Outstanding Prelim award, Duke, 2013
- Outstanding Teaching Assistant award, Duke, 2012
- Gold medal, Indian Institute of Science, 2010
- Invited talk, IBM TJ Watson, NYC (June 2014).Non-Clairvoyant Scheduling To Minimize Weighted Flow-Time.
- STOC 2014, NYC (June 2014).Competitive Algorithms From Competitive Equilibria.
- Invited talk, Google Research, NYC (April 2014). Dual Fitting Framework for Scheduling and Routing Games.
- ITCS 2014, Princeton University, Princeton (Jan 2014).Coordination Mechanisms From Almost All Scheduling Policies
- APPROX 2013,University of California,Berkeley (Aug 2013) Non-clairvoyant Scheduling to Minimize All Convex Functions
- MAPSP 2013, Pont à Mousson, France (Aug 2013). Coordination Mechanisms from (almost) all Scheduling Policies
- ALGO 2013, Ljubljana, Slovenia (Sept 2012). Coordination Mechanisms from (almost) all Scheduling Policies
I worked as a (senior) software engineer from 2004 to 2008 at Huawei Technologies and Citrix Systems. At industry, I worked on Internet routing protocols, especially on multicast routing. During that period, I dabbled with some IETF standardization work.
- PIM-Ping: A Tool to Test the Convexity of Ping Domain
with Archana Patel
- Equal cost route support for RIP/RIPNG
with Naveen Anand