Portal - ICALP 2017

ICALP 2017	July 10-14, 2017 - Warsaw, Poland
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl (Eds.)
ISBN 978-3-95977-041-5, LIPICS Vol. 80	ISSN 1868-8969

Additional Information

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

Authors

Chakrabarty, Deeparnab

Chalopin, Jérémie

Chatzigiannakis, Ioannis

Dueholm Hansen, Thomas

Giannakopoulos, Yiannis

Giannopoulou, Archontia C.

Guruswami, Venkatesan

Gutin, Gregory

Göös, Mika

Haase, Christoph

Hajiaghayi, MohammadTaghi

Halldórsson, Magnús M.

Italiano, Giuseppe F.

Knudsen, Mathias Bæk Tejs

Krinninger, Sebastian

Lambilliotte, Antonin

Mamouras, Konstantinos

Pallavoor, Ramesh Krishnan S.

Raskin, Jean-François

Raskin, Mikhail

Raymond, Jean-Florent

Scheideler, Christian

Schwiegelshohn, Chris

Sivan, Balasubramanian

Thilikos, Dimitrios M.

Varvitsiotis, Antonios

Vassilevska Williams, Virginia

Williamson, Christopher

Ásgeirsson, Eyjólfur I.

Front Matter, Table of Contents, Preface, Organization, List of Authors

Authors: Chatzigiannakis, Ioannis ; Indyk, Piotr ; Kuhn, Fabian ; Muscholl, Anca

Abstract | Document (483 KB) | BibTeX

Orbit-Finite Sets and Their Algorithms (Invited Talk)

Authors: Bojanczyk, Mikolaj

Abstract | Document (1,543 KB) | BibTeX

Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk)

Authors: Henzinger, Monika

Abstract | Document (216 KB) | BibTeX

Local Computation Algorithms (Invited Talk)

Authors: Rubinfeld, Ronitt

Abstract | Document (217 KB) | BibTeX

Fast and Powerful Hashing Using Tabulation (Invited Talk)

Authors: Thorup, Mikkel

Abstract | Document (350 KB) | BibTeX

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

Authors: Baleshzar, Roksana ; Chakrabarty, Deeparnab ; Pallavoor, Ramesh Krishnan S. ; Raskhodnikova, Sofya ; Seshadhri, C.

Abstract | Document (627 KB) | BibTeX

Sublinear Random Access Generators for Preferential Attachment Graphs

Authors: Even, Guy ; Levi, Reut ; Medina, Moti ; Rosén, Adi

Abstract | Document (626 KB) | BibTeX

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection

Authors: Eden, Talya ; Ron, Dana ; Seshadhri, C.

Abstract | Document (549 KB) | BibTeX

Near-Optimal Closeness Testing of Discrete Histogram Distributions

Authors: Diakonikolas, Ilias ; Kane, Daniel M. ; Nikishkin, Vladimir

Abstract | Document (535 KB) | BibTeX

Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays

Authors: Ben-Eliezer, Omri ; Korman, Simon ; Reichman, Daniel

Abstract | Document (536 KB) | BibTeX

On the Value of Penalties in Time-Inconsistent Planning

Authors: Albers, Susanne ; Kraft, Dennis

Abstract | Document (529 KB) | BibTeX

Efficient Approximations for the Online Dispersion Problem

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

Abstract | Document (535 KB) | BibTeX

Online Covering with Sum of $ell_q$-Norm Objectives

Authors: Nagarajan, Viswanath ; Shen, Xiangkun

Abstract | Document (890 KB) | BibTeX

Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration

Authors: Bienkowski, Marcin ; Byrka, Jaroslaw ; Mucha, Marcin

Abstract | Document (570 KB) | BibTeX

The Infinite Server Problem

Authors: Coester, Christian ; Koutsoupias, Elias ; Lazos, Philip

Abstract | Document (528 KB) | BibTeX

Quantum Automata Cannot Detect Biased Coins, Even in the Limit

Authors: Kindler, Guy ; O'Donnell, Ryan

Abstract | Document (459 KB) | BibTeX

A New Holant Dichotomy Inspired by Quantum Computation

Authors: Backens, Miriam

Abstract | Document (541 KB) | BibTeX

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Authors: Cleve, Richard ; Wang, Chunhao

Abstract | Document (767 KB) | BibTeX

Controlled Quantum Amplification

Authors: Dohotaru, Catalin ; Høyer, Peter

