Portal - ICALP 2018

ICALP 2018	July 9-13, 2018 - Prague, Czech Republic
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) Ioannis Chatzigiannakis and Christos Kaklamanis and Dániel Marx and Donald Sannella (Eds.)
ISBN 978-3-95977-076-7, LIPICS Vol. 107	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 70 MB)
Search Publication Server

Authors

Aamand, Anders

Abboud, Amir

Ackerman, Nathanael L.

Akhoondian Amiri, Saeed

Arnon-Friedman, Rotem

Bateni, MohammadHossein

Bæk Tejs Knudsen, Mathias

Chakrabarty, Deeparnab

Chatzigiannakis, Ioannis

Christodoulou, George

Chuzhoy, Julia

Clemente, Lorenzo

Cohen, Sarel

Colini-Baldeschi, Riccardo

Descotte, María Emilia

Douéneau-Tabot, Gaëtan

Eisenbrand, Friedrich

Eppstein, David

Farach-Colton, Martín

Fichtenberger, Hendrik

Giannakopoulos, Yiannis

Hadjistasi, Theophanis

Haeupler, Bernhard

Hajiaghayi, MohammadTaghi

Halldórsson, Magnús M.

Hansen, Thomas Dueholm

Har-Peled, Sariel

Harks, Tobias

Hayashi, Koyo

Hellouin de Menibus, Benjamin

Hunkenschröder, Christoph

Kawarabayashi, Ken-ichi

Mallmann-Trenn, Frederik

Montecchiani, Fabrizio

Montenegro-Retana, Felix

Ossona de Mendez, Patrice

Schwarzmann, Alexander A.

Shahrasbi, Amirbehshad

Silveira, Luis Fernando Schultz Xavier da

Tsakalidis, Konstantinos

Venkatasubramanian, Suresh

Wiederrecht, Sebastian

Wille, Kaja

Williams, Richard Ryan

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Chatzigiannakis, Ioannis ; Kaklamanis, Christos ; Marx, Dániel ; Sannella, Donald

Abstract | Document (562 KB) | BibTeX

Consistent Distributed Memory Services: Resilience and Efficiency (Invited Paper)

Authors: Hadjistasi, Theophanis ; Schwarzmann, Alexander A.

Abstract | Document (521 KB) | BibTeX

Sparsity - an Algorithmic Perspective (Invited Paper)

Authors: Nesetril, Jaroslav

Abstract | Document (160 KB) | BibTeX

Probability Theory from a Programming Perspective (Invited Paper)

Authors: Staton, Sam

Abstract | Document (159 KB) | BibTeX

Lower Bounds by Algorithm Design: A Progress Report (Invited Paper)

Authors: Williams, Richard Ryan

Abstract | Document (215 KB) | BibTeX

Power of d Choices with Simple Tabulation

Authors: Aamand, Anders ; Bæk Tejs Knudsen, Mathias ; Thorup, Mikkel

Abstract | Document (910 KB) | BibTeX

One-Way Trail Orientations

Authors: Aamand, Anders ; Hjuler, Niklas ; Holm, Jacob ; Rotenberg, Eva

Abstract | Document (448 KB) | BibTeX

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

Authors: Arar, Moab ; Chechik, Shiri ; Cohen, Sarel ; Stein, Cliff ; Wajc, David

Abstract | Document (524 KB) | BibTeX

Tighter Connections Between Formula-SAT and Shaving Logs

Authors: Abboud, Amir ; Bringmann, Karl

Abstract | Document (504 KB) | BibTeX

New Approximation Algorithms for (1,2)-TSP

Authors: Adamaszek, Anna ; Mnich, Matthias ; Paluch, Katarzyna

Abstract | Document (556 KB) | BibTeX

Union of Hypercubes and 3D Minkowski Sums with Random Sizes

Authors: Agarwal, Pankaj K. ; Kaplan, Haim ; Sharir, Micha

Abstract | Document (528 KB) | BibTeX

Noise-Tolerant Testing of High Entanglement of Formation

Authors: Arnon-Friedman, Rotem ; Yuen, Henry

