Georgia Institute of Technology College of Sciences

Deletion in a balanced search tree is a problematic operation: rebalancing on deletion has more cases than rebalancing on insertion, and it is easy to get wrong. We describe a way to maintain search trees so that rebalancing occurs only on insertion, not on deletion, but the tree depth remains logarithmic in the number of insertions, independent of the number of deletions. Our results provide theoretical justification for common practice in B-tree implementations, as well as providing a new kind of balanced binary tree that is more efficient in several ways than those previously known. This work was done jointly with Sid Sen. This is a day-long event of exciting talks by meta-learning meta-theorist Nina Balcan, security superman Wenke Lee and prolific mathematician Prasad Tetali, posters by the 10 ARC fellowship winners for the current academic year. All details are posted at http://www.arc.gatech.edu/arc4.php. The event begins at 9:00AM.

Which commutative groups can occur as the ideal class group (or "Picard group") of some Dedekind domain? A number theorist naturally thinks of the case of integer rings of number fields, in which the class group must be finite and the question of which finite groups occur is one of the deepest in algebraic number theory. An algebraic geometer naturally thinks of affine algebraic curves, and in particular, that the Picard group of the standard affine ring of an elliptic curve E over C is isomorphic to the group of rational points E(C), an uncountably infinite (Lie) group. An arithmetic geometer will be more interested in Mordell-Weil groups, i.e., E(k) when k is a number field -- again, this is one of the most notorious problems in the field. But she will at least be open to the consideration of E(k) as k varies over all fields. In 1966, L.E. Claborn (a commutative algebraist) solved the "Inverse Picard Problem": up to isomorphism, every commutative group is the Picard group of some Dedekind domain. In the 1970's, Michael Rosen (an arithmetic geometer) used elliptic curves to show that any countable commutative group can serve as the class group of a Dedekind domain. In 2008 I learned about Rosen's work and showed the following theorem: for every commutative group G there is a field k, an elliptic curve E/k and a Dedekind domain R which is an overring of the standard affine ring k[E] of E -- i.e., a domain in between k[E] and its fraction field k(E) -- with ideal class group isomorphic to G. But being an arithmetic geometer, I cannot help but ask about what happens if one is not allowed to pass to an overring: which commutative groups are of the form E(k) for some field k and some elliptic curve E/k? ("Inverse Mordell-Weil Problem") In this talk I will give my solution to the "Inverse Picard Problem" using elliptic curves and give a conjectural answer to the "Inverse Mordell-Weil Problem". Even more than that, I can (and will, time permitting) sketch a proof of my conjecture, but the proof will necessarily gloss over a plausible technicality about Mordell-Weil groups of "arithmetically generic" elliptic curves -- i.e., I do not in fact know how to do it. But the technicality will, I think, be of interest to some of the audience members, and of course I am (not so) secretly hoping that someone there will be able to help me overcome it.

Given a nonconstant holomorphic map f: X \to Y between compact Riemann surfaces, one of the first objects we learn to construct is its ramification divisor R_f, which describes the locus at which f fails to be locally injective. The divisor R_f is a finite formal linear combination of points of X that is combinatorially constrained by the Hurwitz formula. Now let k be an algebraically closed field that is complete with respect to a nontrivial non-Archimedean absolute value. For example, k = C_p. Here the role of a Riemann surface is played by a projective Berkovich analytic curve. As these curves have many points that are not algebraic over k, some new (non-algebraic) ramification behavior appears for maps between them. For example, the ramification locus is no longer a divisor, but rather a closed analytic subspace. The goal of this talk is to introduce the Berkovich projective line and describe some of the topology and geometry of the ramification locus for self-maps f: P^1 \to P^1.

We study a two dimensional Schrödinger operator for a limit-periodic potential. We prove that the spectrum contains a semiaxis and there is a family of generalized eigenfunctions at every point of this semiaxis with the following properties. First, the eigenfunctions are close to plane waves in the high energy region. Second, the isoenergetic curves in the space of momenta corresponding to these eigenfunctions have a form of slightly distorted circles with holes (Cantor type structure). Third, the spectrum corresponding to these eigenfunctions (the semiaxis) is absolutely continuous.