Siddharth Gupta (सिद्धार्थ गुप्ता)

Postdoctoral Researcher


I am currently a Postdoctoral Researcher at the Department of Computer Science at University of Warwick, UK advised by Professor Ramanujan Sridharan. Before that, I was a Zuckerman Postdoctoral Scholar at the Department of Computer Science at Ben-Gurion University, Israel advised by Professor Meirav Zehavi.

I received my PhD in Computer Science from University of California, Irvine in 2018, advised by Professor David Eppstein and Professor Michael T. Goodrich, and my Master in Mathematics and Bachelor in Computer Science from BITS-Pilani, Goa Campus in 2014, advised by Professor Ankit Agrawal and Professor Tarkeshwar Singh.

Research Interests

My research interests lie in Graph Algorithms and Computational Geometry, more specifically in Parameterized Complexity, Graph Drawing, Approximation Algorithms and, more recently, Fine-Grained Complexity and Combinatorial Reconfiguration.

Publications

(All publications are in alphabetical order of author's last name, except when marked with * )

2022

On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
J. Blum, Y. Disser, A. Feldmann, S. Gupta, A. Zych-Pawlewicz
To appear at IPEC 2022.

Bounding and Computing Obstacle Numbers of Graphs
M. Balko, S. Chaplick, R. Ganian, S. Gupta, M. Hoffmann, P. Valtr, and A. Wolff
To appear at ESA 2022.

Brief Announcement: Distributed Reconfiguration of Spanning Trees
S. Gupta, M. Kumar, and S. Pai
To appear at SSS 2022.

2021

Grid Recognition: Classical and Parameterized Computational Perspectives
S. Gupta, G. Sa’ar, and M. Zehavi
ISAAC 2021. Preprint on arXiv.

Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes (blog)
D. Eppstein, S. Gupta, and E. Havvaei
FCT 2021. Preprint on arXiv.

C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width
G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta
Algorithmica 2021 (special issue on IPEC 2019).
A preliminary version of this article appeared in IPEC 2019.

How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths
M. T. Goodrich, S. Gupta, Hadi Khodabandeh, and Pedro Matias
WADS 2021. Preprint on arXiv.

Multivariate Analysis of Scheduling Fair Competitions
S. Gupta and M. Zehavi
AAMAS 2021. Preprint on arXiv.

2020

Parameterized Complexity of Motion Planning for Snake-Like Robots
S. Gupta, G. Sa’ar, and M. Zehavi
Journal of Artificial Intelligence Research (JAIR), vol. 69.
Invited to the Journal Track of IJCAI 2021.
A preliminary version of this article appeared in IJCAI 2019.

2019

C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width
G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta
IPEC 2019. Preprint on arXiv.
Best Paper Award. Invited to Algorithmica, special issue for IPEC 2019.

Parameterized Complexity of Motion Planning for Snake-Like Robots
S. Gupta, G. Sa’ar, and M. Zehavi
IJCAI 2019. Preprint on arXiv.

Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond
S. Gupta, A. Kosowski, and L. Viennot
ICALP 2019. Preprint on arXiv.

2018

Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity (blog)
G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta
WG 2018. Preprint on arXiv.

2017

Crossing Patterns in Nonplanar Road Networks (blog)
D. Eppstein and S. Gupta
SIGSPATIAL 2017. Preprint on arXiv.

2016

A Topological Algorithm for Determining How Road Networks Evolve Over Time
M. T. Goodrich, S. Gupta, and M. R. Torres
SIGSPATIAL 2016. Preprint on arXiv.

2014

*A New Parallel Algorithm for Two-Pass Connected Component Labeling
S. Gupta, D. Palsetia, M. Patwary, A. Agrawal, and A. Choudhary
MTAAP 2014. Preprint on arXiv.