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 …

We show that the problem of deciding positivity of Kronecker coefficients is NP-hard.
Previously, this problem was conjectured to be in P, just as for the Littlewood–Richardson …

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

This article is an expository account of the theory of twisted commutative algebras, which
simply put, can be thought of as a theory for handling commutative algebras with large …

It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially
equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic …

We study a basic algorithmic problem in algebraic geometry, which we call NNL, of
constructing a normalizing map as per Noether's Normalization Lemma. For general explicit …

The GCT program toward the <italic toggle='yes'>P</italic> vs. <italic toggle='yes'>NP</ita
Page 1 98 CoMMuniCATions of The ACM | june 2012 | vol. 55 | no. 6 review articles Doi:10.1145/2184319.2184341 …

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

We prove that the computation of the Kronecker coefficients of the symmetric group is
contained in the complexity class# BQP. This improves a recent result of Bravyi, Chowdhury …

We give a positive combinatorial formula for the Kronecker coefficient gλ µ (d) ν for any
partitions λ, ν of n and hook shape µ (d):=(n− d, 1d). Our main tool is Haiman's mixed …