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)

• Trading Prophets: How to Trade Multiple Stocks Optimally
  with Surbhi Rajput and Rohit Vaish, in SOSA 2025
• A Decomposition Approach to the Weighted k-server Problem
  with Nikhil Ayyadevara and Amatya Sharma, in FSTTCS 2024
• Prophet Inequality: Order selection beats random order
  with Archit Bubna, 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

Super-smart Student Collaborators

2024

Divyanshu Agarwal - 2020CS10343 (BTP1 + BTP2), Utsav Jaiswal - 2020CS10402 (BTP1 + BTP2), Soumil Aggarwal - 2020CS10392 (BTP1), Rishabh Dhiman - 2020CS10837 (BTP1)

2023

Archit Bubna - 2019CS10331 (BTP1 + BTP2): Archit proved that the prophet problem with order selection has a strictly better competitive ratio than the prophet problem with random arrival order. This work was published in EC2023, a top tier conference. Archit completed his graduation requirements with a perfect 10 CGPA and won the President's Gold Medal.

2022

Nikhil Ayyadevara - 2017CS10330 (MTP), Galav Kapoor - 2018CS10332 (BTP1), Kalash Gupta - 2018CS10346 (BTP1), Navneel Singhal - 2018CS10360 (BTP1)

2021

Nikhil Ayyadevara - 2017CS10330 (BTP1): Nikhil proved that the randomized competitive ratio of the weighted k-server problem is at least exponential in k, improving the previously known lower bound which was only ln(k). This work was published in ESA2021, a top tier conference. Nikhil is currently a Ph.D. student at University of Michigan.
Saumya Gupta - 2016ME10689 (MTP)

Teaching

COL866	Special Topics in Algorithms	Holi 2020 (Online Computation), Holi 2025 (Matroid Theory)
COL100	Intro. to Computer Science	Diwali 2024 (co-taught with Sorav Bansal)
COL352	Theory of Computation	Holi 2021, Holi 2024
COL863	Special Topics in TCS	Diwali 2023 (Bayesian Online Selection)
COL351	Analysis and Design of Algorithms	Holi 2023*
COL106	Data Structures	Diwali 2022 (co-taught with Naveen Garg)
COL756	Mathematical Programming	Holi 2022
COL202	Discrete Mathematics	Diwali 2021
COL702	Advanced Data Structures and Algorithms	Diwali 2020

* Recipient of the institute's Teaching Excellence Award

Other Interests

Hiking, Running, Chess, Bridge, Indian Classical Music