REVIEW 1 cited by
Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most $c$ for some $c = (\log n)^{o(1)}$. Previously, the best update time was $\widetilde O(\sqrt{n})$ for any $c > 2$ and $c = O(\log n)$ [Thorup, Combinatorica'07].
Forward citations
Cited by 1 Pith paper
-
TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability
The paper introduces TCS-Bench, a 300-task proof-generation benchmark from top TCS papers, and reports frontier LLM accuracies from 30% to 68% using an automated verifier.
Discussion (0). Continue with ORCID to comment.