Abstract | Document (514 KB) | BibTeX

A Complete Dichotomy for Complex-Valued Holant^c

Authors: Backens, Miriam

Abstract | Document (493 KB) | BibTeX

Tight Bounds on Online Checkpointing Algorithms

Authors: Bar-On, Achiya ; Dinur, Itai ; Dunkelman, Orr ; Hod, Rani ; Keller, Nathan ; Ronen, Eyal ; Shamir, Adi

Abstract | Document (488 KB) | BibTeX

Fast Reed-Solomon Interactive Oracle Proofs of Proximity

Authors: Ben-Sasson, Eli ; Bentov, Iddo ; Horesh, Yinon ; Riabzev, Michael

Abstract | Document (549 KB) | BibTeX

NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors

Authors: Bhangale, Amey

Abstract | Document (562 KB) | BibTeX

Sublinear Algorithms for MAXCUT and Correlation Clustering

Authors: Bhaskara, Aditya ; Daruki, Samira ; Venkatasubramanian, Suresh

Abstract | Document (524 KB) | BibTeX

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

Authors: Bhattacharyya, Arnab ; Ghoshal, Suprovat ; C. S., Karthik ; Manurangsi, Pasin

Abstract | Document (598 KB) | BibTeX

Rollercoasters and Caterpillars

Authors: Biedl, Therese ; Biniaz, Ahmad ; Cummings, Robert ; Lubiw, Anna ; Manea, Florin ; Nowotka, Dirk ; Shallit, Jeffrey

Abstract | Document (836 KB) | BibTeX

New algorithms for Steiner tree reoptimization

Authors: Bilò, Davide

Abstract | Document (565 KB) | BibTeX

Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

Authors: Bläsius, Thomas ; Freiberger, Cedric ; Friedrich, Tobias ; Katzmann, Maximilian ; Montenegro-Retana, Felix ; Thieffry, Marianne

Abstract | Document (793 KB) | BibTeX

Approximate Convex Hull of Data Streams

Authors: Blum, Avrim ; Braverman, Vladimir ; Kumar, Ananya ; Lang, Harry ; Yang, Lin F.

Abstract | Document (600 KB) | BibTeX

Small Bias Requires Large Formulas

Authors: Bogdanov, Andrej

Abstract | Document (433 KB) | BibTeX

Geodesic Obstacle Representation of Graphs

Authors: Bose, Prosenjit ; Carmi, Paz ; Dujmovic, Vida ; Mehrabi, Saeed ; Montecchiani, Fabrizio ; Morin, Pat ; Silveira, Luis Fernando Schultz Xavier da

Abstract | Document (523 KB) | BibTeX

The Bottleneck Complexity of Secure Multiparty Computation

Authors: Boyle, Elette ; Jain, Abhishek ; Prabhakaran, Manoj ; Yu, Ching-Hua

Abstract | Document (531 KB) | BibTeX

Revisiting Frequency Moment Estimation in Random Order Streams

Authors: Braverman, Vladimir ; Viola, Emanuele ; Woodruff, David P. ; Yang, Lin F.

Abstract | Document (618 KB) | BibTeX

Proportional Approval Voting, Harmonic k-median, and Negative Association

Authors: Byrka, Jaroslaw ; Skowron, Piotr ; Sornat, Krzysztof

Abstract | Document (553 KB) | BibTeX

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

Authors: Carmosino, Marco L. ; Impagliazzo, Russell ; Sabin, Manuel

Abstract | Document (488 KB) | BibTeX

Ranking with Fairness Constraints

Authors: Celis, L. Elisa ; Straszak, Damian ; Vishnoi, Nisheeth K.

Abstract | Document (520 KB) | BibTeX

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median

Authors: Chakrabarty, Deeparnab ; Swamy, Chaitanya

Abstract | Document (540 KB) | BibTeX

Generalized Center Problems with Outliers

Authors: Chakrabarty, Deeparnab ; Negahbani, Maryam

Abstract | Document (519 KB) | BibTeX

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d

Authors: Chan, Timothy M. ; Nekrich, Yakov ; Rahul, Saladi ; Tsakalidis, Konstantinos

