[Lowerbounds, Upperbounds]

SPEAKER: Vijaya Ramachandran
TIME: Thursday 4:30-5:30 pm, October 19th, 2006
PLACE: PPB 300
TITLE: The Diameter of Sparse Random Graphs

ABSTRACT:

We derive an expression of the form $c ln n + o(ln n)$ for the diameter of a sparse random graph with a specified degree sequence. The result holds a.a.s., assuming certain convergence and supercriticality conditions are met. The classes of random graphs for which this result applies include the classical random graph model $G_{n,p}$ when $p=(1+b)/n$ for any positive constant $b$, and ‘power-law’ graphs when the giant component exists and the number of edges is linear in the number of vertices. The proof is constructive and yields a method for computing the constant $c$. Our methods also establish that almost all pairs of vertices that are connected by a path in such a random graph have almost the same shortest path distance.

This is joint work with Dan Fernholz.

SPEAKER: Warren D. Smith
TIME: Wednesday 12-1pm, Octobre 18, 2006
PLACE: NSH 1507

TITLE: Low-Tech Secure Voting Schemes

ABSTRACT:

You want to have secret ballot voting (nobody knows how anybody voted - prevents vote-buying and coercion). Even if the voter wants to reveal her vote, she should be unable. And you want to have verifiable voting - all should be confident the election results were correctly computed using only the correct votes (none altered, deleted, or added).

At first, it seemed impossible to achieve both desires. Later it was seen (via very complicated cryptographic multiparty protocols) how to do it. But last month Ron Rivest invented a blitheringly simple way to do it without any cryptography or computers at all. Then I fixed the flaws in Rivest’s schemes.