ALGO 2016 [ Monday | Tuesday | Wednesday | Thursday | Friday | all ] Tuesday 23/8
	ESA 1	ESA 2	WABI	MASSIVE
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)