Abstract | Document (544 KB) | BibTeX

Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition

Authors: Chandran, L. Sunil ; Cheung, Yun Kuen ; Issac, Davis

Abstract | Document (502 KB) | BibTeX

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier

Authors: Charikar, Moses ; Solomon, Shay

Abstract | Document (459 KB) | BibTeX

On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings

Authors: Charikar, Moses ; Geri, Ofir ; Kim, Michael P. ; Kuszmaul, William

Abstract | Document (483 KB) | BibTeX

How Hard Is It to Satisfy (Almost) All Roommates?

Authors: Chen, Jiehua ; Hermelin, Danny ; Sorge, Manuel ; Yedidsion, Harel

Abstract | Document (623 KB) | BibTeX

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas

Authors: Chillara, Suryajith ; Limaye, Nutan ; Srinivasan, Srikanth

Abstract | Document (560 KB) | BibTeX

Restricted Max-Min Fair Allocation

Authors: Cheng, Siu-Wing ; Mao, Yuchen

Abstract | Document (486 KB) | BibTeX

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

Authors: Chuzhoy, Julia ; Kim, David H. K. ; Nimavat, Rachit

Abstract | Document (676 KB) | BibTeX

Optimal Hashing in External Memory

Authors: Conway, Alex ; Farach-Colton, Martín ; Shilane, Philip

Abstract | Document (503 KB) | BibTeX

Lovász Meets Weisfeiler and Leman

Authors: Dell, Holger ; Grohe, Martin ; Rattan, Gaurav

Abstract | Document (433 KB) | BibTeX

Sample-Optimal Identity Testing with High Probability

Authors: Diakonikolas, Ilias ; Gouleakis, Themis ; Peebles, John ; Price, Eric

Abstract | Document (500 KB) | BibTeX

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

Authors: Duan, Ran ; Ren, Hanlin

Abstract | Document (458 KB) | BibTeX

Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

Authors: Duan, Ran ; Lyu, Kaifeng ; Xie, Yuanhang

Abstract | Document (470 KB) | BibTeX

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

Authors: Duan, Ran ; Gu, Yong ; Zhang, Le

Abstract | Document (500 KB) | BibTeX

Edit Distance between Unrooted Trees in Cubic Time

Authors: Dudek, Bartlomiej ; Gawrychowski, Pawel

Abstract | Document (670 KB) | BibTeX

A Note on Two-Colorability of Nonuniform Hypergraphs

Authors: Duraj, Lech ; Gutowski, Grzegorz ; Kozik, Jakub

Abstract | Document (452 KB) | BibTeX

Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes

Authors: Dvorák, Zdenek ; Kawarabayashi, Ken-ichi

Abstract | Document (444 KB) | BibTeX

How to Navigate Through Obstacles?

Authors: Eiben, Eduard ; Kanj, Iyad

Abstract | Document (502 KB) | BibTeX

Faster Algorithms for Integer Programs with Block Structure

Authors: Eisenbrand, Friedrich ; Hunkenschröder, Christoph ; Klein, Kim-Manuel

Abstract | Document (465 KB) | BibTeX

On the Probe Complexity of Local Computation Algorithms

Authors: Feige, Uriel ; Patt-Shamir, Boaz ; Vardi, Shai

Abstract | Document (514 KB) | BibTeX

Fully-Dynamic Bin Packing with Little Repacking

Authors: Feldkord, Björn ; Feldotto, Matthias ; Gupta, Anupam ; Guruganesh, Guru ; Kumar, Amit ; Riechers, Sören ; Wajc, David

Abstract | Document (707 KB) | BibTeX

A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error

Authors: Fichtenberger, Hendrik ; Levi, Reut ; Vasudev, Yadu ; Wötzel, Maximilian

Abstract | Document (504 KB) | BibTeX

Parameterized Low-Rank Binary Matrix Approximation

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Panolan, Fahad

Abstract | Document (589 KB) | BibTeX

Towards Blackbox Identity Testing of Log-Variate Circuits

Authors: Forbes, Michael A. ; Ghosh, Sumanta ; Saxena, Nitin

