Ashish Chiplunkar Pankaj Gupta Faculty Fellow and Assistant Professor Department of Computer Science and Engineering Indian Institute of Technology Delhi Office: Bharti-409 E-mail: echo iitd.ac.in | sed s/^/ashishc@/

Project / Internship Requests

Please READ THIS before you contact me.

Past Affiliations

• Sep 2017 - Aug 2019: Post-doc in the theory group at the School of Computer and Communication Sciences, EPFL, hosted by Prof. Michael Kapralov and Prof. Ola Svensson
• Mar 2016 - Aug 2017: Post-doc at the School of Computer Science, Tel-Aviv University, hosted by Prof. Amos Fiat and Prof. Haim Kaplan
• Nov 2014 - Dec 2015: Research Scientist at Amazon, Bengaluru
• Jul 2009 - May 2015: Grad student at the Department of Computer Science and Engineering, IITB, supervised by Prof. Sundar Vishwanathan

Research Interests

Algorithm design and analysis: particularly for online and stochastic problems.

Professional Activities

• Program Committee Member: FSTTCS 2021, ESA 2018

Publications

Publications in Journals

(in reverse chronological order)

• Randomized Memoryless Algorithms for the Weighted and the Generalized k-server Problems
  with Sundar Vishwanathan in volume 16 issue 1 of ACM Transactions on Algorithms, 2020
• Metrical Service Systems with Multiple Servers
  with Sundar Vishwanathan in volume 71 issue 1 of Algorithmica, 2015

Selected Publications in Conference Proceedings

(in reverse chronological order)

• Prophet Inequality: Order selection beats random order
  with Archit Bubna, to appear in EC 2023
• Online Min-Max Paging
  with Monika Henzinger, Sagar Kale, and Maximilian Vötsch, in SODA 2023
• Factorial Lower Bounds for (Almost) Random Order Streams
  with John Kallaugher, Michael Kapralov, and Eric Price, in FOCS 2022
• The Randomized Competitive Ratio of Weighted k-server is at Least Exponential
  with Nikhil Ayyadevara, in ESA 2021
• How to Solve Fair k-Center in Massive Data Models
  with Sagar Kale and Sivaramakrishnan Natarajan Ramamoorthy, in ICML 2020
• Testing Graph Clusterability: Algorithms and Lower Bounds
  with Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres, in FOCS 2018
• Prophet Secretary: Surpassing the 1-1/e Barrier
  with Yossi Azar and Haim Kaplan, in EC 2018
• Min-Cost Bipartite Perfect Matching with Delays
  with Itai Ashlagi, Yossi Azar, Moses Charikar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer, in APPROX 2017
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
  with Yossi Azar and Haim Kaplan, in SODA 2017
• Approximating the Regular Graphic TSP in near linear time
  with Sundar Vishwanathan, in FSTTCS 2015
• On Randomized Algorithms for Matching in the Online Preemptive Model
  with Sumedh Tirodkar and Sundar Vishwanathan, in ESA 2015
• On Randomized Memoryless Algorithms for the Weighted k-server Problem
  with Sundar Vishwanathan, in FOCS 2013
• Metrical Service Systems with Multiple Servers
  with Sundar Vishwanathan, in COCOON 2013
• Model Checking Logic WCTL with Multi Constrained Modalities on One Clock Priced Timed Automata
  with Shankara Narayanan Krishna, and Chinmay Jain in FORMATS 2009

Teaching

Diwali 2023	COL863	Special Topics in TCS - Bayesian Online Selection
Holi 2023	COL351	Analysis and Design of Algorithms
Diwali 2022	COL106	Data Structures	co-taught with Naveen Garg
Holi 2022	COL756	Mathematical Programming
Diwali 2021	COL202	Discrete Mathematics
Holi 2021	COL352	Theory of Computation
Diwali 2020	COL702	Advanced Data Structures and Algorithms
Holi 2020	COL866	Special Topics in Algorithms - Online Computation

Other Interests

Hiking, Running, Chess, Bridge, Indian Classical Music