Seminars archive

Almost \$4 billion in federal dollars, provided by the 2002 Help America Vote Act (HAVA), resulted in the initial widespread purchase of paperless computerized voting systems (Direct Recording Electronic or DREs) by many states, including Georgia. Election officials were told that DREs would be cheaper than alternative voting systems, a claim that ignored the costs of testing and secure storage, as well as very expensive annual maintenance contracts. They were told that DREs had been extensively tested and that the certification process guaranteed that the machines were reliable and secure. They were also told that DREs would allow people with disabilities to vote independently. In some cases officials were threatened with lawsuits or actually sued by certain disability rights groups if they expressed hesitation at purchasing DREs. However, early independent security studies, followed by recent results from California’s “Top-to-Bottom Review” have revealed that the DREs that were tested by California – all of which had been federally qualified and state certified – are poorly designed, badly programmed, insecure, unreliable, and at times very difficult for people with disabilities to use. As a result the California Secretary of State Debra Bowen decertified all of the tested systems. While she recertified them, her conditional recertification orders, which contain long lists of detected problems, have still longer lists of conditions, some quite arduous, that must be met. HAVA also required each state to create a statewide computerized database of all registered voters. Congressional Democrats and Republicans supported the computerized databases, because they felt the databases would prevent widespread voter disenfranchisement or voting by illegal aliens, respectively. However, if the databases are not secure and properly monitored, it will be possible to strip large numbers of voters’ names from the databases or to pad the databases with the names of non-citizens. We shall discuss some of the voting technologies that will be used in November, as well as national efforts to make our elections more secure and accurate through the use of voter verified paper ballots. We shall also review the situation in Georgia. Because Georgia still uses paperless Diebold DREs, there will be no way to conduct an audit or recount of the November 2008 election in Georgia. Information on this speaker can be found here: http://usacm.acm.org/usacm/Committee/Simons.htm

Let $G$ be a semisimple linear algebraic group over a field $k$ and let $X$ be a projective homogeneous $G$-variety. The variety $X$ is called \emph{generically cellular} if $G$ splits over the field of rational functions $k(X)$. For example, a Pfister quadric is a generically cellular variety. In the talk I intend to classify such varieties and give applications to the Rost invariant.

We address the problem of the computation of the spectral radius of a family of matrices. We briefly describe the extension of the concept of polytope to the complex space and outline the main geometric properties of such an object. Then we consider the norms determined by the complex polytopes and illustrate a possible algorithm for the approximation of the joint spectral radius of a family of matrices which is based on these complex polytope norms. As an example for our technique we consider the set of two matrices recently analyzed by Blondel, Nesterov and Theys to disprove the finiteness conjecture. This is a joint work with Marino Zennaro (Universit\`{a} di Trieste, Italy).

Evaluation measures act as objective functions to be optimized by Web search engines and other information retrieval systems. Such objective functions must accurately reflect user requirements, particularly when tuning systems and learning ranking functions. Ambiguity in queries and redundancy in retrieved documents represent two areas where current evaluation measures poorly reflect these requirements. In this talk, I will present a framework for evaluation that systematically rewards novelty and diversity. This framework is developed into a specific evaluation measure based on cumulative gain. The feasibility of the approach is demonstrated using a test collection based on the TREC question answering track. Biography: Charles Clarke is an Associate Professor in the School of Computer Science at the University of Waterloo. His research interests cover a wide range of topics related to information search and retrieval, including question answering, XML, program analysis, filesystem search, user interfaces, and statistical NLP.

A model for cleaning a graph with brushes was recently introduced. We consider the minimum number of brushes needed to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. We use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d). We further show that for any d-regular graph on n vertices at most n(d+1)/4 brushes suffice, and prove that for fixed large d, the minimum number of brushes needed to clean a random d-regular graph on n vertices is asymptotically almost surely n(d+o(d))/4. \ (Joint work with Noga Alon and Nick Wormald.)