Abstract | Document (536 KB) | BibTeX

Finding Cliques in Social Networks: A New Distribution-Free Model

Authors: Fox, Jacob ; Roughgarden, Tim ; Seshadhri, C. ; Wei, Fan ; Wein, Nicole

Abstract | Document (586 KB) | BibTeX

A PTAS for a Class of Stochastic Dynamic Programs

Authors: Fu, Hao ; Li, Jian ; Xu, Pan

Abstract | Document (604 KB) | BibTeX

Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

Authors: Gamlath, Buddhima ; Huang, Sangxia ; Svensson, Ola

Abstract | Document (537 KB) | BibTeX

High Probability Frequency Moment Sketches

Authors: Ganguly, Sumit ; Woodruff, David P.

Abstract | Document (708 KB) | BibTeX

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies

Authors: Garg, Shashwat

Abstract | Document (467 KB) | BibTeX

ARRIVAL: Next Stop in CLS

Authors: Gärtner, Bernd ; Hansen, Thomas Dueholm ; Hubácek, Pavel ; Král, Karel ; Mosaad, Hagar ; Slívová, Veronika

Abstract | Document (588 KB) | BibTeX

Improved Bounds for Shortest Paths in Dense Distance Graphs

Authors: Gawrychowski, Pawel ; Karczmarz, Adam

Abstract | Document (543 KB) | BibTeX

Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance

Authors: Gawrychowski, Pawel ; Uznanski, Przemyslaw

Abstract | Document (561 KB) | BibTeX

A Faster Construction of Greedy Consensus Trees

Authors: Gawrychowski, Pawel ; Landau, Gad M. ; Sung, Wing-Kin ; Weimann, Oren

Abstract | Document (497 KB) | BibTeX

A Faster FPTAS for #Knapsack

Authors: Gawrychowski, Pawel ; Markin, Liran ; Weimann, Oren

Abstract | Document (485 KB) | BibTeX

Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams

Authors: Golan, Shay ; Kopelowitz, Tsvi ; Porat, Ely

Abstract | Document (682 KB) | BibTeX

Gray Codes and Symmetric Chains

Authors: Gregor, Petr ; Jäger, Sven ; Mütze, Torsten ; Sawada, Joe ; Wille, Kaja

Abstract | Document (651 KB) | BibTeX

An Improved Isomorphism Test for Bounded-Tree-Width Graphs

Authors: Grohe, Martin ; Neuen, Daniel ; Schweitzer, Pascal ; Wiebking, Daniel

Abstract | Document (443 KB) | BibTeX

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

Authors: Guo, Heng ; Jerrum, Mark

Abstract | Document (505 KB) | BibTeX

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

Authors: Guo, Heng ; Jerrum, Mark

Abstract | Document (500 KB) | BibTeX

Non-Preemptive Flow-Time Minimization via Rejections

Authors: Gupta, Anupam ; Kumar, Amit ; Li, Jason

Abstract | Document (442 KB) | BibTeX

Maximizing Profit with Convex Costs in the Random-order Model

Authors: Gupta, Anupam ; Mehta, Ruta ; Molinaro, Marco

Abstract | Document (634 KB) | BibTeX

Generic Single Edge Fault Tolerant Exact Distance Oracle

Authors: Gupta, Manoj ; Singh, Aditi

Abstract | Document (488 KB) | BibTeX

An Exponential Separation Between MA and AM Proofs of Proximity

Authors: Gur, Tom ; Liu, Yang P. ; Rothblum, Ron D.

Abstract | Document (554 KB) | BibTeX

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Authors: Gurjar, Rohit ; Thierauf, Thomas ; Vishnoi, Nisheeth K.

Abstract | Document (474 KB) | BibTeX

Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions

Authors: Haeupler, Bernhard ; Shahrasbi, Amirbehshad ; Vitercik, Ellen

Abstract | Document (452 KB) | BibTeX

Synchronization Strings: List Decoding for Insertions and Deletions

Authors: Haeupler, Bernhard ; Shahrasbi, Amirbehshad ; Sudan, Madhu

Abstract | Document (468 KB) | BibTeX

