Nikhil Kumar

About Me

I am currently a Postdoctoral Researcher in the Combinatorics and Optimization Group at the University of Waterloo. Prior to this, I was a Postdoctoral Researcher in the Algorithm Engineering Group at the Hasso Plattner Institute (HPI), hosted by Prof. Tobias Friedrich. I completed my B.Tech and M.Tech degrees in Computer Science and Engineering at IIT Delhi in 2014, and earned my Ph.D. there in 2020 under the supervision of Prof. Naveen Garg.

My research interests are in Theoretical Computer Science, with a focus on Combinatorial Optimization and Approximation Algorithms.

Publications

• Almost Tight Additive Guarantees for k-Edge-Connectivity
  with Chaitanya Swamy
  FOCS 2025
• Improved Lower Bounds on Multiflow-Multicut Gaps
  with Sina Kalantarzadeh
  APPROX 2025
• Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique
  with JJ Nan and Chaitanya Swamy
  ESA 2025
• Unsplittable Multicommodity Flows in Outerplanar Graphs
  with David Aleman-Espinosa
  IPCO 2025
• Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
  with Syamantak Das and Daniel Vaz
  MFCS 2024
• Optimal Padded Decomposition For Bounded Treewidth Graphs
  with Arnold Filtser, Tobias Friedrich, Davis Issac, Hung Le, Nadym Mallek, and Ziena Zeif
• Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
  with Tobias Friedrich, Davis Issac, Nadym Mallek, and Ziena Zeif
  STOC 2023
• An Approximate Generalization of the Okamura-Seymour Theorem
  FOCS 2022
• A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs
  with Davis Issac, Nadym Mallek, and Ziena Zeif
  APPROX 2022
• Skeletons and Minimum Energy Scheduling
  with Antonios Antoniadis and Gunjan Kumar
  ISAAC 2021
• Multicommodity Flows in Planar Graphs with Demands on Faces
  ISAAC 2020
• Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
  with Naveen Garg
  ESA 2020
• Integer Plane Multiflow Maximisation: One-Quarter-Approximation and Gaps
  with Naveen Garg and András Sebő
  IPCO 2020 (Journal: Mathematical Programming)
• A Constant Factor Approximation for Capacitated Min-Max Tree Cover
  with Syamantak Das and Lavina Jain
  APPROX 2020
• Parallel Machine Scheduling to Minimize Energy Consumption
  with Antonios Antoniadis, Naveen Garg, and Gunjan Kumar
  SODA 2020
• Some Problems Concerning the Frobenius Number for Extensions of an Arithmetic Progression
  with Sanjit Singh Batra and Amitabha Tripathi
  The Ramanujan Journal
• On a Linear Diophantine Problem Involving the Fibonacci and Lucas Sequences
  with Sanjit Singh Batra and Amitabha Tripathi
  Integers: Electronic Journal of Combinatorial Number Theory