Math 648 (section 600): Introduction to Algorithmic Algebraic Geometry

Prof. J. Maurice Rojas

Handouts, Homework, and Other Announcements

9. Monday, Nov. 9, 2009: Here is a list of papers which are simultaneously references to what we've done recently, references to what we're about to do, and references upon which you can build a final presentation:
- For those of you interested in number theory...
  - ``Derandomization of Sparse Cyclotomic Integer Zero Testing'' is a very nice paper by Qi Cheng that easily implies that deciding whether a sparse polynomial vanishes at a Dth root of unity is doable in NP. In particular, the paper is short, elementary, and a much better read than a later follow-up paper with other authors...
  - ``Multivariable polynomial injections on rational numbers'' is a very nice paper by Bjorn Poonen on a question of Harvey Friedman: given a number field k, can you find a polynomial f in k[x,y] with the induced map kxk->k an injection? Poonen shows that the truth of a famous conjecture on rational points (part of the Bombieri-Lang Conjecture) implies that such polynomials can be found easily.
  - ``Existence of rational points on smooth projective varieties'', also by Bjorn Poonen, shows that being able to detect rational points on smooth projective varieties implies that one can find all rational points algorithmically when there are finitely many. As you can see from the paper, this is far from a trivial reduction...
  - ``Counting Curves and their Projections'' is a very cool paper by Joachim von zur Gathen, Marek Karpinski, and Igor Shparlinski on the complexity of counting the number of points a curve has over a finite field.
  - ``Quantum Computation of Zeta Functions of Curves'', by Kiran Kedlaya, presents an efficient quantum algorithm for computing the zeta function of an algebraic curve over a finite field.
- In our final few lectures, we will be going over sparse resultants (also known as toric resultants).
  - A paper, by Ioannis Emiris and John F. Canny, is still one of the best references for the basic definitions and algorithms...
  - Carlos D'Andrea has written a more recent paper on finding nice formulae for toric resultants. In particular, he has a nice point of view on how to write the toric resultant as a ratio of 2 determinants.
  - ``The Height of the Mixed Sparse Resultant'', by Martin Sombra, is an elegant blend of number theory and algebra that gives excellent bounds on the coefficient growth in toric resultants.
8. Friday, Nov. 6, 2009: The full details for the number-theoretic approach to complex feasibility I mentioned on Lectures 17 & 18 (on Oct. 27 & 29) can be found in an older paper of mine: Check out Paper #50 on my papers page.
7. Thursday, Nov. 5, 2009: Full details for the application of circuit discriminants to real feasibility (and more) mentioned in lecture today can be found in 2 recent papers of mine: Check out Papers #58 and #57 on my papers page.
6. Monday, Nov. 2, 2009: The slides for Day 16 (lecture on Oct. 22, 2009) can be downloaded HERE. Sorry for the delay...
5. Thursday, Sep. 10, 2009: The due date for HW#2 has been corrected: it's Thursday, Sep. 17, 2009.
4. Tuesday, Sep. 8, 2009: HW#2, due Thursday, Sep. 17, 2009, can be downloaded HERE.
3. Tuesday, Sep. 1, 2009: Here is some interesting (optional) reading:
- Landau's ``Mathematics and Common Sense''
- Landau's ``Mathematicians and Social Responsibility "
- a beautiful essay (on being a mathematician and giving talks) by Gian-Carlo Rota, one of the fathers of 20th century combinatorics: here is the link.
2. Tuesday, Sep. 1, 2009: HW#1, due Tuesday, Sep. 8, 2009, can be downloaded HERE. Note: One of the problems refers to a method for computing the Hermite Normal Form, which we will go over briefly this coming thursday.
1. Tuesday, Sep. 1, 2009: The slides for today's lecture can be downloaded HERE. Warning: The verbal asides and definitions I wrote on the board are not in the slides yet...