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 …

This paper initiates a systematic development of a theory of non-commutative optimization, a
setting which greatly extends ordinary (Euclidean) convex optimization. It aims to unify and …

Alternating minimization heuristics seek to solve a (difficult) global optimization task through
iteratively solving a sequence of (much easier) local optimization tasks on different parts (or …

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 …

We prove that in the geometric complexity theory program the vanishing of rectangular
Kronecker coefficients cannot be used to prove superpolynomial determinantal complexity …

For several classical nonnegative integer functions we investigate if they are members of the
counting complexity class# P or not. We prove# P membership in surprising cases, and in …

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 …