Georgia Institute of Technology College of Sciences

Let p be a prime, let C/F_p be an absolutely irreducible curve inside the affine plane. Identify the plane with D=[0,p-1]^2. In this talk, we consider the problem of how often a box B in D will contain the expected number of points. In particular, we give a lower bound on the volume of B that guarantees almost all translations of B contain the expected number of points. This shows that the Weil estimate holds in smaller regions in an "almost all" sense. This is joint work with Alexandru Zaharescu.

A tropical complex is a Delta-complex together with some additional numerical data, which come from a semistable degeneration of a variety. Tropical complexes generalize to higher dimensions some of the analogies between curves and graphs. I will introduce tropical complexes and explain how they relate to classical algebraic geometry.

Many real-world problems require an approximation to an algebraic variety (e.g., determination of the roots of a polynomial). To solve such problems, the standard techniques are either symbolic or numeric. Symbolic techniques are globally correct, but they are often time consuming to compute. Numerical techniques are typically fast, but include more limited correctness statements. Recently, attention has shifted to hybrid techniques that combine symbolic and numerical techniques. In this talk, I will discuss hybrid subdivision algorithms for approximating a variety. These methods recursively subdivide an initial region into smaller and simpler domains which are easier to characterize. These algorithms are typically recursive, making them both easy to implement (in practice) and adaptive (performing more work near difficult features). There are two challenges: to develop algorithms with global correctness guarantees and to determine the efficiency of such algorithms. I will discuss solutions to these challenges by presenting two hybrid subdivision algorithms. The first algorithm computes a piecewise-linear approximation to a real planar curve. This is one of the first numerical algorithms whose output is guaranteed to be topologically correct, even in the presence of singularities. The primitives in this algorithm are numerical (i.e., they evaluate a polynomial and its derivatives), but its correctness is justified with algebraic geometry and symbolic algebra. The second algorithm isolates the real roots of a univariate polynomial. I will analyze the number of subdivisions performed by this algorithm using a new technique called continuous amortization. I will show that the number of subdivisions performed by this algorithm is nearly optimal and is comparable with standard symbolic techniques for solving this problem (e.g., Descartes' rule of signs or Sturm sequences).