Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Ishan Chakraborty

dblp:436/6126 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Approximation and online algorithms
approximation algorithms
1.012026
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026
Approximation and online algorithms
FPT approximation
1.012026
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026
Computational complexity
parameterized complexity
1.012026
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026
Distributed computing theory › distributed complexity
time-approximation trade-offs
1.012026
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026
Computational complexity › parameterized complexity
feedback vertex set
0.312026
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026
Graph algorithms and graph theory
graph cut
0.312026
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026
Computational complexity
hitting set
0.312026
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks · STOC 2026
Graph algorithms and graph theory › graph cut
multiway cut
0.312026
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
YearPublicationVenuePosition
2026 Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks
abstract
In 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
STOC1