default search action
45th ICALP 2018: Prague, Czech Republic
- Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald Sannella:
45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. LIPIcs 107, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-076-7 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xlviii
- Theophanis Hadjistasi, Alexander A. Schwarzmann
:
Consistent Distributed Memory Services: Resilience and Efficiency (Invited Paper). 1:1-1:19 - Jaroslav Nesetril:
Sparsity - an Algorithmic Perspective (Invited Paper). 2:1-2:1 - Sam Staton:
Probability Theory from a Programming Perspective (Invited Paper). 3:1-3:1 - Richard Ryan Williams:
Lower Bounds by Algorithm Design: A Progress Report (Invited Paper). 4:1-4:1 - Anders Aamand, Mathias Bæk Tejs Knudsen, Mikkel Thorup
Power of d Choices with Simple Tabulation. 5:1-5:14 - Anders Aamand, Niklas Hjuler, Jacob Holm, Eva Rotenberg
One-Way Trail Orientations. 6:1-6:13 - Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. 7:1-7:16 - Amir Abboud, Karl Bringmann:
Tighter Connections Between Formula-SAT and Shaving Logs. 8:1-8:18 - Anna Adamaszek, Matthias Mnich
New Approximation Algorithms for (1, 2)-TSP. 9:1-9:14 - Pankaj K. Agarwal, Haim Kaplan, Micha Sharir:
Union of Hypercubes and 3D Minkowski Sums with Random Sizes. 10:1-10:15 - Rotem Arnon Friedman
Noise-Tolerant Testing of High Entanglement of Formation. 11:1-11:12 - Miriam Backens
A Complete Dichotomy for Complex-Valued Holant^c. 12:1-12:14 - Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod
Tight Bounds on Online Checkpointing Algorithms. 13:1-13:13 - Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev:
Fast Reed-Solomon Interactive Oracle Proofs of Proximity. 14:1-14:17 - Amey Bhangale:
NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors. 15:1-15:11 - Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian
Sublinear Algorithms for MAXCUT and Correlation Clustering. 16:1-16:14 - Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S.
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. 17:1-17:15 - Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka
Rollercoasters and Caterpillars. 18:1-18:15 - Davide Bilò
New algorithms for Steiner tree reoptimization. 19:1-19:14 - Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry:
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. 20:1-20:14 - Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, Lin F. Yang
Approximate Convex Hull of Data Streams. 21:1-21:13 - Andrej Bogdanov:
Small Bias Requires Large Formulas. 22:1-22:12 - Prosenjit Bose, Paz Carmi, Vida Dujmovic, Saeed Mehrabi, Fabrizio Montecchiani
Geodesic Obstacle Representation of Graphs. 23:1-23:13 - Elette Boyle, Abhishek Jain
The Bottleneck Complexity of Secure Multiparty Computation. 24:1-24:16 - Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang
Revisiting Frequency Moment Estimation in Random Order Streams. 25:1-25:14 - Jaroslaw Byrka
Proportional Approval Voting, Harmonic k-median, and Negative Association. 26:1-26:14 - Marco L. Carmosino
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. 27:1-27:16 - L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi:
Ranking with Fairness Constraints. 28:1-28:15 - Deeparnab Chakrabarty, Chaitanya Swamy:
Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median. 29:1-29:14 - Deeparnab Chakrabarty, Maryam Negahbani:
Generalized Center Problems with Outliers. 30:1-30:14 - Timothy M. Chan, Yakov Nekrich
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d. 31:1-31:14 - L. Sunil Chandran, Yun Kuen Cheung, Davis Issac:
Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition. 32:1-32:14 - Moses Charikar
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier. 33:1-33:14 - Moses Charikar
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings. 34:1-34:14 - Jiehua Chen, Danny Hermelin, Manuel Sorge, Harel Yedidsion:
How Hard Is It to Satisfy (Almost) All Roommates?. 35:1-35:15 - Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas. 36:1-36:13 - Siu-Wing Cheng, Yuchen Mao:
Restricted Max-Min Fair Allocation. 37:1-37:13 - Julia Chuzhoy, David H. K. Kim, Rachit Nimavat:
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary. 38:1-38:14 - Alexander Conway, Martin Farach-Colton
Optimal Hashing in External Memory. 39:1-39:14 - Holger Dell
Lovász Meets Weisfeiler and Leman. 40:1-40:14 - Ilias Diakonikolas, Themis Gouleakis
Sample-Optimal Identity Testing with High Probability. 41:1-41:14 - Ran Duan, Hanlin Ren
Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time. 42:1-42:12 - Ran Duan, Kaifeng Lyu, Yuanhang Xie:
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. 43:1-43:14 - Ran Duan, Yong Gu
Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs. 44:1-44:14 - Bartlomiej Dudek
Edit Distance between Unrooted Trees in Cubic Time. 45:1-45:14 - Lech Duraj
A Note on Two-Colorability of Nonuniform Hypergraphs. 46:1-46:13 - Zdenek Dvorák, Ken-ichi Kawarabayashi:
Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes. 47:1-47:12 - Eduard Eiben, Iyad A. Kanj:
How to Navigate Through Obstacles?. 48:1-48:13 - Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein:
Faster Algorithms for Integer Programs with Block Structure. 49:1-49:13 - Uriel Feige, Boaz Patt-Shamir, Shai Vardi:
On the Probe Complexity of Local Computation Algorithms. 50:1-50:14 - Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar
Fully-Dynamic Bin Packing with Little Repacking. 51:1-51:24 - Hendrik Fichtenberger
A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error. 52:1-52:14 - Fedor V. Fomin
Parameterized Low-Rank Binary Matrix Approximation. 53:1-53:16 - Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
Towards Blackbox Identity Testing of Log-Variate Circuits. 54:1-54:16 - Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, Nicole Wein:
Finding Cliques in Social Networks: A New Distribution-Free Model. 55:1-55:15 - Hao Fu, Jian Li, Pan Xu:
A PTAS for a Class of Stochastic Dynamic Programs. 56:1-56:14 - Buddhima Gamlath, Sangxia Huang, Ola Svensson:
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering. 57:1-57:14 - Sumit Ganguly, David P. Woodruff:
High Probability Frequency Moment Sketches. 58:1-58:15 - Shashwat Garg:
Quasi-PTAS for Scheduling with Precedences using LP Hierarchies. 59:1-59:13 - Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek
ARRIVAL: Next Stop in CLS. 60:1-60:13 - Pawel Gawrychowski
Improved Bounds for Shortest Paths in Dense Distance Graphs. 61:1-61:15 - Pawel Gawrychowski
Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance. 62:1-62:13 - Pawel Gawrychowski
A Faster Construction of Greedy Consensus Trees. 63:1-63:14 - Pawel Gawrychowski
A Faster FPTAS for #Knapsack. 64:1-64:13 - Shay Golan
Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams. 65:1-65:16 - Petr Gregor
Gray Codes and Symmetric Chains. 66:1-66:14 - Martin Grohe, Daniel Neuen
An Improved Isomorphism Test for Bounded-Tree-Width Graphs. 67:1-67:14 - Heng Guo, Mark Jerrum:
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. 68:1-68:12 - Heng Guo, Mark Jerrum:
Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. 69:1-69:10 - Anupam Gupta, Amit Kumar
Non-Preemptive Flow-Time Minimization via Rejections. 70:1-70:13 - Anupam Gupta, Ruta Mehta, Marco Molinaro:
Maximizing Profit with Convex Costs in the Random-order Model. 71:1-71:14 - Manoj Gupta
Generic Single Edge Fault Tolerant Exact Distance Oracle. 72:1-72:15 - Tom Gur, Yang P. Liu, Ron D. Rothblum:
An Exponential Separation Between MA and AM Proofs of Proximity. 73:1-73:15 - Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi:
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. 74:1-74:14 - Bernhard Haeupler, Amirbehshad Shahrasbi
Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. 75:1-75:14 - Bernhard Haeupler, Amirbehshad Shahrasbi
Synchronization Strings: List Decoding for Insertions and Deletions. 76:1-76:14 - Sariel Har-Peled
Approximate Sparse Linear Regression. 77:1-77:14 - Koyo Hayashi:
A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes. 78:1-78:14 - Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu
Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals. 79:1-79:14 - Jisu Jeong, Eun Jung Kim, Sang-il Oum:
Finding Branch-Decompositions of Matroids, Hypergraphs, and More. 80:1-80:14 - Juan José Besa Vial, William E. Devanny, David Eppstein, Michael T. Goodrich
Optimally Sorting Evolving Data. 81:1-81:13 - Daniel M. Kane, Shachar Lovett
Generalized Comparison Trees for Point-Location Problems. 82:1-82:13 - Zhuan Khye Koh, Laura Sanità:
Stabilizing Weighted Graphs. 83:1-83:13 - Alexandra Kolla, Ioannis Koutis
Spectrally Robust Graph Isomorphism. 84:1-84:13 - Martin Koutecký
A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. 85:1-85:14 - Michael Lampis:
Finer Tight Bounds for Coloring on Clique-Width. 86:1-86:14 - Christoph Lenzen, Reut Levi:
A Centralized Local Algorithm for the Sparse Spanning Graph Problem. 87:1-87:14 - Sixue Liu:
Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT. 88:1-88:13 - Gill Barequet, David Eppstein, Michael T. Goodrich
Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms. 89:1-89:14 - Vasileios Nakos, Xiaofei Shi
Improved Algorithms for Adaptive Compressed Sensing. 90:1-90:14 - Chinmay Nirkhe
Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. 91:1-91:11 - Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein:
Fully Dynamic MIS in Uniformly Sparse Graphs. 92:1-92:14 - Rafail Ostrovsky
Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration. 93:1-93:11 - Felix Reidl
Parameterized Algorithms for Zero Extension and Metric Labelling Problems. 94:1-94:14 - Andrei E. Romashchenko
An Operational Characterization of Mutual Information in Algorithmic Information Theory. 95:1-95:14 - Clemens Rösner, Melanie Schmidt
Privacy Preserving Clustering with Constraints. 96:1-96:14 - Piotr Sankowski:
NC Algorithms for Weighted Planar Perfect Matching and Related Problems. 97:1-97:16 - Andreas Schmid, Jens M. Schmidt
Computing Tutte Paths. 98:1-98:14 - Tasuku Soma
A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity. 99:1-99:14 - Daniele Micciancio
Ring Packing and Amortized FHEW Bootstrapping. 100:1-100:14 - Anand Louis, Rakesh Venkat
Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery. 101:1-101:15 - Stefan Walzer
Load Thresholds for Cuckoo Hashing with Overlapping Blocks. 102:1-102:10 - Navneet Agarwal, Sanat Anand, Manoj Prabhakaran:
Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC. 103:1-103:4 - Amy Babay
Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. 104:1-104:4 - Ben Berger, Zvika Brakerski:
Brief Announcement: Zero-Knowledge Protocols for Search Problems. 105:1-105:5 - Jeremiah Blocki
Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels. 106:1-106:4 - Steven Chaplick
Brief Announcement: Approximation Schemes for Geometric Coverage Problems. 107:1-107:4 - Jing Chen, Bo Li
Brief Announcement: Bayesian Auctions with Efficient Queries. 108:1-108:4 - Daniel Graf, Karim Labib, Przemyslaw Uznanski:
Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication. 109:1-109:4 - Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, Meirav Zehavi:
Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS. 110:1-110:4 - Sofya Raskhodnikova, Nithin Varma
Brief Announcement: Erasure-Resilience Versus Tolerance to Errors. 111:1-111:3 - Mingyu Xiao, Hiroshi Nagamochi:
Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable. 112:1-112:6 - Alejandro Aguirre
Almost Sure Productivity. 113:1-113:15 - Shaull Almagor, Dmitry Chistikov, Joël Ouaknine, James Worrell
O-Minimal Invariants for Linear Loops. 114:1-114:14 - Antoine Amarilli, Charles Paperman
Topological Sorting with Regular Constraints. 115:1-115:14 - Albert Atserias, Stephan Kreutzer
On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface. 116:1-116:14 - Achim Blumensath
Bisimulation Invariant Monadic-Second Order Logic in the Finite. 117:1-117:13 - Lorenzo Clemente, Slawomir Lasota
Binary Reachability of Timed Pushdown Automata via Quantifier Elimination and Cyclic Order Atoms. 118:1-118:14 - Wojciech Czerwinski
Unboundedness Problems for Languages of Vector Addition Systems. 119:1-119:15 - Samir Datta
Reachability and Distances under Multiple Changes. 120:1-120:14 - Laure Daviaud
When is Containment Decidable for Probabilistic Automata?. 121:1-121:14 - Gaëtan Douéneau-Tabot:
On the Complexity of Infinite Advice Strings. 122:1-122:13 - María Emilia Descotte, Diego Figueira
Resynchronizing Classes of Word Relations. 123:1-123:13 - John Fearnley, Martin Gairing, Matthias Mnich
Reachability Switching Games. 124:1-124:14 - Martin Fränzle
Costs and Rewards in Priced Timed Automata. 125:1-125:14 - Jakub Gajarský, Stephan Kreutzer
First-Order Interpretations of Bounded Expansion Classes. 126:1-126:14 - Moses Ganardi
Randomized Sliding Window Algorithms for Regular Languages. 127:1-127:13 - Anaël Grandjean, Benjamin Hellouin de Menibus, Pascal Vanier
Aperiodic Points in Z2-subshifts. 128:1-128:13 - Mathieu Hoyrup, Diego Nava Saucedo, Don M. Stull:
Semicomputable Geometry. 129:1-129:13 - Stefan Kiefer:
On Computing the Total Variation Distance of Hidden Markov Models. 130:1-130:13 - Ines Klimann:
To Infinity and Beyond. 131:1-131:12 - Sang-Ki Ko
On the Identity Problem for the Special Linear Group and the Heisenberg Group. 132:1-132:15 - Dietrich Kuske, Nicole Schweikardt:
Gaifman Normal Forms for Counting Extensions of First-Order Logic. 133:1-133:14 - Jérôme Leroux:
Polynomial Vector Addition Systems With States. 134:1-134:13 - Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi:
Reducing CMSO Model Checking to Highly Connected Graphs. 135:1-135:14 - Dirk Nowotka
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences. 136:1-136:13 - Thomas Place, Marc Zeitoun
Separating Without Any Ambiguity. 137:1-137:14 - Mikhail A. Raskin
A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton. 138:1-138:11 - Géraud Sénizergues, Armin Weiß
The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE. 139:1-139:14 - Michal Skrzypczak:
Unambiguous Languages Exhaust the Index Hierarchy. 140:1-140:14 - Sam Staton, Dario Stein, Hongseok Yang, Nathanael L. Ackerman, Cameron E. Freer, Daniel M. Roy:
The Beta-Bernoulli process and algebraic effects. 141:1-141:15 - Sarah Winter:
Uniformization Problems for Synchronizations of Automatic Relations on Words. 142:1-142:13 - Saeed Akhoondian Amiri, Szymon Dudycz
Congestion-Free Rerouting of Flows on DAGs. 143:1-143:13 - Megumi Ando, Anna Lysyanskaya, Eli Upfal
Practical and Provably Secure Onion Routing. 144:1-144:14 - Boris Aronov
Resolving SINR Queries in a Dynamic Setting. 145:1-145:13 - Vittorio Bilò
Uniform Mixed Equilibria in Network Congestion Games with Link Failures. 146:1-146:14 - Sébastien Bouchard
Byzantine Gathering in Polynomial Time. 147:1-147:15 - Eleni C. Akrida
Temporal Vertex Cover with a Sliding Time Window. 148:1-148:14 - Flavio Chierichetti, Shahrzad Haddadan
On the Complexity of Sampling Vertices Uniformly from a Graph. 149:1-149:13 - George Christodoulou
The Price of Stability of Weighted Congestion Games. 150:1-150:16 - Riccardo Colini-Baldeschi, Max Klimm, Marco Scarsini:
Demand-Independent Optimal Tolls. 151:1-151:14 - Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, Saeed Seddighin:
Greedy Algorithms for Online Survivable Network Design. 152:1-152:14 - Ofer Grossman, Bernhard Haeupler, Sidhanth Mohanty:
Algorithms for Noisy Broadcast with Erasures. 153:1-153:12 - Tobias Harks, Martin Hoefer, Anja Huber, Manuel Surek:
Efficient Black-Box Reductions for Separable Cost Sharing. 154:1-154:15 - Thomas Kesselheim, Bojana Kodric
Price of Anarchy for Mechanisms with Risk-Averse Agents. 155:1-155:14 - Dariusz R. Kowalski, Miguel A. Mosteiro:
Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations. 156:1-156:14 - Orna Kupferman, Gal Vardi:
The Unfortunate-Flow Problem. 157:1-157:14 - Magnús M. Halldórsson
Spanning Trees With Edge Conflicts and Wireless Connectivity. 158:1-158:15 - Frederik Mallmann-Trenn, Cameron Musco, Christopher Musco
Eigenvector Computation and Community Detection in Asynchronous Gossip Models. 159:1-159:14 - Merav Parter:
(Delta+1) Coloring in the Congested Clique Model. 160:1-160:14 - Sarvar Patel, Giuseppe Persiano, Kevin Yeo:
CacheShuffle: A Family of Oblivious Shuffles. 161:1-161:13 - MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni:
Brief Announcement: MapReduce Algorithms for Massive Trees. 162:1-162:4 - Ran Ben-Basat, Gil Einziger, Roy Friedman:
Brief Announcement: Give Me Some Slack: Efficient Network Measurements. 163:1-163:5 - Eli Ben-Sasson, Eden Saig:
Brief Announcement: Towards an Abstract Model of User Retention Dynamics. 164:1-164:4 - Shantanu Das
Brief Announcement: Energy Constrained Depth First Search. 165:1-165:5
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-14 22:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: