We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker
coefficients in the context of the geometric complexity theory program to prove a variant of …

An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing
the polynomial P using only additions and multiplications. It is a syntactic model of …

Abstract In 1950, John Nash sent a remarkable letter to the National Security Agency, in
which—seeking to build theoretical foundations for cryptography—he all but formulated what …

The permanent versus determinant conjecture is a major problem in complexity theory that is
equivalent to the separation of the complexity classes $\mathrm {VP} _ {\mathrm {ws}} $ and …

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by
Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential …

Kostka, Littlewood-Richardson, Kronecker, and plethysm coefficients are fundamental
quantities in algebraic combinatorics, yet many natural questions about them stay …

We introduce a new and natural algebraic proof system, whose complexity measure is
essentially the algebraic circuit size of Nullstellensatz certificates. This enables us to exhibit …

The existence of string functions, which are not polynomial time computable, but whose
graph is checkable in polynomial time, is a basic assumption in cryptography. We prove that …

Algebraic Combinatorics originated in Algebra and Representation Theory, studying their
discrete objects and integral quantities via combinatorial methods which have since …

We provide a thorough introduction to Geometric Complexity Theory, an approach towards
computational complexity lower bounds via methods from algebraic geometry and …