We investigate algorithms to discover the nonzero coefficients and exponents of an unknown sparse polynomial, provided a way to evaluate the polynomial over any modular ring. This problem has been of interest to the computer algebra community for decades, and its uses include multivariate
polynomial GCD computation, factoring, and sparse polynomial arithmetic. Starting with the early works of Zippel, BenOr and Tiwari, and Kaltofen, one line of investigation has a key advantage in achieving the minimal number of evaluations of the polynomial, and has received considerable attention and improvements over the years. It is closely related to problems in coding theory and exponential analysis. The downside, however, is that these methods are not polynomialtime over arbitrary fields. A separate line of work starting with Garg and Schost and continuing with a few papers by the speaker and coauthors, has developed a different approach that works over any finite field. After years of improvements, the
complexity of both approaches over ZZ[x] is currently the same. They scale well in most aspects except for the degree; the bit complexity in both cases is currently cubic in the bitlengths of the exponents. By careful combination of the techniques in both approaches and a few new tricks, we are now able to overcome this hurdle. We present an algorithm whose running time is softlylinear in the size of the output and performs nearly the minimal number of evaluations of the unknown polynomial. Preliminary
implementation results indicate good promise for practical use when the unknown polynomial has a moderate number of variables and/or large exponents.
Sekundärnavigation / Secondary navigation
Inhaltsbereich / Content
4 Einträge gefunden

05. Dezember15:30  17:00
Ort: 48436AG Algebra, Geometrie und ComputeralgebraDan Roche/US Naval Academy Annapolis: nteger Polynomial Sparse Interpolation with NearOptimal Complexity
Kategorie: AG Algebra, Geometrie und Computeralgebra 
07. Dezember17:00  18:00
Ort: 48436AG Algebra, Geometrie und ComputeralgebraEmilio Rotilio, TU Kaiserslautern: Lie Superalgebras in Physics
Kategorie: AG Algebra, Geometrie und ComputeralgebraThe current understanding of nature finds in the „Standard Model“ the most complete and verified theory (for now). The mathematics it involves heavily relies on Lie theory (Lie groups and Lie algebras). To better describe the universe, phisicists have come up with a „Supersymmetry“ theory (among others). This theory is described in terms of Lie superalgebras. The goal of this talk is to give an overview of which Lie algebras/superalgebras are used in Physics and why they help describing nature.

14. Dezember17:00  18:00
Ort: 48436AG Algebra, Geometrie und Computer AlgebraStefano Sannella/University of Birmingham: Broué's conjecture and perverse equivalences
Kategorie: AG Algebra, Geometrie und ComputeralgebraThe representation theory of a finite group G over a field F of positive characteristic carries many questions that have not been answered yet. Most of them can be stated as global/local conjectures: in various forms, they state that the representation theory of G is somehow controlled by its plocal subgroups. Here we will mostly focus on one of these conjectures, Broué's Abelian Defect Group Conjecture, which might be considered as an attempt to give a structural explanation of what is actually connecting G and its local psubgroups in the abelian defect case. In particular, we explain how the strategy of looking for a perverse equivalence (a specific type of derived equivalence) works successfully in some cases and how this procedure is related to some DeligneLusztig varieties.

21. Dezember17:00  18:00
Ort: 48436AG Algebra, Geometrie und Computer AlgebraPatrick Wegener/TU Kaiserslautern: Hurwitz action in elliptic Weyl groups and coherent sheaves on a weighted projective line
Kategorie: AG Algebra, Geometrie und ComputeralgebraSince 2000 the poset of noncrossing partitions attached to a Coxeter group (independently introduced by Bessis and BradyWatt) has gained a lot of attention from different areas of mathematics. In 2010 Igusa, Schiffler and Thomas showed that there exists an order preserving bijection between this poset and the set of thick subcategories in the derived category of mod(A) generated by an exceptional sequence, where A is a hereditary Artin algebra. Following Happel's classification of hereditary categories, it seems natural to ask if there is an analogous statement when replacing mod(A) by the category of coherent sheaves on a weighted projective line. I will give a short summary on hereditary categories, explain how elliptic Weyl groups show up in this context and then generalize the result of IgusaSchifflerThomas to tubular weighted projective lines. (This is joint work with B. Baumeister and S. Yahiatene.)