Sampling a random walk is a fundamental primitive in many graph applications. In the streaming model, it is known that sampling an $L$-step random walk on an $n$-vertex directed graph requires $\Omega(n L)$ space, implying that no sublinear-space streaming algorithm exists for general graphs.

We show that sublinear algorithms are ... more >>>

We investigate central questions in complexity theory through the lens of time-bounded Kolmogorov complexity, focusing on $\textit{nondeterministic}$ measures [AKRR03] and their extensions. In more detail, we consider succinct encodings of a string by programs that may be nondeterministic (nK), randomized (rK), or combine both resources – yielding richer notions such ... more >>>

The main theme of this work is to provide a new characterization of the algebraic complexity class VNP. We achieve this via following the two main steps -
- We define a combinatorial variant of the determinant polynomial which we call the colored determinant and show it to be VNP-complete ... more >>>