VLDB 2026 Research / reviewers in the wild / expert
Yakov Shalunov
dblp:365/8131
· DBLP profile ↗
2ranked-venue papers
2as first author
2since 2021 · last 2026
0009-0005-3865-4872ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 first-author · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Improved Bounds on the Space Complexity of Circuit EvaluationabstractWilliams (STOC 2025) recently proved that time-$t$ multitape Turing machines can be simulated using $O(\sqrt{t \log t})$ space using the Cook-Mertz (STOC 2024) tree evaluation procedure. As Williams notes, applying this result to fast algorithms for the circuit value problem implies an $O(\sqrt{s} \cdot \mathrm{polylog}\; s)$ space algorithm for evaluating size $s$ circuits. In this work, we provide a direct reduction from circuit value to tree evaluation without passing through Turing machines, simultaneously improving the bound to $O(\sqrt{s \log s})$ space and providing a proof with fewer abstraction layers. This result can be thought of as a "sibling" result to Williams' for circuit complexity instead of time; in particular, using the fact that time-$t$ Turing machines have size $O(t \log t)$ circuits, we can recover a slightly weakened version of Williams' result, simulating time-$t$ machines in space $O(\sqrt{t} \log t)$. Yakov Shalunov |
CCC | 1 |
| 2024 | Leakage-Resilient Hardness Equivalence to Logspace DerandomizationabstractEfficient derandomization has long been a goal in complexity theory, and a major recent result by Yanyi Liu and Rafael Pass identifies a new class of hardness assumption under which it is possible to perform time-bounded derandomization efficiently: that of ''leakage-resilient hardness.'' They identify a specific form of this assumption which is $\textit{equivalent}$ to $\mathsf{prP} = \mathsf{prBPP}$. In this paper, we pursue an equivalence to derandomization of $\mathsf{prBP{\cdot}L}$ (logspace promise problems with two-way randomness) through techniques analogous to Liu and Pass. We are able to obtain an equivalence between a similar ''leakage-resilient hardness'' assumption and a slightly stronger statement than derandomization of $\mathsf{prBP{\cdot}L}$, that of finding ''non-no'' instances of ''promise search problems.'' Yakov Shalunov |
MFCS | 1 |