Lecture Notes in Computer Science


Supported by

NYU-Poly
NYU-Poly

CATT
CATT

IBM Research
IBM Research


Program

21 June (Monday)

8:30-9:00
Registration/Breakfast
9:00-9:30
Welcome
9:30-10:30
Matching/Search -I
Session Chair: Laxmi Parida
Kaizhong Zhang and Yunkun Zhu. Algorithms for Forest Pattern Matching (talk)
Christian Hundt. Affine Image Matching is uniform TC0-complete (talk)

10:30-11:00
Coffee break

11:00-12:00
Keynote speaker: Zvi Galil
Tel Aviv University
Session Chair: Alberto Apostolico
12:00-1:00
Matching/Search -II
Session Chair: Kaizhong Zhang
Shoshana Neuburger and Dina Sokol. Small-Space 2D Compressed Dictionary Matching (talk)
Thomas Schnattinger, Enno Ohlebusch and Simon Gog. Bidirectional search in a string with wavelet trees (talk)

1:00-2:30
Lunch

2:30-4:00
Strings
Session Chair: Dina Sokol
Zhi Xu. A Minimal Periods Algorithm with Applications (talk)
Tsvi Kopelowitz. The Property Suffix Tree with Dynamic Properties
Niko Välimäki and Veli Mäkinen. Approximate All-Pairs Suffix/Prefix Overlaps (talk)

4:00-4:30
Coffee break

4:30-5:30
String Matching
Session Chair: Cinzia Pizzi
Djamal Belazzougui. Succinct Dictionary Matching With No Slowdown (talk)
Benjamin Sach and Raphael Clifford. Pseudo-realtime Pattern Matching: Closing the Gap (talk)

5:30-7:00
Wine and Cheese

22 June (Tuesday)

9:00-10:30
Graphs/Trees
Session Chair: Danny Breslauer
Haitao Jiang, Cedric Chauve and Binhai Zhu. Breakpoint distance and PQ-trees (talk)
Minghui Jiang. On the parameterized complexity of some optimization problems related to multiple-interval graphs (talk)
Arash Farzan and Guy Blelloch. Succinct Representations of Separable Graphs (talk)

10:30-11:00
Coffee break

11:00-12:00
Keynote speaker: Richard M. Karp
University of California at Berkeley
(talk)
Session Chair: Maxime Crochemore
12:00-1:00
Recombinations
Session Chair: Shunsuke Inenaga
Yufeng Wu. Bounds on the Minimum Mosaic of Population Sequences Under Recombination (talk)
Michal Nanasi, Tomas Vinar and Brona Brejova. The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection (talk)

1:00-2:30
Lunch

2:30-3:30
Phylogeny/Haplotypes -I
Session Chair: Rolf Backofen
Michael Elberfeld and Till Tantau. Phylogeny- and Parsimony-Based Haplotype Inference with Constraints (talk)
Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara and Gabriel Valiente. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks (talk)

3:30-4:00
Coffee break

4:00-5:00
Phylogeny/Haplotypes -II
Session Chair: Brona Brejova
Marie-France Sagot, Igor Nor and Danny Hermelin. Mod/Resc Parsimony Inference
Mathias Weller, Johannes Uhlmann, Rudolf Fleischer, Yihui Wang, Xi Wu, Jiong Guo and Rolf Niedermeier. Extended Islands of Tractability for Pasimony Haplotyping (talk)

6:00-
Conference dinner - Le Perigord

23 June (Wednesday)

9:00-10:30
String Arrays
Session Chair: Heejin Park
Jouni Sirén. Sampled Longest Common Prefix Array (talk)
Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Verifying a Parameterized Border Array in O(n^{1.5}) Time
Maxime Crochemore, Costas Iliopoulos, Solon Pissis and German Tischler. Cover array string reconstruction (talk)

10:30-11:00
Coffee break

11:00-12:00
Keynote speaker: Jeffrey S. Vitter
Texas A&M University
(talk)
Session Chair: Amihood Amir
12:00-1:00
Automatons
Session Chair: Raphael Clifford
Omar AitMous, Frédérique Bassino and Cyril Nicaud. Building the Minimal Automaton of A^*X in Linear Time, When X Is of Bounded Cardinality (talk)
Simone Faro, Domenico Cantone and Emanuele Giaquinta. A Compact Representation of Nondeterministic (Suffix) Automata for the Bit-Parallel Approach (talk)

1:00-2:30
Lunch

2:30-4:00
Alignments
Session Chair: Avivit Levy
Maxime Crochemore, Marek Cygan, Costas Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen. Algorithms for Three Versions of the Shortest Common Superstring Problem (talk)
Taehyung Lee, Joong Chae Na, Heejin Park, Kunsoo Park and Jeong Seop Sim. Finding Optimal Alignment and Consensus of Circular Strings (talk)
Pablo Montes, Heraldo Memelli, Charles Ward, Joondong Kim, Joseph S. B. Mitchell, and Steven Skiena. Optimizing Restriction Site Placement for Synthetic Genomes (talk)

4:00-4:30
Coffee break

4:30-5:30
Compression
Session Chair: Gad Landau
Hidetoshi Yokoo. Extension and Faster Implementation of the GRP Transform for Lossless Compression (talk)
Luis M. S. Russo and Arlindo Oliveira. Parallel and Distributed Compressed Indexes (talk)