1 citations · 1 across the 5 of their papers we have counts for
9 papers
Rectangular Matrix Multiplication in the Low-Bandwidth Model
Chetan Gupta, Jukka Suomela, Hossein Vahidi
We study rectangular matrix multiplication in the low-bandwidth model of distributed computing. There are computers; initially the input matrices are distributed evenly between…
Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
Chetan Gupta, Raghunath Tewari, Vimal Raj Sharma
We show that given an embedding of an genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight pe…
Lossy Catalytic Computation
Chetan Gupta, Rahul Jain, Vimal Raj Sharma +1
A catalytic Turing machine is a variant of a Turing machine in which there exists an auxiliary tape in addition to the input tape and the work tape. This auxiliary tape is initiall…
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
Archit Chauhan, Samir Datta, Chetan Gupta +1
Finding a simple path of even length between two designated vertices in a directed graph is a fundamental NP-complete problem known as the EvenPath problem. Nedev proved in 1999, t…
Fast Dynamic Programming in Trees in the MPC Model
Chetan Gupta, Rustam Latypov, Yannic Maus +6
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in rounds in the massively parallel computation model (MPC), with…
Sparse Matrix Multiplication in the Low-Bandwidth Model
Chetan Gupta, Juho Hirvonen, Janne H. Korhonen +2
We study matrix multiplication in the low-bandwidth model: There are computers, and we need to compute the product of two matrices. Initially computer knows ro…
Dynamic Meta-theorems for Distance and Matching
Samir Datta, Chetan Gupta, Rahul Jain +3
Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [DKMSZ18, DM…
Reachability and Matching in Single Crossing Minor Free Graphs
Samir Datta, Chetan Gupta, Rahul Jain +3
We show that for each single crossing graph , a polynomially bounded weight function for all -minor free graphs can be constructed in Logspace such that it gives nonzero…
Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
Chetan Gupta, Rahul Jain, Raghunath Tewari
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an imp…