Georgia Institute of Technology College of Sciences

Organizational meeting.

In this talk, we consider a well-known combinatorial search problem. Suppose that there are n identical looking coins and some of them are counterfeit. The weights of all authentic coins are the same and known a priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing (queries) sets of coins on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins. We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most m \geq 2 and the weight w(c) of each counterfeit coin c satisfies \alpha \leq |w(c)| \leq \beta for fixed constants \alpha, \beta > 0. The query complexity of the algorithm is O(\frac{m \log n }{\log m}), which is optimal up to a constant factor. The algorithm uses, in part, random walks. The algorithm may be generalized to find all edges of a hidden weighted graph using a similar type of queries. This graph finding algorithm has various applications including DNA sequencing.

We will discuss the basics of automorphisms of free groups and train track structure. We will define the growth rate which is a topological entropy of the train track map.

The hyperelliptic Torelli group SI(S) is the subgroup of the mapping class group of a surface S consisting of elements which commute with a fixed hyperelliptic involution and which act trivially on homology. The group SI(S) appears in a variety of settings, for example in the context of the period mapping on the Torelli space of a Riemann surface and also as a kernel of the classical Burau representation of the braid group. We will show that the cohomological dimension of SI(S) is g-1; this result fits nicely into a pattern with other subgroups of the mapping class group, particularly those of the Johnson filtration. This is joint work with Leah Childers and Dan Margalit.