BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260530T210537Z
UID:Seminar-ACTO-502@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20200205T140000
DTEND:20200205T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Nick Fischer: The Computational Complexity of Plethysm Coefficients\n\nGeometric Complexity Theory (GCT) is an ambitious approach introduced by Mulmuley and Sohoni with the far-away goal to separate algebraic complexity classes (that is, resolving the algebraic analogue of P versus NP). In that setup, a crucial role is played by certain representation-theoretic constants called plethysm coefficients. It is of particular interest to understand the computational hardness of plethysm coefficients, however, there are almost no results of that sort even for the easier problem of deciding positivity of plethysm coefficients.\n\nIn this work we show that deciding positivity of plethysm coefficients is NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both problems remain hard even if the inner parameter of the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed, then the plethysm coefficient can be computed in polynomial time.\n\nThis talk does not require any previous knowledge about representation theory.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=502
LOCATION:
END:VEVENT
END:VCALENDAR