|
Ashish Chiplunkar
Department of Computer Science and Engineering
|
News
My paper "Weighted k-Server Admits an Exponentially Competitive Algorithm", co-authored with Adithya Bijoy and Ankit Mondal (my B.Tech. project students), has been accepted at SODA 2026. Adithya and Ankit also received the Suresh Chandra Memorial Award for best B.Tech. project in the academic year 2024-25. The paper gives a randomized algorithm for the weighted k-server problem on uniform metrics with competitive ratio exp(O(k2)). This beats the best previously known bound which was doubly exponential in k. This is close to being the best possible, because it is known that every such algorithm must have competitive ratio Ω(2k). The preprint of this result is available on the arXiv.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: ESA 2018, FSTTCS 2021, FSTTCS 2025
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)- Weighted k-Server Admits an Exponentially Competitive Algorithm
with Adithya Bijoy and Ankit Mondal, to appear in SODA 2026 - 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
Ongoing
Surbhi Rajput - 2022CSY7519 (MS(R)), Rittik Dey 2024CSZ8007 (PhD)2025
Adithya Bijoy - 2021CS10571 (BTP1 + BTP2) and Ankit Mondal - 2021CS10229 (BTP1): Adithya and Ankit solved an open problem nine years older than themselves. They designed a randomized algorithm for the weighted k-server problem on uniform metrics with competitive ratio exp(O(k2)). This paper has been accepted in SODA2026, a top tier conference. The best algorithmic bound known previously was doubly exponential in k. Along with the lower bound proved by Nikhil Ayyadevara in 2021 (see below), we can now infer that the randomized competitive ratio of the problem is indeed singly exponential in k -- no better, no worse. Additionally, Adithya and Ankit initiated the study of the weighted k-server problem on certain classes of non-uniform metric spaces. Their project won the Suresh Chandra Memorial Award for the best B.Tech. project.Ankit Mondal won the President's Gold Medal for his exceptional academic performance.
Adithya Bijoy is currently a PhD student at National University of Singapore.
Anant Lunia - 2021CS10068 (BTP1), Manpreet Singh - 2021CS10070 (BTP1), Mihir Kaskhedikar - 2021CS10551 (BTP1)
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
| COL1002 | Discrete Mathematics | Holi 2026 (co-taught with Nikhil Balaji and Amitabha Bagchi) |
| 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