Abstract | Document (512 KB) | BibTeX

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!

Authors: Jayaram, Rajesh ; Saha, Barna

Abstract | Document (706 KB) | BibTeX

Conditional Lower Bounds for All-Pairs Max-Flow

Authors: Krauthgamer, Robert ; Trabelsi, Ohad

Abstract | Document (794 KB) | BibTeX

On the Fine-Grained Complexity of One-Dimensional Dynamic Programming

Authors: Künnemann, Marvin ; Paturi, Ramamohan ; Schneider, Stefan

Abstract | Document (612 KB) | BibTeX

On Problems Equivalent to (min,+)-Convolution

Authors: Cygan, Marek ; Mucha, Marcin ; Wegrzycki, Karol ; Wlodarczyk, Michal

Abstract | Document (553 KB) | BibTeX

On Finding the Jaccard Center

Authors: Bury, Marc ; Schwiegelshohn, Chris

Abstract | Document (498 KB) | BibTeX

The Polytope-Collision Problem

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

Abstract | Document (565 KB) | BibTeX

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Authors: Gold, Omer ; Sharir, Micha

Abstract | Document (558 KB) | BibTeX

Efficient Construction of Probabilistic Tree Embeddings

Authors: Blelloch, Guy E. ; Gu, Yan ; Sun, Yihan

Abstract | Document (792 KB) | BibTeX

Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems

Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Yang, Kuan

Abstract | Document (606 KB) | BibTeX

Inapproximability of the Independent Set Polynomial Below the Shearer Threshold

Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Stefankovic, Daniel

Abstract | Document (571 KB) | BibTeX

The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights

Authors: Lin, Jiabao ; Wang, Hanpin

Abstract | Document (549 KB) | BibTeX

Polynomial-Time Rademacher Theorem, Porosity and Randomness

Authors: Galicki, Alex

Abstract | Document (540 KB) | BibTeX

A QPTAS for the General Scheduling Problem with Identical Release Dates

Authors: Antoniadis, Antonios ; Hoeksma, Ruben ; Meißner, Julie ; Verschae, José ; Wiese, Andreas

Abstract | Document (519 KB) | BibTeX

Improved Algorithms for MST and Metric-TSP Interdiction

Authors: Linhares, André ; Swamy, Chaitanya

Abstract | Document (565 KB) | BibTeX

Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces

Authors: Kohler, Matthias ; Räcke, Harald

Abstract | Document (421 KB) | BibTeX

Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification

Authors: Chen, Shahar ; Di Castro, Dotan ; Karnin, Zohar ; Lewin-Eytan, Liane ; Naor, Joseph (Seffi) ; Schwartz, Roy

Abstract | Document (514 KB) | BibTeX

When the Optimum is also Blind: a New Perspective on Universal Optimization

Authors: Adamczyk, Marek ; Grandoni, Fabrizio ; Leonardi, Stefano ; Wlodarczyk, Michal

Abstract | Document (582 KB) | BibTeX

Reusable Garbled Deterministic Finite Automata from Learning With Errors

Authors: Agrawal, Shweta ; Singh, Ishaan Preet

Abstract | Document (611 KB) | BibTeX

Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols

Authors: Cohen, Ran ; Coretti, Sandro ; Garay, Juan ; Zikas, Vassilis

Abstract | Document (604 KB) | BibTeX

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Authors: Apon, Daniel ; Döttling, Nico ; Garg, Sanjam ; Mukherjee, Pratyay

Abstract | Document (638 KB) | BibTeX

Non-Uniform Attacks Against Pseudoentropy

Authors: Pietrzak, Krzysztof ; Skorski, Maciej

Abstract | Document (587 KB) | BibTeX

Interactive Oracle Proofs with Constant Rate and Query Complexity

Authors: Ben-Sasson, Eli ; Chiesa, Alessandro ; Gabizon, Ariel ; Riabzev, Michael ; Spooner, Nicholas

Abstract | Document (581 KB) | BibTeX

Dynamic Parameterized Problems and Algorithms

Authors: Alman, Josh ; Mnich, Matthias ; Vassilevska Williams, Virginia

Abstract | Document (574 KB) | BibTeX

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

Authors: Georgiadis, Loukas ; Dueholm Hansen, Thomas ; Italiano, Giuseppe F. ; Krinninger, Sebastian ; Parotsidis, Nikos

Abstract | Document (613 KB) | BibTeX

