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.
  • Adamaszek, Anna
  • Agarwal, Navneet
  • Agarwal, Pankaj K.
  • Aguirre, Alejandro
  • Akhoondian Amiri, Saeed
  • Akrida, Eleni C.
  • Almagor, Shaull
  • Amarilli, Antoine
  • Anand, Sanat
  • Ando, Megumi
  • Arar, Moab
  • Arnon-Friedman, Rotem
  • Aronov, Boris
  • Atserias, Albert
  • Bćk Tejs Knudsen, Mathias
  • Babay, Amy
  • Backens, Miriam
  • Bar-On, Achiya
  • Bar-On, Gali
  • Barequet, Gill
  • Barthe, Gilles
  • Bateni, MohammadHossein
  • Behnezhad, Soheil
  • Ben-Sasson, Eli
  • Ben Basat, Ran
  • Bentov, Iddo
  • Berger, Ben
  • Besa, Juan Jose
  • Bhangale, Amey
  • Bhaskara, Aditya
  • Bhattacharyya, Arnab
  • Biedl, Therese
  • Bilň, Davide
  • Bilň, Vittorio
  • Biniaz, Ahmad
  • Bläsius, Thomas
  • Blocki, Jeremiah
  • Blum, Avrim
  • Blumensath, Achim
  • Bogdanov, Andrej
  • Bose, Prosenjit
  • Bouchard, Sébastien
  • Boyle, Elette
  • Brakerski, Zvika
  • Braverman, Vladimir
  • Bringmann, Karl
  • Byrka, Jaroslaw
  • C. S., Karthik
  • Carmi, Paz
  • Carmosino, Marco L.
  • Celis, L. Elisa
  • Chakrabarty, Deeparnab
  • Chan, Timothy M.
  • Chandran, L. Sunil
  • Chaplick, Steven
  • Charikar, Moses
  • Chatzigiannakis, Ioannis
  • Chechik, Shiri
  • Chen, Jiehua
  • Chen, Jing
  • Cheng, Siu-Wing
  • Cheung, Yun Kuen
  • Chierichetti, Flavio
  • Chillara, Suryajith
  • Chistikov, Dmitry
  • Christodoulou, George
  • Chuzhoy, Julia
  • Clemente, Lorenzo
  • Cohen, Sarel
  • Colini-Baldeschi, Riccardo
  • Conway, Alex
  • Cummings, Robert
  • Czerwinski, Wojciech
  • Daruki, Samira
  • Das, Shantanu
  • Datta, Samir
  • Daviaud, Laure
  • De, Minati
  • Dehghani, Sina
  • Dell, Holger
  • Derakhshan, Mahsa
  • Dereniowski, Dariusz
  • Descotte, María Emilia
  • Devanny, William E.
  • Diakonikolas, Ilias
  • Dieudonné, Yoann
  • Dinitz, Michael
  • Dinur, Itai
  • Douéneau-Tabot, Gaëtan
  • Duan, Ran
  • Dudek, Bartlomiej
  • Dudycz, Szymon
  • Dujmovic, Vida
  • Dunkelman, Orr
  • Duraj, Lech
  • Dvorák, Zdenek
  • Ehsani, Soheil
  • Eiben, Eduard
  • Einziger, Gil
  • Eisenbrand, Friedrich
  • Eppstein, David
  • Farach-Colton, Martín
  • Fearnley, John
  • Feige, Uriel
  • Feldkord, Björn
  • Feldotto, Matthias
  • Fichtenberger, Hendrik
  • Figueira, Diego
  • Fomin, Fedor V.
  • Forbes, Michael A.
  • Fox, Jacob
  • Fränzle, Martin
  • Freer, Cameron E.
  • Freiberger, Cedric
  • Friedman, Roy
  • Friedrich, Tobias
  • Fu, Hao
  • Gärtner, Bernd
  • Gairing, Martin
  • Gajarský, Jakub
  • Gamlath, Buddhima
  • Ganardi, Moses
  • Gandikota, Venkata
  • Ganguly, Sumit
  • Garg, Shashwat
  • Gawrychowski, Pawel
  • Geri, Ofir
  • Ghosh, Sumanta
  • Ghoshal, Suprovat
  • Giannakopoulos, Yiannis
  • Golan, Shay
  • Golovach, Petr A.
  • Goodrich, Michael T.
  • Gouleakis, Themis
  • Graf, Daniel
  • Grandjean, Anael
  • Gregor, Petr
  • Grigorescu, Elena
  • Grohe, Martin
  • Grossman, Ofer
  • Gu, Yong
  • Guo, Heng
  • Gupta, Anupam
  • Gupta, Manoj
  • Gur, Tom
  • Gurjar, Rohit
  • Guruganesh, Guru
  • Gutowski, Grzegorz
  • Haddadan, Shahrzad
  • 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
  • Hermelin, Danny
  • Hjuler, Niklas
  • Hod, Rani
  • Hoefer, Martin
  • Hofman, Piotr
  • Holm, Jacob
  • Horesh, Yinon
  • Hoyrup, Mathieu
  • Hsu, Justin
  • Huang, Sangxia
  • Huang, Zhiyi
  • Hubácek, Pavel
  • Huber, Anja
  • Hucke, Danny
  • Hunkenschröder, Christoph
  • Impagliazzo, Russell
  • Indyk, Piotr
  • Issac, Davis
  • Jäger, Sven
  • Jain, Abhishek
  • Jeong, Jisu
  • Jerrum, Mark
  • Johnson, Timothy
  • Jurdzinski, Marcin
  • Kaklamanis, Christos
  • Kane, Daniel M.
  • Kanj, Iyad
  • Kaplan, Haim
  • Karczmarz, Adam
  • Katz, Matthew J.
  • Katzmann, Maximilian
  • Kawarabayashi, Ken-ichi
  • Keller, Nathan
  • Kesselheim, Thomas
  • Kiefer, Stefan
  • Kim, David H. K.
  • Kim, Eun Jung
  • Kim, Michael P.
  • Klein, Kim-Manuel
  • Klimann, Ines
  • Klimm, Max
  • Ko, Sang-Ki
  • Kodric, Bojana
  • Koh, Zhuan Khye
  • Kolla, Alexandra
  • Kopelowitz, Tsvi
  • Kortsarz, Guy
  • Koutecký, Martin
  • Koutis, Ioannis
  • Kowalski, Dariusz R.
  • Kozik, Jakub
  • Král, Karel
  • Kreutzer, Stephan
  • Kumar, Amit
  • Kumar, Ananya
  • Kupferman, Orna
  • Kuske, Dietrich
  • Kuszmaul, William
  • Labib, Karim
  • Lamani, Anissa
  • Lampis, Michael
  • Landau, Gad M.
  • Lang, Harry
  • Lasota, Slawomir
  • Lazic, Ranko
  • Lenzen, Christoph
  • Leroux, Jérôme
  • Levi, Reut
  • Levin, Asaf
  • Li, Bo
  • Li, Jason
  • Li, Jian
  • Li, Yingkai
  • Liaghat, Vahid
  • Limaye, Nutan
  • Liu, Sixue
  • Liu, Yang P.
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Louis, Anand
  • Lovett, Shachar
  • Lu, Pinyan
  • Lubiw, Anna
  • Lysyanskaya, Anna
  • Lyu, Kaifeng
  • Mütze, Torsten
  • Madan, Vivek
  • Mahabadi, Sepideh
  • Mallmann-Trenn, Frederik
  • Mamano, Nil
  • Manea, Florin
  • Manurangsi, Pasin
  • Mao, Yuchen
  • Markin, Liran
  • Marx, Dániel
  • Mazowiecki, Filip
  • Mehrabi, Saeed
  • Mehta, Ruta
  • Mertzios, George B.
  • Miccianco, Daniele
  • Mirrokni, Vahab
  • Mitra, Pradipta
  • Mnich, Matthias
  • Mohanty, Sidhanth
  • Molinaro, Marco
  • Montecchiani, Fabrizio
  • Montenegro-Retana, Felix
  • Moran, Shay
  • Morin, Pat
  • Mosaad, Hagar
  • Moscardelli, Luca
  • Mosteiro, Miguel A.
  • Mukherjee, Anish
  • Musco, Cameron
  • Musco, Christopher
  • Nagamochi, Hiroshi
  • Nakos, Vasileios
  • Nava Saucedo, Diego
  • Negahbani, Maryam
  • Nekrich, Yakov
  • Nesetril, Jaroslav
  • Neuen, Daniel
  • Nimavat, Rachit
  • Nirkhe, Chinmay
  • Niskanen, Reino
  • Nowotka, Dirk
  • Noy, Marc
  • Onak, Krzysztof
  • Onn, Shmuel
  • Ossona de Mendez, Patrice
  • Ostrovsky, Rafail
  • Ouaknine, Joël
  • Oum, Sang-il
  • Pérez, Guillermo A.
  • Paluch, Katarzyna
  • Panolan, Fahad
  • Paperman, Charles
  • Parter, Merav
  • Patel, Sarvar
  • Patt-Shamir, Boaz
  • Peebles, John
  • Persiano, Giuseppe
  • Pilipczuk, Michal
  • Place, Thomas
  • Porat, Ely
  • Potapov, Igor
  • Prabhakaran, Manoj
  • Price, Eric
  • Puppis, Gabriele
  • Rösner, Clemens
  • Rabani, Yuval
  • Rahul, Saladi
  • Ramanujan, M. S.
  • Raskhodnikova, Sofya
  • Raskin, Mikhail
  • Rattan, Gaurav
  • Ravsky, Alexander
  • Reidl, Felix
  • Ren, Hanlin
  • Riabzev, Michael
  • Riechers, Sören
  • Romashchenko, Andrei
  • Ronen, Eyal
  • Rotenberg, Eva
  • Rothblum, Ron D.
  • Roughgarden, Tim
  • Roy, Daniel M.
  • Sénizergues, Géraud
  • Saarela, Aleksi
  • Sabin, Manuel
  • Saig, Eden
  • Sanitŕ, Laura
  • Sankowski, Piotr
  • Sannella, Donald
  • Saurabh, Saket
  • Savani, Rahul
  • Sawada, Joe
  • Saxena, Nitin
  • Scarsini, Marco
  • Schieber, Baruch
  • Schmid, Andreas
  • Schmid, Stefan
  • Schmidt, Jens M.
  • Schmidt, Melanie
  • Schwarzmann, Alexander A.
  • Schweikardt, Nicole
  • Schweitzer, Pascal
  • Seddighin, Saeed
  • Seshadhri, C.
  • Shahrasbi, Amirbehshad
  • Shallit, Jeffrey
  • Shamir, Adi
  • Sharir, Micha
  • Sharma, Roohani
  • Shi, Xiaofei
  • Shilane, Philip
  • Shirmohammadi, Mahsa
  • Siebertz, Sebastian
  • Silva, Alexandra
  • Silveira, Luis Fernando Schultz Xavier da
  • Singh, Aditi
  • Sinop, Ali Kemal
  • Skowron, Piotr
  • Skrzypczak, Michal
  • Slívová, Veronika
  • Solomon, Shay
  • Soma, Tasuku
  • Sorge, Manuel
  • Sornat, Krzysztof
  • Sorrell, Jessica
  • Spirakis, Paul G.
  • Spoerhase, Joachim
  • Srinivasan, Srikanth
  • Staton, Sam
  • Stein, Cliff
  • Stein, Dario
  • Straszak, Damian
  • Stull, Don M.
  • Sudan, Madhu
  • Sung, Wing-Kin
  • Surek, Manuel
  • Svensson, Ola
  • Swaminathan, Mani
  • Swamy, Chaitanya
  • Tang, Zhihao Gavin
  • Thieffry, Marianne
  • Thierauf, Thomas
  • Thorup, Mikkel
  • Tonoyan, Tigran
  • Torunczyk, Szymon
  • Tsakalidis, Konstantinos
  • Upfal, Eli
  • Uznanski, Przemyslaw
  • Vanier, Pascal
  • Vardi, Gal
  • Vardi, Shai
  • Varma, Nithin
  • Vasudev, Yadu
  • Vazirani, Umesh
  • Venkat, Rakesh
  • Venkatasubramanian, Suresh
  • Vinci, Cosimo
  • Viola, Emanuele
  • Vishnoi, Nisheeth K.
  • Vitercik, Ellen
  • Vortmeier, Nils
  • Wötzel, Maximilian
  • Wahlström, Magnus
  • Wajc, David
  • Walzer, Stefan
  • Weiß, Armin
  • Wei, Fan
  • Weimann, Oren
  • Wein, Nicole
  • Wiebking, Daniel
  • Wiederrecht, Sebastian
  • Wille, Kaja
  • Williams, Richard Ryan
  • Winter, Sarah
  • Wolf, Felix
  • Woodruff, David P.
  • Worrell, James
  • Wu, Xiaowei
  • Xiao, Mingyu
  • Xie, Yuanhang
  • Xu, Pan
  • Yang, Hongseok
  • Yang, Lin F.
  • Yedidsion, Harel
  • Yeo, Kevin
  • Yoshida, Yuichi
  • Yousefi, Arman
  • Yu, Ching-Hua
  • Yuen, Henry
  • Zamaraev, Viktor
  • Zehavi, Meirav
  • Zeitoun, Marc
  • Zetzsche, Georg
  • Zeume, Thomas
  • Zhang, Hongyang
  • Zhang, Le
  • Zhang, Yuhao
  • Zhang, Zeyu
  • Zhou, Samson
  • Zimand, Marius

  •   
    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