BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Smoothing the degree of regularity for polynomial systems
DTSTART:20261103T130000Z
DTEND:20261103T143000Z
DTSTAMP:20261104T010300Z
UID:indico-event-17648@indico.math.cnrs.fr
DESCRIPTION:Speakers: Melvin Seitner\n\nThe complexity of many algebraic a
 lgorithms for solving non-linear polynomial systems of equations over fini
 te fields such as the XL (eXtended Linearization) algorithm or variants of
  the F4/F5  algorithms is directly determined by the so called degree of 
 regularity. In essence\, we need toform a Macaulay matrix at this degree\,
  which can be thought of as the linearization of monomial multiples of the
  polynomials from the problem instance\, and then solve the obtained linea
 r system.\nAlthough the degree of regularity guarantees we can solve the s
 ystem\, it is a rather coarse parameter. This means that sometimes\, we en
 d up with a heavily overdetermined Macaulay matrix in order to provably de
 al with underdeterminedness in a lower degree. To reduce this coarseness\,
  and thus avoid unnecessary high time and memory complexity\, we propose a
  technique for ``smoothing'' the degree of regularity that can be seen as 
 operating at a degree in-between two integer values. Instead of the full M
 acaulay matrix\, we consider specific submatrices that we show are suffici
 ent to solve the given system. Under a mild assumption that generalizes th
 e notion of semi-regularity\, which we experimentally verify for a range o
 f parameters\, we show that our approach smooths the complexity of XL.\nTr
 avail en commun avec Samuel Jaques\, Lars Ran et Simona Samardjiska.\n\nht
 tps://indico.math.cnrs.fr/event/17648/
LOCATION:XR203 (XLIM)
URL:https://indico.math.cnrs.fr/event/17648/
END:VEVENT
END:VCALENDAR