BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Markus Bläser (Saarland University)
DTSTART:20201020T171500Z
DTEND:20201020T174500Z
DTSTAMP:20260423T023012Z
UID:LA-CoCo/6
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/LA-CoCo/6/">
 Variety Membership Testing\, Algebraic Natural Proofs\, and Geometric Comp
 lexity Theory</a>\nby Markus Bläser (Saarland University) as part of LA C
 ombinatorics and Complexity Seminar\n\n\nAbstract\nWe study the variety me
 mbership testing problem in the case when the variety is given as an orbit
  closure and the ambient space is the space of all $3$-tensors. The first 
 variety that we consider is the slice rank variety\, which consists of all
  $3$-tensors of slice rank at most $r$. We show that the membership testin
 g problem for the slice rank variety is <b>NP</b>-hard. While the slice ra
 nk variety is a union of orbit closures\, we define another variety\, the 
 minrank variety\, expressible as a single orbit closure. We also prove the
  <b>NP</b>-hardness of membership testing in the minrank variety\, establi
 shing the <b>NP</b>-hardness of the orbit closure containment problem for 
 $3$-tensors.\n\nAlgebraic natural proofs were recently introduced by Forbe
 s\, Shpilka and Volk and independently by Grochow\, Kumar\, Saks and Saraf
 . We prove that there are no polynomial algebraic natural proofs for testi
 ng membership in the slice rank and minrank variety unless <b>coNP</b> is 
 a subset of exists-<b>BPP</b>.\n\nThe talk is aimed at the general audienc
 e.\n
LOCATION:https://researchseminars.org/talk/LA-CoCo/6/
END:VEVENT
END:VCALENDAR