Oct 6 Zach Abel

Origami is Hard in Theory, Too

What do floors, cages, drains, pipes, wires, bricks, and towers have in common? They're all used in a fairly involved construction[1] showing that the problem of polyhedral Edge Unfolding—an important problem in Computational Origami—is computationally intractable. (The Edge Unfolding problem asks whether, for a given polyhedron, it is possible to unfold the surface into a non-overlapping net in the plane while keeping the faces intact.)

What if we try to make Origami simpler by recasting it in LOWER dimensions? Specifically, we could ask whether a given planar graph (with edge lengths) can be "folded flat" along a line without overlaps.

It turns out that any attempts to solve this problem efficiently are also destined to fall flat.

In this talk we will offer background and motivation for these Computational Geometry problems and sketch (literally!) their hardness proofs.

Oct 20 Theja Tulabandhula

A 60 minute tour of Statistical Learning Theory

There are many learning algorithms that people have developed and a theory based on statistical point of view formalizes and analyses these algorithms. In this introductory self-contained talk, I will discuss a way to describe some learning scenarios. We will see how the assumptions we make influence our guarantees on learning. There will be some interesting applications of concentration bounds.

Nov 10 Alex Levin

Sleeping with the Enemy

Neanderthals were archaic hominids who co-existed with modern humans tens of thousands of years ago. Many researchers have tried to understand their genetics, and recently, a team has succeeded in producing a draft of the Neanderthal genome. After analyzing this genome, they reached the shocking conclusion that Neanderthals and modern humans exchanged DNA, and that a significant portion of the genome of non-Africans is of Neanderthal origins.

We will give an overview of the work required to sequence and analyze the Neanderthal genome. Since much of the data is now publicly available, anyone interested can try to see what else it says about human history!