ALGO 2016 [ Monday | Tuesday | Wednesday | Thursday | Friday | all ]

Tuesday 23/8
08:30-09:00 Registration
09:00-10:15 Session 6A: Streaming Algorithms
Chair: Christian Sohler
Session 6B: FPT Hardness
Chair: Holger Dell
Session 6C
Chair: Sven Rahmann
Session 6D
Chair: Ke Yi
09:00 Nathanaël François, Frédéric Magniez, Michel de Rougemont, Olivier Serre
Streaming Property Testing of Visibly Pushdown Languages
Lukasz Kowalik, Juho Lauri, Arkadiusz Socala
On the Fine-Grained Complexity of Rainbow Coloring
Sorina Maciuca, Carlos Del Ojo Elias, Gil McVean and Zamin Iqbal:
A Natural Encoding of Genetic Variation in a Burrows-Wheeler Transform to Enable Mapping and Genome Inference
Xiao Hu and Ke Yi:
Towards a Worst-case I/O-optimal Algorithm for Acyclic Joins
09:25 Lasse Kliemann, Christian Schielke, Anand Srivastav
A Streaming Algorithm for the Undirected Longest Path Problem
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket
On the Hardness of Learning Sparse Parities
Adam Novak, Erik Garrison and Benedict Paten:
A Graph Extension of the Positional Burrows-Wheeler Transform and Its Applications
Kasper Eenberg, Kasper Green Larsen and Huacheng Yu:
DecreaseKeys are Expensive for External Memory Priority Queues
09:50 Michael Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff
Stochastic Streams: Sample Complexity vs. Space Complexity
Subhash Khot, Rishi Saket
Hardness of Bipartite Expansion
Svend V Nielsen, Simon Simonsen and Asger Hobolth:
Inferring Population Genetic Parameters: Particle Filtering, HMM, Ripley’s K-Function or Runs of Homozygosity?
Gerth Stølting Brodal:
External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates
10:15-10:35 Coffee Break
10:35-11:25 Session 7A: Lower Bounds
Chair: Ulrich Meyer
Session 7B: Geometry III
Chair: Stefan Schirra
Session 7C
Chair: Jan Baumbach
Session 7D
Chair: Kasper Green Larsen
10:35 Raphaël Clifford, Markus Jalsenius, Benjamin Sach
Cell-Probe Lower Bounds for Bit Stream Computation
Lingxiao Huang, Jian Li, Jeff M. Phillips, Haitao Wang
ε-Kernel Coresets for Stochastic Points
Leena Salmela and Alexandru I. Tomescu:
Safely filling gaps with partial solutions common to all solutions
Rasmus Pagh, Mayank Goswami, Francesco Silvestriand Johan Sivertsen:
Distance Sensitive Bloom Filters Without False Negatives
11:00 Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Julian Shun
Efficient Algorithms with Asymmetric Read and Write Costs
Tamal K. Dey, Dayu Shi, Yusu Wang
SimBa: An Efficient Tool for Approximating  Rips-Filtration Persistence via Simplicial Batch-Collapse
Jay Ghurye and Mihai Pop:
Better Identification of Repeats in Metagenomic Scaffolding
Thomas D. Ahle, Martin Aumuller and Rasmus Pagh: Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
11:25-11:30 Break
11:30-12:30 WABI Invited
Kiyoshi Asai
Algorithms on Marginal Distributions of
RNA Secondary Structures
Chair: Martin Frith
12:30-14:00 Lunch
14:00-15:15 Session 8A: Scheduling
Chair: Marcin Bieńkowski
Session 8B: Polynomial Time
Chair: Michał Pilipczuk
Session 8C
Chair: Richard Röttger
Session 8D
Chair: Ke Yi
14:00 Chien-Chung Huang, Sebastian Ott
A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
Jean Cardinal, John Iacono, Aurélien Ooms
Solving k-SUM Using Few Linear Queries
Yun Deng and David Fernández-Baca:
Fast Compatibility Testing for Phylogenies with Nested Taxa
Vladimir Braverman, Alan Roytman and Greg Vorsanger: Approximating Subadditive Hadamard Functions on Implicit Matrices
14:25 Guy Even, Moti Medina, Adi Rosen
A Constant Approximation Algorithm for Scheduling Packets on Line Networks
Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat
How Hard is it to Find (Honest) Witnesses?
Arnon Benshahar, Vered Caspi, Danny Hermelin, and Michal Ziv-Ukelson:
A Biclique Approach to Reference Anchored Gene Blocks and its Applications to Pathogenicity Islands
Frank Kammer, Maarten Löffler and Rodrigo Silveira: Space-Efficient Surface Removal
14:50 Andreas S. Schulz, José Verschae
Min-Sum Scheduling Under Precedence Constraints
Matti Karppa, Petteri Kaski, Jukka Kohonen, Padraig Ó Catháin
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time
Mohammed El-Kebir, Ben Raphael, Ron Shamir, Roded Sharan, Simone Zaccaria, Meirav Zehavi and Ron Zeira:
Copy-Number Evolution Problems: Complexity and Algorithms
Lingxiao Huang and Jian Li:
Stochastic k-Center and j-Flat-Center Problems
15:15-15:30 Break
15:30-16:45 Session 9A: FPT Counting
Chair: Bart M. P. Jansen
Session 9B: Distance Oracles
Chair: Giuseppe F. Italiano
Session 9C
Chair: Martin Frith
Session 9D
Chair: Nodari Sitchinava
15:30 Radu Curticapean
Counting Matchings with k Unmatched Vertices in Planar Graphs
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Ely Porat
Sublinear Distance Labeling
WABI Poster Peyman Afshani and Zhewei Wei:
Independent Range Sampling Revisited
15:55 Eduard Eiben, Robert Ganian, Kustaa Kanga, Sebastian Ordyniak
Counting Linear Extensions: Parameterizations by Treewidth
Krishnendu Chatterjee, Rasmus Rasmus Ibsen-Jensen, Andreas Pavlogiannis
Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs
Zengfeng Huang and Ke Yi:
The Communication Complexity of Distributed Epsilon-Approximations
16:20-16:35 Break
16:35-18:30 Session 10A: ESA best papers
Chair: Piotr Sankowski & Dorothea Wagner
Session 10C
Chair: Martin Frith
16:35 ESA Test-of-Time Award WABI Poster
16:50 Stefan Kratsch
A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
17:15 Thomas Bläsius, Tobias Friedrich, Anton Krohmer, Sören Laue
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
17:40 Adam Kunysz
The Strongly Stable Roommates Problem
18:05 Michele Borassi, Emanuele Natale
KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
18:30 Bus to conference dinner
19:00-... Conference Dinner (Godsbanen, downtown)