Approximate Sparse Linear Regression

Authors: Har-Peled, Sariel ; Indyk, Piotr ; Mahabadi, Sepideh

Abstract | Document (623 KB) | BibTeX

A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes

Authors: Hayashi, Koyo

Abstract | Document (695 KB) | BibTeX

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

Authors: Huang, Zhiyi ; Tang, Zhihao Gavin ; Wu, Xiaowei ; Zhang, Yuhao

Abstract | Document (909 KB) | BibTeX

Finding Branch-Decompositions of Matroids, Hypergraphs, and More

Authors: Jeong, Jisu ; Kim, Eun Jung ; Oum, Sang-il

Abstract | Document (528 KB) | BibTeX

Optimally Sorting Evolving Data

Authors: Besa, Juan Jose ; Devanny, William E. ; Eppstein, David ; Goodrich, Michael T. ; Johnson, Timothy

Abstract | Document (637 KB) | BibTeX

Generalized Comparison Trees for Point-Location Problems

Authors: Kane, Daniel M. ; Lovett, Shachar ; Moran, Shay

Abstract | Document (478 KB) | BibTeX

Stabilizing Weighted Graphs

Authors: Koh, Zhuan Khye ; Sanità, Laura

Abstract | Document (474 KB) | BibTeX

Spectrally Robust Graph Isomorphism

Authors: Kolla, Alexandra ; Koutis, Ioannis ; Madan, Vivek ; Sinop, Ali Kemal

Abstract | Document (508 KB) | BibTeX

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

Authors: Koutecký, Martin ; Levin, Asaf ; Onn, Shmuel

Abstract | Document (587 KB) | BibTeX

Finer Tight Bounds for Coloring on Clique-Width

Authors: Lampis, Michael

Abstract | Document (455 KB) | BibTeX

A Centralized Local Algorithm for the Sparse Spanning Graph Problem

Authors: Lenzen, Christoph ; Levi, Reut

Abstract | Document (482 KB) | BibTeX

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

Authors: Liu, Sixue

Abstract | Document (549 KB) | BibTeX

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

Authors: Barequet, Gill ; Eppstein, David ; Goodrich, Michael T. ; Mamano, Nil

Abstract | Document (990 KB) | BibTeX

Improved Algorithms for Adaptive Compressed Sensing

Authors: Nakos, Vasileios ; Shi, Xiaofei ; Woodruff, David P. ; Zhang, Hongyang

Abstract | Document (577 KB) | BibTeX

Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States

Authors: Nirkhe, Chinmay ; Vazirani, Umesh ; Yuen, Henry

Abstract | Document (426 KB) | BibTeX

Fully Dynamic MIS in Uniformly Sparse Graphs

Authors: Onak, Krzysztof ; Schieber, Baruch ; Solomon, Shay ; Wein, Nicole

Abstract | Document (437 KB) | BibTeX

Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration

Authors: Ostrovsky, Rafail ; Rabani, Yuval ; Yousefi, Arman

Abstract | Document (497 KB) | BibTeX

Parameterized Algorithms for Zero Extension and Metric Labelling Problems

Authors: Reidl, Felix ; Wahlström, Magnus

Abstract | Document (511 KB) | BibTeX

An Operational Characterization of Mutual Information in Algorithmic Information Theory

Authors: Romashchenko, Andrei ; Zimand, Marius

Abstract | Document (414 KB) | BibTeX

Privacy Preserving Clustering with Constraints

Authors: Rösner, Clemens ; Schmidt, Melanie

Abstract | Document (410 KB) | BibTeX

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

Authors: Sankowski, Piotr

Abstract | Document (515 KB) | BibTeX

Computing Tutte Paths

Authors: Schmid, Andreas ; Schmidt, Jens M.

Abstract | Document (768 KB) | BibTeX

A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity

Authors: Soma, Tasuku ; Yoshida, Yuichi

Abstract | Document (496 KB) | BibTeX

Ring Packing and Amortized FHEW Bootstrapping

Authors: Miccianco, Daniele ; Sorrell, Jessica

Abstract | Document (506 KB) | BibTeX

Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