General Bounds for Incremental Maximization

Authors: Bernstein, Aaron ; Disser, Yann ; Groß, Martin

Abstract | Document (552 KB) | BibTeX

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs

Authors: Bernstein, Aaron

Abstract | Document (456 KB) | BibTeX

Testing Core Membership in Public Goods Economies

Authors: Bodwin, Greg

Abstract | Document (521 KB) | BibTeX

Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting

Authors: Böhnlein, Toni ; Kratsch, Stefan ; Schaudt, Oliver

Abstract | Document (536 KB) | BibTeX

Online Market Intermediation

Authors: Giannakopoulos, Yiannis ; Koutsoupias, Elias ; Lazos, Philip

Abstract | Document (538 KB) | BibTeX

Tight Lower Bounds for Multiplicative Weights Algorithmic Families

Authors: Gravin, Nick ; Peres, Yuval ; Sivan, Balasubramanian

Abstract | Document (553 KB) | BibTeX

The Power of Shared Randomness in Uncertain Communication

Authors: Ghazi, Badih ; Sudan, Madhu

Abstract | Document (572 KB) | BibTeX

Separation of AC^0[oplus] Formulas and Circuits

Authors: Rossman, Benjamin ; Srinivasan, Srikanth

Abstract | Document (528 KB) | BibTeX

Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers

Authors: Lin, Chengyu ; Zhang, Shengyu

Abstract | Document (581 KB) | BibTeX

Randomized Communication vs. Partition Number

Authors: Göös, Mika ; Jayram, T. S. ; Pitassi, Toniann ; Watson, Thomas

Abstract | Document (621 KB) | BibTeX

Approximate Bounded Indistinguishability

Authors: Bogdanov, Andrej ; Williamson, Christopher

Abstract | Document (444 KB) | BibTeX

Finding Detours is Fixed-Parameter Tractable

Authors: Bezáková, Ivona ; Curticapean, Radu ; Dell, Holger ; Fomin, Fedor V.

Abstract | Document (582 KB) | BibTeX

Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs

Authors: Ahmadian, Sara ; Friggstad, Zachary

Abstract | Document (658 KB) | BibTeX

Covering Vectors by Spaces: Regular Matroids

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket

Abstract | Document (493 KB) | BibTeX

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes

Authors: Giannopoulou, Archontia C. ; Pilipczuk, Michal ; Raymond, Jean-Florent ; Thilikos, Dimitrios M. ; Wrochna, Marcin

Abstract | Document (707 KB) | BibTeX

k-Distinct In- and Out-Branchings in Digraphs

Authors: Gutin, Gregory ; Reidl, Felix ; Wahlström, Magnus

Abstract | Document (592 KB) | BibTeX

Fast Regression with an $ell_infty$ Guarantee

Authors: Price, Eric ; Song, Zhao ; Woodruff, David P.

Abstract | Document (576 KB) | BibTeX

Embeddings of Schatten Norms with Applications to Data Streams

Authors: Li, Yi ; Woodruff, David P.

Abstract | Document (535 KB) | BibTeX

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements

Authors: Nakos, Vasileios

Abstract | Document (538 KB) | BibTeX

String Inference from Longest-Common-Prefix Array

Authors: Kärkkäinen, Juha ; Piatkowski, Marcin ; Puglisi, Simon J.

Abstract | Document (549 KB) | BibTeX

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs

Authors: Eickmeyer, Kord ; Giannopoulou, Archontia C. ; Kreutzer, Stephan ; Kwon, O-joung ; Pilipczuk, Michal ; Rabinovich, Roman ; Siebertz, Sebastian

Abstract | Document (577 KB) | BibTeX

Additive Spanners and Distance Oracles in Quadratic Time

Authors: Knudsen, Mathias Bæk Tejs

Abstract | Document (519 KB) | BibTeX

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (628 KB) | BibTeX

A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry

Authors: Schweitzer, Pascal

Abstract | Document (508 KB) | BibTeX

A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time

Authors: Wiese, Andreas

Abstract | Document (527 KB) | BibTeX

Linear-Time Kernelization for Feedback Vertex Set

Authors: Iwata, Yoichi

Abstract | Document (578 KB) | BibTeX

Exact Algorithms via Multivariate Subroutines

Authors: Gaspers, Serge ; Lee, Edward J.

Abstract | Document (554 KB) | BibTeX

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs

Authors: Barbero, Florian ; Paul, Christophe ; Pilipczuk, Michal

