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
  • Ásgeirsson, Eyjólfur I.
  • Abrahamsen, Mikkel
  • Achlioptas, Dimitris
  • Adamczyk, Marek
  • Agrawal, Shweta
  • Ahmadian, Sara
  • Albers, Susanne
  • Almagor, Shaull
  • Alman, Josh
  • Alstrup, Stephen
  • Alur, Rajeev
  • Amarilli, Antoine
  • Antoniadis, Antonios
  • Apon, Daniel
  • Asada, Kazuyuki
  • Atserias, Albert
  • Böhnlein, Toni
  • Babaioff, Moshe
  • Bacci, Giorgio
  • Bacci, Giovanni
  • Backens, Miriam
  • Bacquey, Nicolas
  • Baleshzar, Roksana
  • Balle, Borja
  • Barbero, Florian
  • Barthe, Gilles
  • Basset, Nicolas
  • Baswana, Surender
  • Belleville, Amanda
  • Ben-Eliezer, Omri
  • Ben-Sasson, Eli
  • Benedikt, Michael
  • Bernstein, Aaron
  • Berthon, Raphaël
  • Bezáková, Ivona
  • Bienkowski, Marcin
  • Bilň, Vittorio
  • Björklund, Andreas
  • Blelloch, Guy E.
  • Blumrosen, Liad
  • Boczkowski, Lucas
  • Bodwin, Greg
  • Bogdanov, Andrej
  • Boigelot, Bernard
  • Bojanczyk, Mikolaj
  • Bonnet, Édouard
  • Bourhis, Pierre
  • Bournez, Olivier
  • Bozzelli, Laura
  • Brandt, Sebastian
  • Bringmann, Karl
  • Bury, Marc
  • Byrka, Jaroslaw
  • Cadilhac, Michaël
  • Cai, Leran
  • Caragiannis, Ioannis
  • Carton, Olivier
  • Chakrabarty, Deeparnab
  • Chalopin, Jérémie
  • Chatzigiannakis, Ioannis
  • Chen, Jing
  • Chen, Shahar
  • Chepoi, Victor
  • Chiesa, Alessandro
  • Chistikov, Dmitry
  • Choudhari, Jayesh
  • Choudhary, Keerti
  • Clemente, Lorenzo
  • Cleve, Richard
  • Coester, Christian
  • Cohen, Ran
  • Coretti, Sandro
  • Curticapean, Radu
  • Cygan, Marek
  • Czerwinski, Wojciech
  • Döttling, Nico
  • Dartois, Luc
  • Dasgupta, Anirban
  • Datta, Samir
  • Daviaud, Laure
  • Dehghani, Sina
  • Dell, Holger
  • Dereniowski, Dariusz
  • Diakonikolas, Ilias
  • Di Castro, Dotan
  • Diekert, Volker
  • Disser, Yann
  • Doerr, Benjamin
  • Dohotaru, Catalin
  • Doty, David
  • Dowek, Gilles
  • Dueholm Hansen, Thomas
  • Eden, Talya
  • Ehsani, Soheil
  • Eickmeyer, Kord
  • Elder, Murray
  • Emek, Yuval
  • Espitau, Thomas
  • Even, Guy
  • Fanelli, Angelo
  • Figueira, Diego
  • Fijalkow, Nathanaël
  • Finkel, Alain
  • Flammini, Michele
  • Fomin, Fedor V.
  • Fournier, Paulin
  • Friggstad, Zachary
  • Göös, Mika
  • Gabizon, Ariel
  • Galanis, Andreas
  • Galicki, Alex
  • Garay, Juan
  • Garg, Sanjam
  • Gaspers, Serge
  • Geeraerts, Gilles
  • Georgiadis, Loukas
  • Ghazi, Badih
  • Giannakopoulos, Yiannis
  • Giannopoulou, Archontia C.
  • Gimbert, Hugo
  • Gmyr, Robert
  • Gold, Omer
  • Goldberg, Leslie Ann
  • Goldwasser, Shafi
  • Golovach, Petr A.
  • Gorain, Barun
  • Gourdeau, Pascale
  • Graf, Daniel
  • Grandjean, Etienne
  • Grandoni, Fabrizio
  • Gravin, Nick
  • Groß, Martin
  • Grossman, Ofer
  • Gu, Yan
  • Guillon, Bruno
  • Gupta, Manoj
  • Guruswami, Venkatesan
  • Gutin, Gregory
  • Hřyer, Peter
  • Haase, Christoph
  • Hajiaghayi, MohammadTaghi
  • Halldórsson, Magnús M.
  • Henzinger, Monika
  • Hinnenthal, Kristian
  • Hoefer, Martin
  • Hoeksma, Ruben
  • Holm, Stephen
  • Hsu, Justin
  • Iliopoulos, Fotis
  • Indyk, Piotr
  • Italiano, Giuseppe F.
  • Iwata, Yoichi
  • Jachiet, Louis
  • Jayaram, Rajesh
  • Jayram, T. S.
  • Jecker, Ismaël
  • Jez, Artur
  • Jung, Jean Christoph
  • Kärkkäinen, Juha
  • Künnemann, Marvin
  • Kane, Daniel M.
  • Karnin, Zohar
  • Kaski, Petteri
  • Kelmendi, Edon
  • Kerenidis, Iordanis
  • Khan, Shahbaz
  • Kindler, Guy
  • Klin, Bartek
  • Knudsen, Mathias Bćk Tejs
  • Kobayashi, Naoki
  • Kodric, Bojana
  • Kohler, Matthias
  • Korman, Amos
  • Korman, Simon
  • Kosowski, Adrian
  • Kostrygin, Anatolii
  • Koutis, Ioannis
  • Koutsoupias, Elias
  • Kraft, Dennis
  • Kratsch, Stefan
  • Krauthgamer, Robert
  • Kreutzer, Stephan
  • Krinninger, Sebastian
  • Kuhn, Fabian
  • Kwon, O-joung
  • Lambilliotte, Antonin
  • Larsen, Kim G.
  • Lasota, Slawomir
  • Lazic, Ranko
  • Lazos, Philip
  • Lee, Edward J.
  • Lee, Euiwoong
  • Leonardi, Stefano
  • Leroux, Jérôme
  • Levi, Reut
  • Lewin-Eytan, Liane
  • Lhote, Nathan
  • Li, Bo
  • Li, Yi
  • Li, Yingkai
  • Liaghat, Vahid
  • Lin, Chengyu
  • Lin, Jiabao
  • Linhares, André
  • Lokshtanov, Daniel
  • Lozes, Etienne
  • Lutz, Carsten
  • Magniez, Frédéric
  • Mai, Tung
  • Mainz, Isabelle
  • Mamouras, Konstantinos
  • Mancinska, Laura
  • Manurangsi, Pasin
  • Mardare, Radu
  • Marsault, Victor
  • Martel, Mauricio
  • Matuschke, Jannik
  • Mazowiecki, Filip
  • McCormick, S. Thomas
  • Medina, Moti
  • Meißner, Julie
  • Mengel, Stefan
  • Michail, Othon
  • Misra, Neeldhara
  • Mnich, Matthias
  • Molinari, Alberto
  • Monaco, Gianpiero
  • Monemizadeh, Morteza
  • Montanari, Angelo
  • Mouawad, Amer E.
  • Mucha, Marcin
  • Mukherjee, Anish
  • Mukherjee, Pratyay
  • Muscholl, Anca
  • Muthukrishnan, S.
  • Nagarajan, Viswanath
  • Nakos, Vasileios
  • Naor, Joseph (Seffi)
  • Nikishkin, Vladimir
  • Nisan, Noam
  • O'Donnell, Ryan
  • Ochremiak, Joanna
  • Olive, Frédéric
  • Oriolo, Gianpaolo
  • Ouaknine, Joël
  • Pallavoor, Ramesh Krishnan S.
  • Panageas, Ioannis
  • Panangaden, Prakash
  • Panolan, Fahad
  • Paperman, Charles
  • Parotsidis, Nikos
  • Parter, Merav
  • Paturi, Ramamohan
  • Paul, Christophe
  • Pelc, Andrzej
  • Penelle, Vincent
  • Peng, Pan
  • Peres, Yuval
  • Peron, Adriano
  • Piatkowski, Marcin
  • Pietrzak, Krzysztof
  • Pilipczuk, Michal
  • Pitassi, Toniann
  • Pouly, Amaury
  • Price, Eric
  • Pudlák, Pavel
  • Puglisi, Simon J.
  • Räcke, Harald
  • Rümmele, Stefan
  • Rabinovich, Roman
  • Raghavendra, Prasad
  • Ramanujan, M. S.
  • Randour, Mickael
  • Raskhodnikova, Sofya
  • Raskin, Jean-François
  • Raskin, Mikhail
  • Raymond, Jean-Florent
  • Reichman, Daniel
  • Reidl, Felix
  • Reiter, Fabian
  • Riabzev, Michael
  • Rigo, Michel
  • Roberson, David E.
  • Rodeh, Yoav
  • Roditty, Liam
  • Ron, Dana
  • Rosén, Adi
  • Rossman, Benjamin
  • Rubinfeld, Ronitt
  • Rubinstein, Aviad
  • Saffidine, Abdallah
  • Saha, Barna
  • Sala, Pietro
  • Samal, Robert
  • Sankur, Ocan
  • Sato, Tetsuya
  • Sauerwald, Thomas
  • Saurabh, Saket
  • Schaudt, Oliver
  • Scheder, Dominik
  • Scheideler, Christian
  • Schlipf, Lena
  • Schmidt, Jens M.
  • Schneider, Stefan
  • Schneider, Thomas
  • Schwartz, Roy
  • Schweitzer, Pascal
  • Schwentick, Thomas
  • Schwiegelshohn, Chris
  • Seddighin, Saeed
  • Seshadhri, C.
  • Severini, Simone
  • Sharir, Micha
  • Shen, Xiangkun
  • Siebertz, Sebastian
  • Singh, Ishaan Preet
  • Sivan, Balasubramanian
  • Skorski, Maciej
  • Skretas, George
  • Sohler, Christian
  • Soloveichik, David
  • Song, Zhao
  • Spirakis, Paul G.
  • Spooner, Nicholas
  • Srinivasan, Srikanth
  • Stöckel, Morten
  • Stanford, Caleb
  • Stefankovic, Daniel
  • Strub, Pierre-Yves
  • Sudan, Madhu
  • Sun, Yihan
  • Sutre, Grégoire
  • Swamy, Chaitanya
  • Talebanfard, Navid
  • Thilikos, Dimitrios M.
  • Thorup, Mikkel
  • Tonoyan, Tigran
  • Trabelsi, Ohad
  • Uitto, Jara
  • Uznanski, Przemyslaw
  • Vanden Boom, Michael
  • Varvitsiotis, Antonios
  • Vassilevska Williams, Virginia
  • Vazirani, Vijay V.
  • Verschae, José
  • Vlassis, Nikos
  • Vortmeier, Nils
  • Wahlström, Magnus
  • Wang, Chunhao
  • Wang, Hanpin
  • Watson, Thomas
  • Wattenhofer, Roger
  • Wegrzycki, Karol
  • Weitz, Benjamin
  • Wiese, Andreas
  • Williamson, Christopher
  • Wlodarczyk, Michal
  • Wolter, Frank
  • Woodruff, David P.
  • Worrell, James
  • Wrochna, Marcin
  • Xing, Chaoping
  • Yang, Kuan
  • Yuan, Chen
  • Zehavi, Meirav
  • Zeume, Thomas
  • Zhang, Shengyu
  • Zikas, Vassilis
  • Zou, Mengchuan

  •   
    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, Stephen ; 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 Published by LZI