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

COL202	Discrete Mathematics	Diwali 2021, Diwali 2025
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
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