Abstract | Document (538 KB) | BibTeX

Packing Cycles Faster Than Erdos-Posa

Authors: Lokshtanov, Daniel ; Mouawad, Amer E. ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (576 KB) | BibTeX

An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model

Authors: Baswana, Surender ; Choudhary, Keerti ; Roditty, Liam

Abstract | Document (583 KB) | BibTeX

Preserving Distances in Very Faulty Graphs

Authors: Bodwin, Greg ; Grandoni, Fabrizio ; Parter, Merav ; Vassilevska Williams, Virginia

Abstract | Document (556 KB) | BibTeX

All-Pairs 2-Reachability in O(n^w log n) Time

Authors: Georgiadis, Loukas ; Graf, Daniel ; Italiano, Giuseppe F. ; Parotsidis, Nikos ; Uznanski, Przemyslaw

Abstract | Document (736 KB) | BibTeX

Edge-Orders

Authors: Schlipf, Lena ; Schmidt, Jens M.

Abstract | Document (607 KB) | BibTeX

Relaxations of Graph Isomorphism

Authors: Mancinska, Laura ; Roberson, David E. ; Samal, Robert ; Severini, Simone ; Varvitsiotis, Antonios

Abstract | Document (538 KB) | BibTeX

Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder

Authors: Rubinstein, Aviad

Abstract | Document (600 KB) | BibTeX

A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

Authors: Manurangsi, Pasin ; Raghavendra, Prasad

Abstract | Document (613 KB) | BibTeX

Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis

Authors: Manurangsi, Pasin

Abstract | Document (547 KB) | BibTeX

On the Bit Complexity of Sum-of-Squares Proofs

Authors: Raghavendra, Prasad ; Weitz, Benjamin

Abstract | Document (555 KB) | BibTeX

The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

Authors: Korman, Amos ; Rodeh, Yoav

Abstract | Document (538 KB) | BibTeX

A Tight Lower Bound for the Capture Time of the Cops and Robbers Game

Authors: Brandt, Sebastian ; Emek, Yuval ; Uitto, Jara ; Wattenhofer, Roger

Abstract | Document (564 KB) | BibTeX

Stochastic Control via Entropy Compression

Authors: Achlioptas, Dimitris ; Iliopoulos, Fotis ; Vlassis, Nikos

Abstract | Document (512 KB) | BibTeX

Approximation Strategies for Generalized Binary Search in Weighted Trees

Authors: Dereniowski, Dariusz ; Kosowski, Adrian ; Uznanski, Przemyslaw ; Zou, Mengchuan

Abstract | Document (666 KB) | BibTeX

Tighter Hard Instances for PPSZ

Authors: Pudlák, Pavel ; Scheder, Dominik ; Talebanfard, Navid

Abstract | Document (574 KB) | BibTeX

Subspace Designs Based on Algebraic Function Fields

Authors: Guruswami, Venkatesan ; Xing, Chaoping ; Yuan, Chen

Abstract | Document (525 KB) | BibTeX

Bipartite Perfect Matching in Pseudo-Deterministic NC

Authors: Goldwasser, Shafi ; Grossman, Ofer

Abstract | Document (505 KB) | BibTeX

A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model

Authors: Raskin, Mikhail

Abstract | Document (504 KB) | BibTeX

Rerouting Flows When Links Fail

Authors: Matuschke, Jannik ; McCormick, S. Thomas ; Oriolo, Gianpaolo

Abstract | Document (550 KB) | BibTeX

The Parameterized Complexity of Positional Games

Authors: Bonnet, Édouard ; Gaspers, Serge ; Lambilliotte, Antonin ; Rümmele, Stefan ; Saffidine, Abdallah

Abstract | Document (552 KB) | BibTeX

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Authors: Björklund, Andreas ; Kaski, Petteri ; Koutis, Ioannis

Abstract | Document (590 KB) | BibTeX

Improved Hardness for Cut, Interdiction, and Firefighter Problems

Authors: Lee, Euiwoong

Abstract | Document (561 KB) | BibTeX

Subspace-Invariant AC^0 Formulas

Authors: Rossman, Benjamin

Abstract | Document (471 KB) | BibTeX

On the Complexity of Quantified Integer Programming

Authors: Chistikov, Dmitry ; Haase, Christoph

Abstract | Document (597 KB) | BibTeX

Word Equations in Nondeterministic Linear Space

Authors: Jez, Artur