Authors: Louis, Anand ; Venkat, Rakesh

Abstract | Document (558 KB) | BibTeX

Load Thresholds for Cuckoo Hashing with Overlapping Blocks

Authors: Walzer, Stefan

Abstract | Document (483 KB) | BibTeX

Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC

Authors: Agarwal, Navneet ; Anand, Sanat ; Prabhakaran, Manoj

Abstract | Document (301 KB) | BibTeX

Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

Authors: Babay, Amy ; Dinitz, Michael ; Zhang, Zeyu

Abstract | Document (285 KB) | BibTeX

Brief Announcement: Zero-Knowledge Protocols for Search Problems

Authors: Berger, Ben ; Brakerski, Zvika

Abstract | Document (247 KB) | BibTeX

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels

Authors: Blocki, Jeremiah ; Gandikota, Venkata ; Grigorescu, Elena ; Zhou, Samson

Abstract | Document (305 KB) | BibTeX

Brief Announcement: Approximation Schemes for Geometric Coverage Problems

Authors: Chaplick, Steven ; De, Minati ; Ravsky, Alexander ; Spoerhase, Joachim

Abstract | Document (389 KB) | BibTeX

Brief Announcement: Bayesian Auctions with Efficient Queries

Authors: Chen, Jing ; Li, Bo ; Li, Yingkai ; Lu, Pinyan

Abstract | Document (334 KB) | BibTeX

Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication

Authors: Graf, Daniel ; Labib, Karim ; Uznanski, Przemyslaw

Abstract | Document (417 KB) | BibTeX

Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS

Authors: Lokshtanov, Daniel ; Ramanujan, M. S. ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

Abstract | Document (390 KB) | BibTeX

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors

Authors: Raskhodnikova, Sofya ; Varma, Nithin

Abstract | Document (249 KB) | BibTeX

Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable

Authors: Xiao, Mingyu ; Nagamochi, Hiroshi

Abstract | Document (398 KB) | BibTeX

Almost Sure Productivity

Authors: Aguirre, Alejandro ; Barthe, Gilles ; Hsu, Justin ; Silva, Alexandra

Abstract | Document (461 KB) | BibTeX

O-Minimal Invariants for Linear Loops

Authors: Almagor, Shaull ; Chistikov, Dmitry ; Ouaknine, Joël ; Worrell, James

Abstract | Document (616 KB) | BibTeX

Topological Sorting with Regular Constraints

Authors: Amarilli, Antoine ; Paperman, Charles

Abstract | Document (451 KB) | BibTeX

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface

Authors: Atserias, Albert ; Kreutzer, Stephan ; Noy, Marc

Abstract | Document (473 KB) | BibTeX

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Authors: Blumensath, Achim ; Wolf, Felix

Abstract | Document (458 KB) | BibTeX

Binary Reachability of Timed Pushdown Automata via Quantifier Elimination and Cyclic Order Atoms

Authors: Clemente, Lorenzo ; Lasota, Slawomir

Abstract | Document (547 KB) | BibTeX

Unboundedness Problems for Languages of Vector Addition Systems

Authors: Czerwinski, Wojciech ; Hofman, Piotr ; Zetzsche, Georg

Abstract | Document (516 KB) | BibTeX

Reachability and Distances under Multiple Changes

Authors: Datta, Samir ; Mukherjee, Anish ; Vortmeier, Nils ; Zeume, Thomas

Abstract | Document (470 KB) | BibTeX

When is Containment Decidable for Probabilistic Automata?

Authors: Daviaud, Laure ; Jurdzinski, Marcin ; Lazic, Ranko ; Mazowiecki, Filip ; Pérez, Guillermo A. ; Worrell, James

Abstract | Document (553 KB) | BibTeX

On the Complexity of Infinite Advice Strings

Authors: Douéneau-Tabot, Gaëtan

Abstract | Document (548 KB) | BibTeX

Resynchronizing Classes of Word Relations

Authors: Descotte, María Emilia ; Figueira, Diego ; Puppis, Gabriele

Abstract | Document (675 KB) | BibTeX

Reachability Switching Games

