Demo Data from VLDB 2026 / reviewers in the wild / expert
Ishan Chakraborty
dblp:436/6126
· DBLP profile ↗
1ranked-venue papers
1as first author
1since 2021 · last 2026
0009-0003-9931-878XORCID · reported
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 1 first-author · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Approximation and online algorithms · 38% Computational complexity · 31% Distributed computing theory · 19% |
Topics — the 8 heaviest of 8, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Approximation and online algorithms
approximation algorithms |
1.0 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Approximation and online algorithms
FPT approximation |
1.0 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Computational complexity
parameterized complexity |
1.0 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Distributed computing theory › distributed complexity
time-approximation trade-offs |
1.0 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Computational complexity › parameterized complexity
feedback vertex set |
0.3 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Graph algorithms and graph theory
graph cut |
0.3 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Computational complexity
hitting set |
0.3 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Graph algorithms and graph theory › graph cut
multiway cut |
0.3 | 1 | 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026 |
Methods — techniques the papers use, named apart from their topics
randomized branching · 1.0random walk · 1.0LP relaxation · 1.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random WalksabstractIn the last decade, FPT approximation has witnessed tremendous growth, with the development of several powerful upper- and lower-bound techniques. Within this framework, a newly emerging direction focuses on problems that admit algorithms with running time of the form ck · nO(1) for some constant c. This line of inquiry naturally leads to the notion of time–approximation ratio trade-offs (or time-ratio trade-offs): by relaxing the approximation guarantee in a controlled manner, one can improve the exponential dependence on the parameter in the running time. The contribution of this paper is threefold: (i) a formal language for parameterized randomized branching algorithms (called Oracle Subset Problems); (ii) a meta-algorithm applicable to all problems expressible in this language; and (iii) new time–ratio trade-offs obtained by instantiating the framework on fundamental problems, including Above-Guarantee Vertex Cover (parameterized by excess over the LP lower bound), Odd Cycle Transversal, Node Multiway Cut, Subset/Group Feedback Vertex Set, Min-Weight d-SAT, and Matroid-Rank d-Hitting Set (where solution is measured by the rank in a matroid accessible via an independence oracle), among others. Our applications demonstrate substantially broader applicability. For the first time, they apply to cut problems, problems with parity constraints (Odd Cycle Transversal), “complex” cycle hitting problems (hitting all cycles whose length mod73 is non-zero), and even a generalization where the user specifies the subset of vertices such that only the cycles passing through that subset of vertices should be hit. These results are obtained by developing time–ratio trade-offs for two meta-algorithms, expressed in our language: (i) the biased-graph framework [Wahlström, SODA 2017; Lee and Wahlström, arXiv 2020], and (ii) the Vertex Cover above LP framework [Lokshtanov et al., TALG 2014]. Ishan Chakraborty, Tanmay Inamdar 0002, Ariel Kulik, Madhumita Kundu, Saket Saurabh 0001 |
STOC | 1 |