Álvaro Gutiérrez

Algebraic functions in log-space

Countless constants in algebra are positive by construction, and hard to compute in general. A combinatorial understanding of these often unlocks theoretical methods and computational tools. A philosophy of Mulmuley (in his quest towards P vs NP) and later flagshipped by Pak equates the notions of "combinatorial interpretation" with a certain computational complexity class #P (poly-time verifiable).

We study algebraic functions from representation theory, number theory, and enumerative combinatorics in a different class #L (log-space verifiable), which is as good of a candidate to formalise "combinatorial interpretation". Instead, we propose a new candidate formalisation.