LATIN 2018: Theoretical Informatics

The graph tessellation cover number: extremal bounds, efficient algorithms and hardness.- Approximate Correlation Clustering Using Same-Cluster Queries.- Finding tight Hamilton cycles in random hypergraphs faster.- Walking Through Waypoints.- Lower Bounds for Online Matching on the Line.- On the complexity of _nding internally vertex-disjoint long directed paths.- Algorithms and Hardness Results for Nearest Neighbor Problems in Bicolored Point Sets.- A Polynomial Sized Kernel for Tracking Paths Problem.- Time-Space Trade-O_s for Computing Euclidean Minimum Spanning Trees.- Approximate nearest neighbor for lp-spaces (2 < p < ) via embeddings.- The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model.- Partitioning Orthogonal Histograms into Rectangular Boxes.- Compact Self-Stabilizing Leader Election for General Networks.- Random Walks with Multiple Step Lengths.- Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set.- A tight bound for shortest augmenting paths on trees.- Approximation Algorithms for Replenishment Problems with Fixed Turnover Times.- Maximum Box Problem on Stochastic Points.- The Online Set Aggregation Problem.- Agglomerative Clustering of Growing Squares.- Fourier Entropy-Inuence Conjecture for Random Linear Threshold Functions.- Property Suffix Array with Applications.- Competitive Algorithms for Demand Response Management in Smart Grid.- An Average-Case Lower Bound against ACC^0.- Compressed Indexing with Signature Grammars.- Combinatorics of Beacon-based Routing in Three Dimensions.- On split B1-EPG graphs.- Efficient algorithms for computing a minimal homology basis.- Shifting the Phase Transition Threshold for Random Graphs using Degree Set Constraints.- On the Biased Partial Word Collector Problem.- Constructive Ramsey Numbers For Loose Hyperpaths.- Cache Oblivious Sparse Matrix Multiplication.- Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and