Demo Data from VLDB 2026 / reviewers in the wild / expert
Shane Ferrante
dblp:424/9163
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2026
0009-0002-1044-0117ORCID · reported
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 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 |
Algorithms and data structures · 100% |
Topics — the 2 heaviest of 2, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Algorithms and data structures › data streams › streaming algorithms
maximum directed cut |
1.0 | 1 | 2026 | Half-Approximating Maximum Dicut in the Streaming Setting · STOC 2026 |
Algorithms and data structures › data streams
streaming algorithms |
1.0 | 1 | 2026 | Half-Approximating Maximum Dicut in the Streaming Setting · STOC 2026 |
Methods — techniques the papers use, named apart from their topics
local algorithms · 1.0cut sparsifiers · 1.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Half-Approximating Maximum Dicut in the Streaming SettingabstractWe study streaming algorithms for the maximum directed cut problem. The edges of an n-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With O(n) space, a (1−ε)-approximation can be trivially obtained for any fixed ε > 0 using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., n1−Ω(1)) space. A lower bound of Kapralov and Krachun (STOC’19) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS’23). The same authors later obtained a (1/2−ε)-approximation, assuming that the graph is constant-degree (SODA’25). In this paper, we show that for any ε > 0, a (1/2−ε)-approximation of maximum dicut value can be obtained with n1−Ωε(1) space in *general graphs*. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high- and low-degree vertices, when simulating a suitable local algorithm. Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, Mohammad Saneian |
STOC | 3 |