Wednesday, September 9, 2009 at 4:30 PM in SAS 4201
Michael Singer, NCSU
Algebraic Relations Among Solutions of Linear Difference Equations
The Fibonacci ${F_n}$ numbers are defined by a simple difference equation
[F_{n+2} - F_{n+1} - F_n = 0, F_0 = F_1 = 1.]
How does one discover that the Fibonacci numbers satisfy Cassini's Identity
[ F_{n+2} F_n - F_{n+1}^2 = (-1)^n?]
In 2008, Kauers and Zimmermann published an algorithm that allows one to find the ideal of polynomial relations among sequences defined by linear difference equations with constant coefficients. We will present an alternate algorithm that generalizes to deal with sequences defined by linear difference equations with polynomial coefficients.Wednesday, September 16, 2009 at 4:30 PM in SAS 4201
Wen-shin Lee, University of Antwerp
Extracting Numerical Factors of Multivariate Polynomials from Taylor Expansions and Beyond
We present a method to extract factors of multivariate polynomials
with complex coefficients in floating point arithmetic. We establish
the connection between the reciprocal of a multivariate polynomial and
its Taylor expansion. Since the multivariate Taylor coefficients are
determined by the irreducible factors of the given polynomial, we
reconstruct the factors from the Taylor expansion. As each irreducible
factor, regardless of its multiplicity, can be separately extracted,
our method can lead toward the complete numerical factorization of
multivariate polynomials.
Besides the numerical factorization, we plan to further comment on a
recently revealed link between Pade approximation theory and
polynomial algebra, which may provide us with an additional tool to
extract algebraic structure from numerical partial data.
This is joint work with Annie Cuyt at University of Antwerp in Belgium.Wednesday, September 23, 2009 at 4:30 PM in SAS 4201
Dan Bates, Colorado State University
A numerical shortcut for symbolic computation in algebraic geometry
Many problems in algebraic geometry can be studied via symbolic computation, typically based on some sort of Groebner basis computation. Another option in many cases is numerical computation, typically rooted in homotopy continuation. Symbolic methods provide exact results but suffer from some complexity issues. Numerical methods are often more efficient but provide inexact output.
The focus of this talk is a new technique (joint with J. Hauenstein, T. McCoy, C. Peterson, and A. Sommese) to move from exact input through inexact computations to exact output. In particular, given an ideal of polynomials with rational coefficients, standard numerical methods will produce witness points (approximations of generic points) on each irreducible component of the algebraic set associated to the ideal. Given that information, lattice basis reduction algorithms such as LLL can be used to find generators of the ideals corresponding to each irreducible component. These results can then be verified by (less expensive) symbolic methods. It appears that this new method will be handy in a number of situations, at least a few of which will be discussed.Wednesday, September 30, 2009 at 4:30 PM in SAS 4201
Eunjeong Lee, NCSU
Pairing computation for cryptography (Overview and Recent Progress)
A pairing is a bilinear map among groups, whose theory was developed
by Weil and Tate in the context of algebraic geometry.
Later it was discovered that the pairing could be used for cryptography.
Since then, intensive research has been carried out on the topic.
By now the pairing is considered to be one of the most important
tools in cryptography.
In this talk, we provide an introductory overview on
* what pairings are,
* how they can be used for cryptography,
* two celebrated pairings ("Tate" and "Ate")
We will also present an improved pairing (which we call "R-Ate"),
which turns to be optimal on certain elliptic curves.Wednesday, October 7, 2009 at 4:30 PM in SAS 4201
Mohab Safey El Din, Pierre et Marie Curie University & LIP6 INRIA Paris-Rocquencourt
Variant Quantifier Elimination: Algorithm and Application
Joint work with Hoon Hong, NCSU, USA
We study a variant of the real quantifier elimination problem (QE). The variant problem requires the input to satisfy a certain extra condition, and allows the ouput to be almost equivalent to the input. In a sense, we are strengthening the pre-condition and weakening the post-condition of the standard QE problem. The motivation/rationale for studying such a variant QE problem is that many quantified formulas arising in applications do satisfy the extra conditions. Furthermore, in most applications, it is sufficient that the ouput formula is almost equivalent to the input formula. Thus, we propose to solve a variant of the initial quantifier elimination problem. We present an algorithm (VQE), that exploits the strengthened pre-condition and the weakened post-condition. The main idea underlying the algorithm is to substitute the repeated projection step of CAD by a single projection without carrying out a parametric existential decision over the reals. We find that the algorithm VQE can tackle important and challenging problems, such as numerical stability analysis of the widely-used MacCormack's scheme. The problem has been practically out of reach for standard QE algorithms in spite of many attempts to tackle it. However the current implementation of VQE can solve it in about 1 day.Wednesday, October 14, 2009 at 4:30 PM in SAS 4201
Mohab Safey El Din, ierre et Marie Curie University & LIP6 INRIA Paris-Rocquencourt
A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
Joint work with Eric Schost, Univeristy of Western Ontario, Canada
We consider the problem of constructing roadmaps of real algebraic
sets. This problem was introduced by Canny to answer connectivity
questions and solve motion planning problems. Given $s$ polynomial
equations with rational coefficients, of degree $D$ in $n$ variables,
Canny's algorithm has a Monte Carlo cost of $s^nlog(s) D^{O(n^2)}$
operations in $mathbb{Q}$; a deterministic version runs in time $s^n
log(s) D^{O(n^4)}$. A subsequent improvement was due to Basu,
Pollack and Roy, with an algorithm of deterministic cost $s^{d+1}
D^{O(n^2)}$ for the more general problem of computing roadmaps of a
semi-algebraic set ($d le n$ is the dimension of an associated
object).
We give a probabilistic algorithm of complexity $(nD)^{O(n^{1.5})}$
for the problem of computing a roadmap of a closed and bounded
hypersurface $V$ of degree $D$ in $n$ variables, with a finite number
of singular points. Even under these extra assumptions, no previous
algorithm featured a cost better than $D^{O(n^2)}$.
Wednesday, October 21, 2009 at 4:30 PM in SAS 4201
Sebastian Pauli, UNC Greensboro
The Distribution of the Zeros of the Derivatives of the Riemann Zeta Function
We investigate the distribution of the zeros of the derivatives of the Riemann Zeta function and find unexpected regularity in their distribution. For higher derivatives we give rectangular regions, which contain exactly one zero.Wednesday, October 28, 2009 at 4:30 PM in SAS 4201
Eunjeong Lee, NCSU
"Curious" Graphs arising from Cyclotomic Polynomials
In this talk, we investigate puzzling graphs
arising from polynomial operations on cyclotomic polynomials.
Specifically, let Phi_n(x) be a cyclotomic polynomial of n-th order.
Let d be the degree of the remainder of x^i when divided by Phi_n(x).
Of course d depends on i and n.
For a fixed n, imagine the graph of d versus i.
The graphs exhibit intriguing patterns.
We will make several observations on the patterns,
make a few conjectures, and prove some of them,
still leaving many as open problems for the curious minds.
The research was initially motivated by complexity analysis
of a state-of-the-art crypto-system,
where the above question naturally arose.
We also feel that the question is interesting on its own,
because it seems to provide a channel through which
one could gain a deeper understanding on the relations
among the notions such as sparsity and remaindering defects
for cyclotomic polynomials.Wednesday, November 4, 2009 at 4:30 PM in SAS 4201
Seth Sullivant, NCSU
Identifiability of phylogenetic mixture models
A statistical model is generically identifiable if the map
from parameters to probability distributions is generically one-to-one. We
show that tree parameters of two-tree phylogenetic mixture models are
generically identifiable for the Jukes-Cantor and Kimura 2 parameter
models and verify computationally that the stochastic parameters are
identifiable.
These provide the first positive results on identifiability of
phylogenetic mixture models with different trees. Proofs rely on a
combination of algebraic geometry, combinatorics, and symbolic
computation.
I will spend most of the talk explaining the background of phylogenetic
models, mixture models, and the identifiability problem. Then I will try
to highlight some algebraic surprises that arise in the proofs.Wednesday, November 18, 2009 at 4:30 PM in SAS 4201
Sonja Petrovic, University of Illinois, Chicago
Markov degrees of hierarchical models arising from Betti numbers of Stanley-Reisner ideals
There are two seemingly unrelated classical objects associated to a
simplicial complex: a hierarchical model and a Stanley-Reisner ring.
A hierarchical model gives rise to a toric ideal, a relationship that
is a staple of algebraic statistics. The degrees of generators of this
ideal are dubbed "Markov degrees" and encode the complexity of the
model.
In turn, a Stanley-Reisner ideal is a monomial ideal whose algebraic
properties are encoded by the combinatorial properties of the complex.
Betti numbers encode ranks of free modules in a minimal free
resolution of the Stanley-Reisner ring, a central object in
commutative algebra.
In this talk, I will introduce all of these concepts, and present a
recent result which explores a first connection between Markov degrees
of the model and Betti numbers of the Stanley-Reisner ideal.
As an application of the main theorem, we recover a result of Froberg
which classifies simplicial complexes with linear resolutions.
This talk is based on joint work with Erik Stokes, preprint available
at arXiv:0910.1610v1Wednesday, December 2, 2009 at 4:30 PM in SAS 4201
Joseph Burdis, NCSU
Equivalence of Curves Under Generalized Weak Perspective Projection
TBA
You can add or remove yourself from a seminar mailing list by visiting this link.
Seminar Organizer: Agnes Szanto