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

List recovery of error-correcting codes has emerged as a fundamental notion with broad applications across coding theory and theoretical computer science. Folded Reed-Solomon (FRS) and univariate multiplicity codes are explicit constructions which can be efficiently list-recovered up to capacity, namely a fraction of errors approaching $1-R$ where $R$ is the ... more >>>