Publications
Bandit Online Linear Optimization with Hints and Queries. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
International Conference on Machine Learning (ICML), 2023 [paper]
Efficient Caching with Reserves via Marking. Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua Wang
International Colloquium on Automata Languages and Programming (ICALP), 2023 [paper]
Caching with Reserves. Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua Wang
International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2022 [paper]
Parsimonious Learning-Augmented Caching. Sungjin Im, Ravi Kumar, Aditya Petety, Manish Purohit
International Conference on Machine Learning (ICML), 2022 [arXiv]
Scheduling with Communication Delay in Near-Linear Time. Quanquan Liu, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua Wang
Symposium on Theoretical Aspects of Computer Science (STACS), 2022 [arXiv]
Learning-Augmented Weighted Paging. Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee
Symposium on Discrete Algorithms (SODA), 2022 [arXiv]
Online Knapsack with Frequency Predictions. Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, Manish Purohit
Neural Information Processing Systems (NeurIPS), 2021 [paper]
Logarithmic Regret from Sublinear Hints. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
Neural Information Processing Systems (NeurIPS), 2021 [arXiv]
Revenue Maximization in Transportation Networks. Kshipra Bhalwankar, Kostas Kollias, Manish Purohit
International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2021
Dynamic Balancing for Model Selection in Bandits and RL. Ashok Cutkosky, Christoph Dann, Abhimanyu Das, Claudio Gentile, Aldo Pacchiano, Manish Purohit
International Conference on Machine Learning (ICML), 2021 [paper]
Non-Clairvoyant Scheduling with Predictions. Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, Manish Purohit
Strategy-proof and Envy-free Mechanisms for House Allocation. Priyanka Shende, Manish Purohit
Preprint [arXiv]
Upper Confidence Bounds for Combining Stochastic Bandits. Ashok Cutkosky, Abhimanyu Das, Manish Purohit
Preprint [arXiv]
Scale-free Allocation, Amortized Convexity and Myopic Paging. Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee
Preprint [arXiv]
Power of Hints for Online Learning with Movement Costs. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
International Conference on Artificial Intelligence and Statistics (AISTATS), 2021 [paper]
Online Linear Optimization with Many Hints. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
Neural Information Processing Systems (NeurIPS), 2020 [arXiv]
Online Learning with Imperfect Hints. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
Interleaved Caching with Access Graphs. Ravi Kumar, Manish Purohit, Zoya Svitkina, Erik Vee.
Symposium on Discrete Algorithms (SODA), 2020 [paper]
Efficient Rematerialization for Deep Networks. Ravi Kumar, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua Wang
Matroid Coflow Scheduling. Sungjin Im, Benjamin Moseley, Kirk Pruhs, Manish Purohit.
International Colloquium on Automata Languages and Programming (ICALP), 2019 [paper]
Near Optimal Coflow Scheduling in Networks. Mosharaf Chowdhury, Samir Khuller, Manish Purohit, Sheng Yang, Jie You.
Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019 [arXiv]
Hiring Under Uncertainty. Sreenivas Gollapudi, Manish Purohit, Manish Raghavan.
Semi-Online Bipartite Matching. Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, Erik Vee.
Innovations in Theoretical Computer Science (ITCS), 2019 [arXiv]
Improving Online Algorithms via ML Predictions. Ravi Kumar, Manish Purohit, Zoya Svitkina.
On Maximum Leaf Trees and Connections to Connected Maximum Cut Problems. Rajiv Gandhi, MohammadTaghi Hajiaghayi, Guy Kortsarz, Manish Purohit, Kanthi Sarpatwar.
Information Processing Letters, 2018 [paper]
On Scheduling Co-Flows. Saba Ahmadi, Samir Khuller, Manish Purohit, Sheng Yang.
Integer Programming and Combinatorial Optimization (IPCO), 2017 [paper] [full version] [slides (by Saba Ahmadi)] [slides (by Sheng Yang)]
Brief Announcement: Improved Approximation Algorithms for Scheduling Co-Flows. Samir Khuller, Manish Purohit.
Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016 [paper]
On Correcting Inputs : Inverse Optimization for Online Structured Prediction. Hal Daum ́e III, Samir Khuller, Manish Purohit, Gregory Sanders.
Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2015 [arXiv]
On the Approximability of Digraph Ordering. Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, Rishi Saket.
An Approximation Algorithm for the Connected Maximum Cut Problem. MohammadTaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit, Kanthi Sarpatwar.
European Symposium on Algorithms (ESA), 2015 [arXiv]
Fast Influence-based Coarsening for Large Networks. Manish Purohit, Aditya Prakash, Chanhyun Kang, Yao Zhang, V.S. Subrahmanian.
ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2014 [paper]
Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems. Samir Khuller, Manish Purohit, Kanthi Sarpatwar.
Symposium on Discrete Algorithms (SODA), 2014 [arXiv]
Firewall Placement in Cloud Data Centers. Seungjoon Lee, Manish Purohit, Barna Saha.
Symposium on Cloud Computing (SoCC) (Poster), 2013 [paper]
Betweenness Computation in the Single Graph Representation of Hypergraphs. Rami Puzis, Manish Purohit, V.S.Subrahmanian.
Social Networks, 2013 [paper]
Improved algorithms and analysis for the laminar matroid secretary problem. David Harris, Manish Purohit.
ArXiv, 2013 [arXiv]