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 >>>

Small set expansion in high dimensional expanders is of great importance, e.g., towards proving cosystolic expansion, local testability of codes and constructions of good quantum codes.

In this work we improve upon the state of the art results of small set expansion in high dimensional expanders. Our improvement is either ... more >>>