The shadow of the hidden combinatorics of completely positive operators on Polynomial Identity Testing
Josué Tonelli-Cueto (TU Berlin)
Under the name "Polynomial Identity Testing" (PIT), one has a variety of decision problems of which the simplest one is to decide if a given formula represents the zero polynomial. These problems have a fundamental role in complexity theory, where their solution is linked to new lower bounds, and in computational algebra, where they play a fundamental role in the derandomization of some probabilistic algorithms.
In this talk, we introduce the PIT, sketch how some of its instances relate and describe how one of the versions of the PIT turns out to be a quantum generalization of the perfect matching existence decision problem for bipartite graphs. More concretely, we show how this problem is encoded in the combinatorics of completely positive operators between psd cones, how there is a part of this combinatorics that cannot be read from how these operators act on the face lattices of psd cones and how this hidden combinatorics is the major obstacle to the solution of this instance of the PIT. This is part of my Master's thesis which was supervised by P. Bürgisser.
Talk given during the 5th BMS Student Conference on the 23rd of February of 2017.