Authors: Fearnley, John ; Gairing, Martin ; Mnich, Matthias ; Savani, Rahul

Abstract | Document (478 KB) | BibTeX

Costs and Rewards in Priced Timed Automata

Authors: Fränzle, Martin ; Shirmohammadi, Mahsa ; Swaminathan, Mani ; Worrell, James

Abstract | Document (512 KB) | BibTeX

First-Order Interpretations of Bounded Expansion Classes

Authors: Gajarský, Jakub ; Kreutzer, Stephan ; Nesetril, Jaroslav ; Ossona de Mendez, Patrice ; Pilipczuk, Michal ; Siebertz, Sebastian ; Torunczyk, Szymon

Abstract | Document (516 KB) | BibTeX

Randomized Sliding Window Algorithms for Regular Languages

Authors: Ganardi, Moses ; Hucke, Danny ; Lohrey, Markus

Abstract | Document (481 KB) | BibTeX

Aperiodic Points in Z²-subshifts

Authors: Grandjean, Anael ; Hellouin de Menibus, Benjamin ; Vanier, Pascal

Abstract | Document (521 KB) | BibTeX

Semicomputable Geometry

Authors: Hoyrup, Mathieu ; Nava Saucedo, Diego ; Stull, Don M.

Abstract | Document (516 KB) | BibTeX

On Computing the Total Variation Distance of Hidden Markov Models

Authors: Kiefer, Stefan

Abstract | Document (416 KB) | BibTeX

To Infinity and Beyond

Authors: Klimann, Ines

Abstract | Document (395 KB) | BibTeX

On the Identity Problem for the Special Linear Group and the Heisenberg Group

Authors: Ko, Sang-Ki ; Niskanen, Reino ; Potapov, Igor

Abstract | Document (538 KB) | BibTeX

Gaifman Normal Forms for Counting Extensions of First-Order Logic

Authors: Kuske, Dietrich ; Schweikardt, Nicole

Abstract | Document (513 KB) | BibTeX

Polynomial Vector Addition Systems With States

Authors: Leroux, Jérôme

Abstract | Document (471 KB) | BibTeX

Reducing CMSO Model Checking to Highly Connected Graphs

Authors: Lokshtanov, Daniel ; Ramanujan, M. S. ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (542 KB) | BibTeX

An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences

Authors: Nowotka, Dirk ; Saarela, Aleksi

Abstract | Document (423 KB) | BibTeX

Separating Without Any Ambiguity

Authors: Place, Thomas ; Zeitoun, Marc

Abstract | Document (506 KB) | BibTeX

A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton

Authors: Raskin, Mikhail

Abstract | Document (440 KB) | BibTeX

The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE

Authors: Sénizergues, Géraud ; Weiß, Armin

Abstract | Document (481 KB) | BibTeX

Unambiguous Languages Exhaust the Index Hierarchy

Authors: Skrzypczak, Michal

Abstract | Document (516 KB) | BibTeX

The Beta-Bernoulli process and algebraic effects

Authors: Staton, Sam ; Stein, Dario ; Yang, Hongseok ; Ackerman, Nathanael L. ; Freer, Cameron E. ; Roy, Daniel M.

Abstract | Document (523 KB) | BibTeX

Uniformization Problems for Synchronizations of Automatic Relations on Words

Authors: Winter, Sarah

Abstract | Document (534 KB) | BibTeX

Congestion-Free Rerouting of Flows on DAGs

Authors: Akhoondian Amiri, Saeed ; Dudycz, Szymon ; Schmid, Stefan ; Wiederrecht, Sebastian

Abstract | Document (509 KB) | BibTeX

Practical and Provably Secure Onion Routing

Authors: Ando, Megumi ; Lysyanskaya, Anna ; Upfal, Eli

Abstract | Document (485 KB) | BibTeX

Resolving SINR Queries in a Dynamic Setting

Authors: Aronov, Boris ; Bar-On, Gali ; Katz, Matthew J.

Abstract | Document (618 KB) | BibTeX

Uniform Mixed Equilibria in Network Congestion Games with Link Failures

