A recent manuscript of OpenAI proves that the exponent of matrix multiplication satisfies $\omega\le9/4$. We give an elementary, self-contained proof of this bound. We follow the ideas of the original manuscript, but implement them differently to obtain explicit algorithms. Specifically, for every $\varepsilon>0$, we give a matrix multiplication algorithm with ... more >>>

One of the central questions in space complexity is whether nondeterministic logspace computations (NL) can be simulated in unambiguous logspace (UL). A stronger notion, reach unambiguity (RUL $\subseteq$ UL $\cap$ coUL), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph ... more >>>

In this work, we design knowledge compilation languages for quantified Boolean formulas (QBFs), with a particular focus on model counting. We introduce various languages in increasing order of their power of representation, starting from a simple tree-based structure, and extending it to DAGs for a more efficient representation. We study ... more >>>