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
Demo Data from EDBT 2026 / reviewers in the wild / expert

Dmitry Krachun

dblp:230/7970 · also Dmitrii Krachun · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
0since 2021 · last 2019
0000-0001-9814-1706ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1

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
Computational complexity · 44% Approximation and online algorithms · 44% Graph algorithms and graph theory · 13%

Topics — the 3 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Approximation and online algorithms › approximation algorithms › approximation algorithms for graph problems
max-cut approximation		 0.412019
An optimal space lower bound for approximating MAX-CUT · STOC 2019
Computational complexity › lower bounds › machine model lower bounds
streaming lower bounds		 0.412019
An optimal space lower bound for approximating MAX-CUT · STOC 2019
Graph algorithms and graph theory
graph sparsification		 0.112019
An optimal space lower bound for approximating MAX-CUT · STOC 2019

Methods — techniques the papers use, named apart from their topics

communication complexity · 0.4
YearPublicationVenuePosition
2019 An optimal space lower bound for approximating MAX-CUT
abstract
We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output half of this value as the estimate for the size of the MAX-CUT. On the other extreme, for any fixed є > 0, if one allows Õ(n) space, a (1+є)-approximate solution to the MAX-CUT value can be obtained by storing an Õ(n)-size sparsifier that essentially preserves MAX-CUT value.
Michael Kapralov, Dmitry Krachun
 STOC2