Authors: Bilò, Vittorio ; Moscardelli, Luca ; Vinci, Cosimo

Abstract | Document (499 KB) | BibTeX

Byzantine Gathering in Polynomial Time

Authors: Bouchard, Sébastien ; Dieudonné, Yoann ; Lamani, Anissa

Abstract | Document (430 KB) | BibTeX

Temporal Vertex Cover with a Sliding Time Window

Authors: Akrida, Eleni C. ; Mertzios, George B. ; Spirakis, Paul G. ; Zamaraev, Viktor

Abstract | Document (534 KB) | BibTeX

On the Complexity of Sampling Vertices Uniformly from a Graph

Authors: Chierichetti, Flavio ; Haddadan, Shahrzad

Abstract | Document (525 KB) | BibTeX

The Price of Stability of Weighted Congestion Games

Authors: Christodoulou, George ; Gairing, Martin ; Giannakopoulos, Yiannis ; Spirakis, Paul G.

Abstract | Document (508 KB) | BibTeX

Demand-Independent Optimal Tolls

Authors: Colini-Baldeschi, Riccardo ; Klimm, Max ; Scarsini, Marco

Abstract | Document (453 KB) | BibTeX

Greedy Algorithms for Online Survivable Network Design

Authors: Dehghani, Sina ; Ehsani, Soheil ; Hajiaghayi, MohammadTaghi ; Liaghat, Vahid ; Seddighin, Saeed

Abstract | Document (464 KB) | BibTeX

Algorithms for Noisy Broadcast with Erasures

Authors: Grossman, Ofer ; Haeupler, Bernhard ; Mohanty, Sidhanth

Abstract | Document (436 KB) | BibTeX

Efficient Black-Box Reductions for Separable Cost Sharing

Authors: Harks, Tobias ; Hoefer, Martin ; Huber, Anja ; Surek, Manuel

Abstract | Document (509 KB) | BibTeX

Price of Anarchy for Mechanisms with Risk-Averse Agents

Authors: Kesselheim, Thomas ; Kodric, Bojana

Abstract | Document (476 KB) | BibTeX

Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations

Authors: Kowalski, Dariusz R. ; Mosteiro, Miguel A.

Abstract | Document (501 KB) | BibTeX

The Unfortunate-Flow Problem

Authors: Kupferman, Orna ; Vardi, Gal

Abstract | Document (668 KB) | BibTeX

Spanning Trees With Edge Conflicts and Wireless Connectivity

Authors: Halldórsson, Magnús M. ; Kortsarz, Guy ; Mitra, Pradipta ; Tonoyan, Tigran

Abstract | Document (424 KB) | BibTeX

Eigenvector Computation and Community Detection in Asynchronous Gossip Models

Authors: Mallmann-Trenn, Frederik ; Musco, Cameron ; Musco, Christopher

Abstract | Document (525 KB) | BibTeX

(Delta+1) Coloring in the Congested Clique Model

Authors: Parter, Merav

Abstract | Document (886 KB) | BibTeX

CacheShuffle: A Family of Oblivious Shuffles

Authors: Patel, Sarvar ; Persiano, Giuseppe ; Yeo, Kevin

Abstract | Document (436 KB) | BibTeX

Brief Announcement: MapReduce Algorithms for Massive Trees

Authors: Bateni, MohammadHossein ; Behnezhad, Soheil ; Derakhshan, Mahsa ; Hajiaghayi, MohammadTaghi ; Mirrokni, Vahab

Abstract | Document (267 KB) | BibTeX

Brief Announcement: Give Me Some Slack: Efficient Network Measurements

Authors: Ben Basat, Ran ; Einziger, Gil ; Friedman, Roy

Abstract | Document (394 KB) | BibTeX

Brief Announcement: Towards an Abstract Model of User Retention Dynamics

Authors: Ben-Sasson, Eli ; Saig, Eden

Abstract | Document (238 KB) | BibTeX

Brief Announcement: Energy Constrained Depth First Search

Authors: Das, Shantanu ; Dereniowski, Dariusz ; Uznanski, Przemyslaw

Abstract | Document (356 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)