Speakers: 1. John Iacono (Polytechnic Institute of New York University), 
2. Stefan Langerman (Universite Libre de Bruxelles)
3. Erik D. Demaine (MIT)
--
UEC & ELC Joint Seminar on Theoretical Computer Science

We are going to have a seminar on Theoretical Computer Science,  
which consists of three talks by distinguished researchers. 
We hope you all participate.  

--

Time and Date: 13:30--16:20, Sept.20, 2013.
Place: AV hall, 3F, West-9 BLDG, The University of Electro-Communications

Program ---- 

13:30--14:30

John Iacono (Polytechnic Institute of New York University)

Title: In pursuit of the dynamic optimality conjecture

Abstract: 
In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting 
binary search tree algorithm. Splay trees were conjectured to perform 
within a constant factor as any offline rotation-based search tree 
algorithm on every sufficiently long sequence---any binary search tree 
algorithm that has this property is said to be dynamically optimal. 
However, currently neither splay trees nor any other tree algorithm is 
known to be dynamically optimal. Here we survey the progress that has 
been made in the almost thirty years since the conjecture was first 
formulated, and present a binary search tree algorithm that is 
dynamically optimal if any binary search tree algorithm is dynamically 
optimal.

--

14:30--15:20

Stefan Langerman (Universite Libre de Bruxelles)

Title: Bichromatic compatible matchings

Abstract: 
For a set $R$ of $n$ red points and a set $B$ of $n$ blue points, a
$BR$-matching is a non-crossing geometric perfect matching where each
segment has one endpoint in $B$ and one in $R$. Such a matching always
exists. Two $BR$-matchings are compatible if their union is also
non-crossing. We prove that, for any two distinct $BR$-matchings $M$
and $M'$, there exists a sequence of $BR$-matchings $M = M_1, ..., M_k
= M'$ such that $M_{i-1} $ is compatible with $M_i$.
Joint work with Greg Aloupis, Luis Barba, and Diane L. Souvaine

--

15:30--16:20

Erik D. Demaine (MIT)

Title: Geometric Folding Algorithms: Linkages, Origami, Polyhedra

Abstract: 
What forms of origami can be designed automatically by algorithms?
How might we build reconfigurable robots like Transformers or Terminator 3,
hinging together a collection of pieces that dynamically reconfigure
into arbitrary shapes?  When can a robotic arm of rigid rods be folded into
a desired configuration?  What shapes can result by folding a piece of
paper flat and making one complete straight cut?  What 3D surfaces can be
manufactured from a single sheet of material?  How might proteins fold?

   Geometric folding is a branch of discrete and computational geometry
that addresses these and many other intriguing questions.
I will give a taste of the many results that have been proved in the past
several years, as well as the several exciting unsolved problems that remain
open.  Many folding problems have applications in areas including
manufacturing, robotics, graphics, and protein folding.

--

Organizer: Hiro Ito (School of Informatics and Engineering, UEC)