VLDB 2026 Research / reviewers in the wild / expert
Sahiba
dblp:413/7070
· DBLP profile ↗
2ranked-venue papers
0as first author
2since 2021 · last 2026
0009-0009-7271-2406ORCID · reported
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | The Parameterized Complexity of Maximum Span on Natural Matroid ClassesabstractWe study Maximum Span, motivated by the recent Maximum Span Hypothesis of Karthik and Khot [SODA 2025], which suggests strong parameterized intractability for finding large structured subsets in vector spaces. Formally, given a matrix M and integers k and t, the task is to decide whether there exists a linearly independent set S of at most k columns such that at least t additional columns of M lie in span(S). Equivalently, the goal is to identify a low-rank witness whose span covers many input columns. We initiate a systematic study of the parameterized complexity of Maximum Span on natural matroid classes, revealing a diverse complexity landscape. We first show that the problem is polynomial-time solvable on laminar matroids, via a dynamic program over the laminar tree. In sharp contrast, on graphic matroids the problem is W[1]-hard parameterized by k+t, and, assuming Gap-ETH, admits no f(k)⋅ n^𝒪(1)-time k^o(1)-approximation. On cographic matroids, we show that the problem is equivalent to deleting at most k+t edges so as to create at least t+1 connected components; this yields fixed-parameter tractability parameterized by k+t, and W[1]-hardness parameterized by t. On transversal matroids, using a Hall-type interpretation, we prove W[1]-hardness parameterized by k+t. For strict gammoids, we develop a separator-based formulation. We prove W[1]-hardness parameterized by k+t, give an XP algorithm parameterized by t, and obtain FPT 2^k-approximation algorithms in both the directed and undirected settings. For general gammoids, we establish W[1]-hardness parameterized by k+t, NP-hardness already for t = 1, and an XP algorithm parameterized by k. Together, these results give a detailed parameterized complexity map for Maximum Span across fundamental matroid classes, ranging from polynomial-time solvability to fixed-parameter algorithms, XP algorithms, approximation algorithms, and strong hardness. Madhumita Kundu, Ashutosh Rai 0001, Sahiba, Saket Saurabh 0001 |
MFCS | 3 |
| 2025 | Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, Saket Saurabh 0001 |
MFCS | 5 |