|
|
|
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
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)
Selected Publications in Conference Proceedings
(in reverse chronological order)
- 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
- Model Checking Logic WCTL with Multi Constrained Modalities on One Clock Priced Timed Automata
with Shankara Narayanan Krishna, and Chinmay Jain in FORMATS 2009
Super-smart Student Collaborators
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 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)
Other Interests
Hiking, Running, Chess, Bridge, Indian Classical Music