Abstract | Document (432 KB) | BibTeX

Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

Authors: Diekert, Volker ; Elder, Murray

Abstract | Document (574 KB) | BibTeX

Pumping Lemma for Higher-order Languages

Authors: Asada, Kazuyuki ; Kobayashi, Naoki

Abstract | Document (609 KB) | BibTeX

A Strategy for Dynamic Programs: Start over and Muddle Through

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

Abstract | Document (567 KB) | BibTeX

Definability by Horn Formulas and Linear Time on Cellular Automata

Authors: Bacquey, Nicolas ; Grandjean, Etienne ; Olive, Frédéric

Abstract | Document (657 KB) | BibTeX

Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment

Authors: Reiter, Fabian

Abstract | Document (527 KB) | BibTeX

A Counterexample to Thiagarajan's Conjecture on Regular Event Structures

Authors: Chalopin, Jérémie ; Chepoi, Victor

Abstract | Document (585 KB) | BibTeX

*-Liftings for Differential Privacy

Authors: Barthe, Gilles ; Espitau, Thomas ; Hsu, Justin ; Sato, Tetsuya ; Strub, Pierre-Yves

Abstract | Document (584 KB) | BibTeX

Bisimulation Metrics for Weighted Automata

Authors: Balle, Borja ; Gourdeau, Pascale ; Panangaden, Prakash

Abstract | Document (534 KB) | BibTeX

On the Metric-Based Approximate Minimization of Markov Chains

Authors: Bacci, Giovanni ; Bacci, Giorgio ; Larsen, Kim G. ; Mardare, Radu

Abstract | Document (603 KB) | BibTeX

Expressiveness of Probabilistic Modal Logics, Revisited

Authors: Fijalkow, Nathanaël ; Klin, Bartek ; Panangaden, Prakash

Abstract | Document (490 KB) | BibTeX

Emptiness of Zero Automata Is Decidable

Authors: Bojanczyk, Mikolaj ; Gimbert, Hugo ; Kelmendi, Edon

Abstract | Document (555 KB) | BibTeX

Characterizing Definability in Decidable Fixpoint Logics

Authors: Benedikt, Michael ; Bourhis, Pierre ; Vanden Boom, Michael

Abstract | Document (556 KB) | BibTeX

Conservative Extensions in Guarded and Two-Variable Fragments

Authors: Jung, Jean Christoph ; Lutz, Carsten ; Martel, Mauricio ; Schneider, Thomas ; Wolter, Frank

Abstract | Document (584 KB) | BibTeX

Models and Termination of Proof Reduction in the lambda Pi-Calculus Modulo Theory

Authors: Dowek, Gilles

Abstract | Document (472 KB) | BibTeX

Proof Complexity Meets Algebra

Authors: Atserias, Albert ; Ochremiak, Joanna

Abstract | Document (482 KB) | BibTeX

A Circuit-Based Approach to Efficient Enumeration

Authors: Amarilli, Antoine ; Bourhis, Pierre ; Jachiet, Louis ; Mengel, Stefan

Abstract | Document (498 KB) | BibTeX

Automata-Based Stream Processing

Authors: Alur, Rajeev ; Mamouras, Konstantinos ; Stanford, Caleb

Abstract | Document (609 KB) | BibTeX

On Reversible Transducers

Authors: Dartois, Luc ; Fournier, Paulin ; Jecker, Ismaël ; Lhote, Nathan

Abstract | Document (547 KB) | BibTeX

Which Classes of Origin Graphs Are Generated by Transducers

Authors: Bojanczyk, Mikolaj ; Daviaud, Laure ; Guillon, Bruno ; Penelle, Vincent

Abstract | Document (8,549 KB) | BibTeX

Continuity and Rational Functions

Authors: Cadilhac, Michaël ; Carton, Olivier ; Paperman, Charles

Abstract | Document (547 KB) | BibTeX

A Universal Ordinary Differential Equation

Authors: Bournez, Olivier ; Pouly, Amaury

Abstract | Document (579 KB) | BibTeX

Regular Separability of Parikh Automata

Authors: Clemente, Lorenzo ; Czerwinski, Wojciech ; Lasota, Slawomir ; Paperman, Charles

Abstract | Document (538 KB) | BibTeX

An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention

Authors: Boigelot, Bernard ; Mainz, Isabelle ; Marsault, Victor ; Rigo, Michel

Abstract | Document (557 KB) | BibTeX

Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One

