|
01/31 5:00pm |
BLOC 302 |
M. Varbaro |
Singularities of varieties with a squarefree Gröbner degeneration
Let S be a polynomial ring over a field, I a homogeneous ideal, X the projective variety defined by I, and < a monomial order on S. Assume that in_<(I) is squarefree. When < is the revlex order, the smoothness of X forces S/I to be Cohen-Macaulay with negative a-invariant (hence a (F)-rational singularity). We will discuss on the problem wether this phenomenon can happen in general; this is not clear even when X is a curve and < is lex. In this case, rephrasing the question it asks: if X is a smooth projective curve admitting some embedding for which the defining ideal has a squarefree initial ideal, then X must have genus 0. In this talk we will largely discuss this problem, giving some evidence for it and explaining why it is difficult to show it in general. |
|
03/03 3:00pm |
BLOC 302 |
R. Oliveira U. Waterloo |
Primes via Zeros: interactive proofs for testing primality of natural classes of ideals
A central question in mathematics and computer science is the question of determining whether a given ideal I is prime, which geometrically corresponds to the zero set of $I$, denoted $Z(I)$, being irreducible.
The current best algorithms for the ideal primality testing problem require, in the worst-case, exponential space (i.e., in EXPSPACE).
This state of affairs has prompted intense research on the computational complexity of this problem even for special and natural classes of ideals.
Notable classes of ideals are the class of radical ideals, complete intersections (and more generally Cohen-Macaulay ideals).
For radical ideals, the current best upper bounds are given by (Buergisser & Scheiblechner, 2009), putting the problem in PSPACE.
For complete intersections, the primary decomposition algorithm of (Eisenbud, Huneke, Vasconcelos 1992) coupled with the degree bounds of (Dickenstein et al 1991), puts the ideal primality testing problem in exponential time (EXP).
In these situations, the only known complexity-theoretic lower bound for the ideal primality testing problem is that it is coNP-hard for the classes of radical ideals, and equidimensional Cohen-Macaulay ideals.
In this work, we significantly reduce the complexity-theoretic gap for the ideal primality testing problem for the important families of ideals (namely, *radical ideals* and *equidimensional Cohen-Macaulay ideals*).
For these classes of ideals, assuming the Generalized Riemann Hypothesis, we show that primality testing can be efficiently verified (also by randomized algorithms).
This significantly improves the upper bound for these classes, approaching their lower bound, as the primality testing problem is coNP-hard for these classes of ideals.
This talked is based on joint work with Abhibhav Garg and Nitin Saxena. |