Aleksandr Storozhenko
Hi! I am an M.S.E. student in Computer Science at Princeton University, where I am advised by
Pravesh K. Kothari.
Previously, I earned a B.Sc. in Mathematics and Computer Science from École Polytechnique.
I also spent a summer at ETH Zürich as an SSRF research fellow, where I worked with
David Steurer.
I am broadly interested in theoretical computer science.
Here is my CV.
Publications and Preprints
-
Rate-optimal Community Detection near the KS Threshold via Node-robust Algorithms.
With
J. Ding,
Y. Hua,
K. Lindberg,
D. Steurer
(2025).
[arXiv]
[Abstract]
We study community detection in the symmetric $k$-stochastic block model,
where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively.
Our main result is a polynomial-time algorithm that achieves the minimax-optimal misclassification rate
\begin{equation*}
\exp \Bigl(-\bigl(1 \pm o(1)\bigr) \tfrac{C}{k}\Bigr),
\quad \text{where } \quad \qquad C = (\sqrt{pn}-\sqrt{qn})^2,
\end{equation*}
whenever $C \ge K\,k^2\,\log k$ for some universal constant $K$, matching the Kesten-Stigum (KS) threshold up to a $\log k$ factor.
Notably, this rate holds even when an adversary corrupts an $\eta \le \exp\bigl(- (1 \pm o(1)) \tfrac{C}{k}\bigr)$ fraction of the nodes.
To the best of our knowledge, the minimax rate was previously only attainable either via computationally inefficient procedures (Zhang and Zhou, 2015) or via polynomial-time algorithms that require strictly stronger assumptions such as $C \ge K k^3$ (Gao et al., 2017).
In the node-robust setting, the best known algorithm requires the substantially stronger condition $C \ge K k^{102}$ (Liu and Moitra, 2022).
Our results close this gap by providing the first polynomial-time algorithm that achieves the minimax rate near the KS threshold in both settings.
Our work has two key technical contributions:
(1) we robustify majority voting via the Sum-of-Squares framework,
(2) we develop a novel graph bisectioning algorithm via robust majority voting, which allows us to significantly improve the misclassification rate to $1/\mathrm{poly}(k)$ for the initial estimation near the KS threshold.
-
Conway’s Cosmological Theorem and Automata Theory.
With
P. Lairez.
The American Mathematical Monthly, 132(9), 867-882, (2025).
[Journal]
[Abstract]
John Conway proved that every audioactive sequence (a.k.a. look-and-say) decays into a compound of 94 elements, a statement he termed the cosmological theorem. The underlying audioactive process can be modeled by a finite-state machine, mapping one sequence of integers to another. Leveraging automata theory, we propose a new proof of Conway's theorem based on a few simple machines, using a computer to compose and minimize them.
Teaching
Princeton University Graduate Teaching Assistant
COS 324: Introduction to Machine Learning, Spring 2026
COS 240: Reasoning about Computation, Fall 2025
Contact
Email: as7649@princeton.edu
Office Hours (CS 003): Monday, 6-8pm