Authors: Figueira, Diego ; Lazic, Ranko ; Leroux, Jérôme ; Mazowiecki, Filip ; Sutre, Grégoire

Abstract | Document (784 KB) | BibTeX

Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption

Authors: Bozzelli, Laura ; Molinari, Alberto ; Montanari, Angelo ; Peron, Adriano ; Sala, Pietro

Abstract | Document (631 KB) | BibTeX

Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes

Authors: Berthon, Raphaël ; Randour, Mickael ; Raskin, Jean-François

Abstract | Document (668 KB) | BibTeX

Synchronizability of Communicating Finite State Machines is not Decidable

Authors: Finkel, Alain ; Lozes, Etienne

Abstract | Document (588 KB) | BibTeX

Admissiblity in Concurrent Games

Authors: Basset, Nicolas ; Geeraerts, Gilles ; Raskin, Jean-François ; Sankur, Ocan

Abstract | Document (671 KB) | BibTeX

Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs

Authors: Bringmann, Karl ; Dueholm Hansen, Thomas ; Krinninger, Sebastian

Abstract | Document (551 KB) | BibTeX

Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems

Authors: Bilò, Vittorio ; Caragiannis, Ioannis ; Fanelli, Angelo ; Flammini, Michele ; Monaco, Gianpiero

Abstract | Document (529 KB) | BibTeX

Stochastic k-Server: How Should Uber Work?

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

Abstract | Document (560 KB) | BibTeX

Multiple Source Dual Fault Tolerant BFS Trees

Authors: Gupta, Manoj ; Khan, Shahbaz

Abstract | Document (596 KB) | BibTeX

Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Authors: Abrahamsen, Mikkel ; Alstrup, Stephen ; Holm, Jacob ; Knudsen, Mathias Bæk Tejs ; Stöckel, Morten

Abstract | Document (572 KB) | BibTeX

Universal Framework for Wireless Scheduling Problems

Authors: Ásgeirsson, Eyjólfur I. ; Halldórsson, Magnús M. ; Tonoyan, Tigran

Abstract | Document (563 KB) | BibTeX

Streaming Communication Protocols

Authors: Boczkowski, Lucas ; Kerenidis, Iordanis ; Magniez, Frédéric

Abstract | Document (602 KB) | BibTeX

Testable Bounded Degree Graph Properties Are Random Order Streamable

Authors: Monemizadeh, Morteza ; Muthukrishnan, S. ; Peng, Pan ; Sohler, Christian

Abstract | Document (515 KB) | BibTeX

Deterministic Graph Exploration with Advice

Authors: Gorain, Barun ; Pelc, Andrzej

Abstract | Document (566 KB) | BibTeX

Combinatorial Secretary Problems with Ordinal Information

Authors: Hoefer, Martin ; Kodric, Bojana

Abstract | Document (544 KB) | BibTeX

Selling Complementary Goods: Dynamics, Efficiency and Revenue

Authors: Babaioff, Moshe ; Blumrosen, Liad ; Nisan, Noam

Abstract | Document (514 KB) | BibTeX

Saving Critical Nodes with Firefighters is FPT

Authors: Choudhari, Jayesh ; Dasgupta, Anirban ; Misra, Neeldhara ; Ramanujan, M. S.

Abstract | Document (554 KB) | BibTeX

On the Transformation Capability of Feasible Mechanisms for Programmable Matter

Authors: Michail, Othon ; Skretas, George ; Spirakis, Paul G.

Abstract | Document (516 KB) | BibTeX

Distributed Monitoring of Network Properties: The Power of Hybrid Networks

Authors: Gmyr, Robert ; Hinnenthal, Kristian ; Scheideler, Christian ; Sohler, Christian

Abstract | Document (493 KB) | BibTeX

Randomized Rumor Spreading Revisited

Authors: Doerr, Benjamin ; Kostrygin, Anatolii

Abstract | Document (506 KB) | BibTeX

Randomized Load Balancing on Networks with Stochastic Inputs

Authors: Cai, Leran ; Sauerwald, Thomas

Abstract | Document (573 KB) | BibTeX

Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion

Authors: Mai, Tung ; Panageas, Ioannis ; Vazirani, Vijay V.

Abstract | Document (663 KB) | BibTeX

Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols

Authors: Belleville, Amanda ; Doty, David ; Soloveichik, David

Abstract | Document (559 KB) | BibTeX

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

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)