FUN 2004 PROGRAM

WEDNESDAY MAY 26, 2004


Workshop registration
 
Invited talk
9:00 - 10:00 Odds and evens in algorithm design
S. Muthukrishnan
  
Coffee break
 
Regular papers
10:30 - 11:00 Insertion sort is O(n log n)
M.A. Bender, M. Farach-Colton, M. Mosteiro
11:00 - 11:30 The post-order heap
N.J.A. Harvey, K. Zatloukal
11:30 - 12:00 A problem in scheduling: your time starts now...
A. McGregor
12:00 - 12:30 Polygonal broadcast, secret maturity and the firing sensors
S. Dolev, T. Herman, L. Lahiani
 
Lunch break
 
Invited talk
15:30 - 16:15 Locally free substitutions are not so free: an open problem in sequence alignment
F. Luccio (joint work with S. Brunetti, V. Ciriani, E. Lodi, N. Pisanti)
 
Coffee break
 
Regular papers
16:30 - 17:00 Morpion Solitaire
E.D. Demaine, M.L. Demaine, A. Langerman, S. Langerman
17:00 - 17:30 The hardness of the Lemming Games
G. Cormode
17:30 - 18:00 On the NP-completeness of the NURIKABE-pencil puzzle and variants thereof
M. Holzer, A. Klein, M. Kutrib
 
FUNny papers
18:30 - 19:00 The estherithms museum
P. Crescenzi, E. Lodi, L. Pagli
19:00 - 19:30 How to increase the acceptance ratios of top conferences
G. Cormode, A. Czumaj, S. Muthukrishnan
 
Social dinner
 

THURSDAY, MAY 27


Invited talk
9:00 - 10:00 Rhythm and mathematics: problems at the interface
G. Toussaint
  
Coffee break
 
Regular papers
10:30 - 11:00 Juggling with pattern matching
J. Cardinal, S. Kremer, S. Langerman
11:00 - 11:30 The pattern matching problem in biological weighted sequences
C. Iliopoulos, K. Perdicuri, K. Tsihlas, K. Tsichlas
11:30 - 12:00 Searching for a substring with constant extra space complexity
D. Cantone, S. Faro
 
State-of-the-art tutorials
12:00 - 12:40 How to cope with selfish agents in routing and scheduling
G. Persiano
 
Lunch break
 
State-of-the-art tutorials
15:30 - 16:00 A beginner's guide to the webgraph: properties, models and algorithms
D. Donato, L. Laura, S. Millozzi
16:00 - 16:40 Ranking the Web
G. Del Corso, A. Gullì
 
Coffee break
 
Regular papers
17:00 - 17:30 Sequencing from compomers: the puzzle
S. Boecker
17:30 - 18:00 Reflections on REFLEXION -- Complexity Considerations on a puzzle game
M. Holzer, S. Schwoon
18:00 - 18:30 Pushpush-k is PSACE-complete
E.D. Demaine, M. Hoffmann, M. Holzer

FRIDAY, MAY 28


Invited talk
9:00 - 10:00 Puzzles, art, and magic with algorithms
E.D. Demaine (joint work with M.L. Demaine)
  
Coffee break
 
Regular papers
10:30 - 11:00 How tasty is a cannibal? A strategy for the mesh cannibal game
R. Focardi, F.L. Luccio
11:00 - 11:30 On the efficient capture of dangerous criminals
V. Gervasi, G. Prencipe
11:30 - 12:00 An experimental evaluation of cover design algorithms
P. Crescenzi, F. Greco
12:00 - 12:30 Finding a divisible pair and a good wooden fence
S. Ciurea, E.D. Demaine, C.E. Patrascu, M. Patrascu
 
Lunch break
 
State-of-the-art tutorials
15:00 - 15:30 On explorers, chasers and cameramen
G. Ausiello, L. Laura, V. Bonifaci
15:30 - 16:10 Shortest-path reoptimization algorithms
P. Festa, S. Pallottino
 
Coffee break
 
Regular papers
16:30 - 17:00 Uniform random generation of (r,s)-Fibonacci tilings
D. Merlini, R. Sprugnoli, F. Uncini, M.C. Verri
17:00 - 17:30 More fun with symmetric Venn diagrams
F. Ruskey, M. Weston
17:30 - 18:00 The Graham-Knowlton problem revisited
N. Goyal, S. Lodha, S. Muthukrishnan
 
End of the workshop