ICALP 2019 July 9-12, 2019, Patras, Greece

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)



Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi (Eds.)
ISBN 978-3-95977-109-2, LIPICS Vol. 132 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 74 MB)
Search Publication Server


Authors
  • Aaronson, Scott
  • Abboud, Amir
  • Abrahamsen, Mikkel
  • Abu Radi, Bader
  • Afshani, Peyman
  • Agrawal, Akanksha
  • Akrida, Eleni C.
  • Alon, Noga
  • Anagnostopoulos, Aris
  • Ancona, Bertie
  • Andoni, Alexandr
  • Appavoo, Anuja Meetoo
  • Arunachalam, Srinivasan
  • Assadi, Sepehr
  • Awasthi, Pranjal
  • Axiotis, Kyriakos
  • Baazizi, Mohamed-Amine
  • Baier, Christel
  • Bakshi, Ainesh
  • Balaji, Nikhil
  • Balcan, Maria-Florina
  • Barceló, Pablo
  • Bartal, Yair
  • Basin, David
  • Bell, Paul C.
  • Bernardini, Giulia
  • Bezáková, Ivona
  • Biedl, Therese
  • Björklund, Andreas
  • Bojanczyk, Mikolaj
  • Bonne, Matthias
  • Brandão, Fernando G. S. L.
  • Briceño, Raimundo
  • Brunet, Paul
  • Bulatov, Andrei A.
  • Bun, Mark
  • Cantu, Angel A.
  • Caragiannis, Ioannis
  • Carette, Titouan
  • Casel, Katrin
  • Casteigts, Arnaud
  • Censor-Hillel, Keren
  • Chakraborty, Shantanav
  • Chakraborty, Sourav
  • Chalopin, Jérémie
  • Chattopadhyay, Arkadev
  • Chatzigiannakis, Ioannis
  • Chechik, Shiri
  • Cheng, Kuan
  • Cheng, Siu-Wing
  • Chen, Xue
  • Chepoi, Victor
  • Cheraghchi, Mahdi
  • Chlamtác, Eden
  • Ciobanu, Laura
  • Cohen-Addad, Vincent
  • Cohen, Ilan R.
  • Cohen, Sarel
  • Coja-Oghlan, Amin
  • Cojocaru, Alexandru
  • Colazzo, Dario
  • Colcombet, Thomas
  • Cormode, Graham
  • Czyzowicz, Jurek
  • Dalirrooyfard, Mina
  • Dal Lago, Ugo
  • Dalmau, Víctor
  • Dark, Jacques
  • Dawar, Anuj
  • Day, Joel D.
  • Deligkas, Argyrios
  • Dell, Holger
  • de Wolf, Ronald
  • Díaz, Josep
  • Dinitz, Michael
  • Dobrev, Stefan
  • Dörfler, Julian
  • Dorfman, Dani
  • Duan, Ran
  • Ducoffe, Guillaume
  • Eden, Talya
  • Elder, Murray
  • Emek, Yuval
  • Ene, Alina
  • Equi, Massimo
  • Erlebach, Thomas
  • Etessami, Kousha
  • Fandina, Nova
  • Fanelli, Angelo
  • Fearnley, John
  • Feldman, Michal
  • Ficak, Miron
  • Figueira, Diego
  • Filmus, Yuval
  • Fleischmann, Pamela
  • Flocchini, Paola
  • Fomin, Fedor V.
  • Fortin, Marie
  • Freksen, Casper Benjamin
  • Friedrich, Tobias
  • Galanis, Andreas
  • Garg, Ankit
  • Garg, Naveen
  • Gavazzo, Francesco
  • Gavinsky, Dmitry
  • Gawrychowski, Pawel
  • Gebhard, Oliver
  • Georgiadis, Loukas
  • Georgiou, Konstantinos
  • Ghaffari, Mohsen
  • Ghelli, Giorgio
  • Gheorghiu, Alexandru
  • Giannopoulos, Panos
  • Gilbert, Seth
  • Gilyén, András
  • Goldberg, Leslie Ann
  • Goldberg, Paul W.
  • Golovach, Petr A.
  • Golovnev, Alexander
  • Gordon, Spencer
  • Grädel, Erich
  • Grilo, Alex B.
  • Grohe, Martin
  • Grossi, Roberto
  • Gupta, Anupam
  • Gupta, Nikhil
  • Gupta, Siddharth
  • Guruganesh, Guru
  • Guruswami, Venkatesan
  • Haeupler, Bernhard
  • Hahn-Klimroth, Max
  • Hambardzumyan, Lianna
  • Hamoudi, Yassine
  • Haney, Samuel
  • Hatami, Hamed
  • Hatami, Pooya
  • Hegerfeld, Falko
  • Henzinger, Monika
  • Hollender, Alexandros
  • Hong, Chih-Duo
  • Hosseini, Mehran
  • Hrubes, Pavel
  • Huang, Zhiyi
  • Ikenmeyer, Christian
  • Ilango, Rahul
  • Impagliazzo, Russell
  • Im, Sungjin
  • Italiano, Giuseppe F.
  • Jansen, Klaus
  • Jeandel, Emmanuel
  • Jeffery, Stacey
  • Jin, Ce
  • Jin, Lingfei
  • Jin, Zhengzhong
  • Kabanets, Valentine
  • Kalev, Amir
  • Kamma, Lior
  • Kammer, Frank
  • Kaplan, Haim
  • Kashefi, Elham
  • Kaski, Petteri
  • Kayal, Neeraj
  • Kiefer, Sandra
  • Kiefer, Stefan
  • Killick, Ryan
  • Kindermann, Philipp
  • Kirousis, Lefteris
  • Kociumaka, Tomasz
  • Kokonezi, Sofia
  • Kolmogorov, Vladimir
  • Kolokolova, Antonina
  • Konrad, Christian
  • Korman, Amos
  • Koroth, Sajin
  • Kosowski, Adrian
  • Kowalski, Dariusz R.
  • Kozik, Marcin
  • Kranakis, Evangelos
  • Kratsch, Stefan
  • Krauthgamer, Robert
  • Krizanc, Danny
  • Kuhn, Fabian
  • Kumar, Amit
  • Kumar, Mrinal
  • Kupferman, Orna
  • Kurpisz, Adam
  • Kuszmaul, William
  • Kutten, Shay
  • Lacki, Jakub
  • Lafond, Manuel
  • Larose, Benoît
  • Larsen, Kasper Green
  • Lassota, Alexandra
  • Lavi, Ron
  • Lee, Euiwoong
  • Lee, Troy
  • Leonardi, Stefano
  • Le, Xuan-Bach
  • Lhote, Nathan
  • Liaee, Mehraneh
  • Li, Jason
  • Lin, Anthony W.
  • Lin, Bingkai
  • Lin, Cedric Yen-Yu
  • Li, Tongyang
  • Livieratos, John
  • Li, Xin
  • Löding, Christof
  • Löffler, Maarten
  • Loick, Philipp
  • Lokshtanov, Daniel
  • Luchsinger, Austin
  • Luo, Kelin
  • Lu, Zhenjian
  • Maggs, Bruce M.
  • Magniez, Frédéric
  • Mäkinen, Veli
  • Malkin, Tal
  • Mallmann-Trenn, Frederik
  • Mande, Nikhil S.
  • Manea, Florin
  • Mao, Yuchen
  • Martinov, Emanuel
  • Martinsson, Anders
  • Matuschke, Jannik
  • Maus, Yannic
  • Mayr, Richard
  • Mehta, Ruta
  • Meir, Or
  • Melissourgos, Themistoklis
  • Merino, Arturo I.
  • Mertz, Ian
  • Mertzios, George B.
  • Milius, Stefan
  • Mizrachi, Eyal
  • Molina Lovett, Antonio
  • Moran, Shay
  • Moseley, Benjamin
  • Moses Jr., William K.
  • Mosteiro, Miguel A.
  • Muscholl, Anca
  • Mustafa, Nabil H.
  • Myrisiotis, Dimitrios
  • Naor, Joseph (Seffi)
  • Narayanan, Lata
  • Natarajan Ramamoorthy, Sivaramakrishnan
  • Neiman, Ofer
  • Nguyen, Huy L.
  • Nguyen, Lê Thành Dung
  • Nikoletseas, Sotiris
  • Niskanen, Reino
  • Nosatzki, Negev Shekel
  • Novotný, Petr
  • Oh, Shunhao
  • Oliveira, Igor Carboni
  • Oliveira, Rafael
  • Olsák, Miroslav
  • Opatrny, Jaroslav
  • Ouaknine, Joël
  • Pajak, Dominik
  • Pakusa, Wied
  • Panagiotou, Konstantinos
  • Panigrahi, Debmalya
  • Pankratov, Denis
  • Panolan, Fahad
  • Panova, Greta
  • Paraashar, Manaswi
  • Parotsidis, Nikos
  • Parter, Merav
  • Pasch, Matija
  • Peng, Binghui
  • Perdrix, Simon
  • Pérez, Guillermo A.
  • Peters, Joseph G.
  • Petrova, Kalina
  • Pfister, Pascal
  • Picantin, Matthieu
  • Pin, Jean-Éric
  • Pirogov, Anton
  • Pisanti, Nadia
  • Pissis, Solon P.
  • Pitassi, Toniann
  • Place, Thomas
  • Pradic, Pierre
  • Price, Eric
  • Pruhs, Kirk
  • Puppis, Gabriele
  • Purohit, Manish
  • Rabie, Mikaël
  • Rafiey, Akbar
  • Rafiey, Arash
  • Rajaraman, Rajmohan
  • Rao, Anup
  • Raptopoulos, Christoforos
  • Raszyk, Martin
  • Reutenauer, Christophe
  • Reynier, Pierre-Alain
  • Riazanov, Andrii
  • Robinson, Thomas
  • Rodeh, Yoav
  • Roditty, Liam
  • Rohwedder, Lars
  • Romero, Miguel
  • Ron, Dana
  • Rosenbaum, Will
  • Rosone, Giovanna
  • Rote, Günter
  • Rothenberger, Ralf
  • Roth, Marc
  • Saha, Chandan
  • Sajenko, Andrej
  • Santha, Miklos
  • Santos, Thiago
  • Sanyal, Swagato
  • Saptharishi, Ramprasad
  • Sartiani, Carlo
  • Sauerwald, Thomas
  • Saurabh, Saket
  • Savani, Rahul
  • Sayyadi, Ali
  • Scheideler, Christian
  • Schmand, Daniel
  • Schmid, Markus L.
  • Schmidt-Kraepelin, Ulrike
  • Schmitz, Sylvain
  • Schoeters, Jason
  • Schröder, Marc
  • Schwartz, Roy
  • Schweller, Robert
  • Semukhin, Pavel
  • Setzer, Alexander
  • Shallit, Jeffrey
  • Shende, Sunil
  • Shirmohammadi, Mahsa
  • Silva, Alexandra
  • Singla, Sahil
  • Skopalik, Alexander
  • Solomon, Shay
  • Soto, José A.
  • Spirakis, Paul G.
  • Spoerhase, Joachim
  • Spooner, Jakob T.
  • Stankiewicz, Szymon
  • Stefankovic, Daniel
  • Stein, Clifford
  • Stewart, Alistair
  • Sundaram, Ravi
  • Sun, Xiaoming
  • Svensson, Ola
  • Svore, Krysta M.
  • Tal, Avishay
  • Tale, Prafullkumar
  • Thaler, Justin
  • Thorup, Mikkel
  • Tomescu, Alexandru I.
  • Totzke, Patrick
  • Trabelsi, Ohad
  • Traytel, Dmitriy
  • Tzamos, Christos
  • Umboh, Seeun William
  • Uniyal, Sumedha
  • Urbat, Henning
  • Uznanski, Przemyslaw
  • Vaandrager, Frits
  • van Apeldoorn, Joran
  • Verschae, José
  • Viennot, Laurent
  • Villevalois, Didier
  • Vilmart, Renaud
  • Vyas, Nikhil
  • Wajc, David
  • Warmuth, Manfred K.
  • Watson, Thomas
  • Wein, Nicole
  • Wei, Yuanhao
  • Wellnitz, Philip
  • White, Colin
  • Williamson, David P.
  • Williams, Ryan
  • Williams, Virginia Vassilevska
  • Wolleb-Graf, Daniel
  • Woodruff, David P.
  • Worrell, James
  • Wu, Hongxun
  • Wu, Ke
  • Wu, Xiaodi
  • Wylie, Tim
  • Xing, Chaoping
  • Xu, Yinzhan
  • Yang, Guang
  • Yannakakis, Mihalis
  • Yehudayoff, Amir
  • Yogev, Eylon
  • Yoshimizu, Akira
  • Yuan, Chen
  • Yu, Yuancheng
  • Zamaraev, Viktor
  • Zamir, Or
  • Zanetti, Luca
  • Zehavi, Meirav
  • Zeitoun, Marc
  • Zhang, Jialin
  • Zhong, Peilin
  • Zhu, Xue
  • Zuckerman, David
  • Zwick, Uri

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Baier, Christel ; Chatzigiannakis, Ioannis ; Flocchini, Paola ; Leonardi, Stefano

    Abstract | Document (434 KB) | BibTeX

    Auction Design under Interdependent Values (Invited Talk)
    Authors: Feldman, Michal

    Abstract | Document (199 KB) | BibTeX

    Symmetry and Similarity (Invited Talk)
    Authors: Grohe, Martin

    Abstract | Document (181 KB) | BibTeX

    Approximately Good and Modern Matchings (Invited Talk)
    Authors: Svensson, Ola

    Abstract | Document (177 KB) | BibTeX

    Automata Learning and Galois Connections (Invited Talk)
    Authors: Vaandrager, Frits

    Abstract | Document (182 KB) | BibTeX

    Fixed Point Computation Problems and Facets of Complexity (Invited Talk)
    Authors: Yannakakis, Mihalis

    Abstract | Document (173 KB) | BibTeX

    Complexity-Theoretic Limitations on Blind Delegated Quantum Computation
    Authors: Aaronson, Scott ; Cojocaru, Alexandru ; Gheorghiu, Alexandru ; Kashefi, Elham

    Abstract | Document (577 KB) | BibTeX

    Faster Algorithms for All-Pairs Bounded Min-Cuts
    Authors: Abboud, Amir ; Georgiadis, Loukas ; Italiano, Giuseppe F. ; Krauthgamer, Robert ; Parotsidis, Nikos ; Trabelsi, Ohad ; Uznanski, Przemyslaw ; Wolleb-Graf, Daniel

    Abstract | Document (629 KB) | BibTeX

    Fine-Grained Reductions and Quantum Speedups for Dynamic Programming
    Authors: Abboud, Amir

    Abstract | Document (467 KB) | BibTeX

    Geometric Multicut
    Authors: Abrahamsen, Mikkel ; Giannopoulos, Panos ; Löffler, Maarten ; Rote, Günter

    Abstract | Document (633 KB) | BibTeX

    Lower Bounds for Multiplication via Network Coding
    Authors: Afshani, Peyman ; Freksen, Casper Benjamin ; Kamma, Lior ; Larsen, Kasper Green

    Abstract | Document (511 KB) | BibTeX

    Path Contraction Faster Than 2^n
    Authors: Agrawal, Akanksha ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Tale, Prafullkumar

    Abstract | Document (5,696 KB) | BibTeX

    Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
    Authors: Alon, Noga ; Chechik, Shiri ; Cohen, Sarel

    Abstract | Document (554 KB) | BibTeX

    Algorithms and Hardness for Diameter in Dynamic Graphs
    Authors: Ancona, Bertie ; Henzinger, Monika ; Roditty, Liam ; Williams, Virginia Vassilevska ; Wein, Nicole

    Abstract | Document (515 KB) | BibTeX

    Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity
    Authors: Andoni, Alexandr ; Stein, Clifford ; Zhong, Peilin

    Abstract | Document (540 KB) | BibTeX

    Two Party Distribution Testing: Communication and Security
    Authors: Andoni, Alexandr ; Malkin, Tal ; Nosatzki, Negev Shekel

    Abstract | Document (581 KB) | BibTeX

    Two New Results About Quantum Exact Learning
    Authors: Arunachalam, Srinivasan ; Chakraborty, Sourav ; Lee, Troy ; Paraashar, Manaswi ; de Wolf, Ronald

    Abstract | Document (531 KB) | BibTeX

    When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
    Authors: Assadi, Sepehr ; Solomon, Shay

    Abstract | Document (566 KB) | BibTeX

    Robust Communication-Optimal Distributed Clustering Algorithms
    Authors: Awasthi, Pranjal ; Bakshi, Ainesh ; Balcan, Maria-Florina ; White, Colin ; Woodruff, David P.

    Abstract | Document (542 KB) | BibTeX

    Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
    Authors: Axiotis, Kyriakos ; Tzamos, Christos

    Abstract | Document (531 KB) | BibTeX

    Covering Metric Spaces by Few Trees
    Authors: Bartal, Yair ; Fandina, Nova ; Neiman, Ofer

    Abstract | Document (540 KB) | BibTeX

    Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
    Authors: Bernardini, Giulia ; Gawrychowski, Pawel ; Pisanti, Nadia ; Pissis, Solon P. ; Rosone, Giovanna

    Abstract | Document (626 KB) | BibTeX

    The Complexity of Approximating the Matching Polynomial in the Complex Plane
    Authors: Bezáková, Ivona ; Galanis, Andreas ; Goldberg, Leslie Ann ; Stefankovic, Daniel

    Abstract | Document (520 KB) | BibTeX

    Finding Tutte Paths in Linear Time
    Authors: Biedl, Therese ; Kindermann, Philipp

    Abstract | Document (895 KB) | BibTeX

    Approximate Counting of k-Paths: Deterministic and in Polynomial Space
    Authors: Björklund, Andreas ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (652 KB) | BibTeX

    Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors
    Authors: Björklund, Andreas ; Williams, Ryan

    Abstract | Document (512 KB) | BibTeX

    Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction
    Authors: Björklund, Andreas ; Kaski, Petteri ; Williams, Ryan

    Abstract | Document (442 KB) | BibTeX

    Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning
    Authors: Brandão, Fernando G. S. L. ; Kalev, Amir ; Li, Tongyang ; Lin, Cedric Yen-Yu ; Svore, Krysta M. ; Wu, Xiaodi

    Abstract | Document (504 KB) | BibTeX

    A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round
    Authors: Grilo, Alex B.

    Abstract | Document (529 KB) | BibTeX

    Dismantlability, Connectedness, and Mixing in Relational Structures
    Authors: Briceño, Raimundo ; Bulatov, Andrei A. ; Dalmau, Víctor ; Larose, Benoît

    Abstract | Document (518 KB) | BibTeX

    Sign-Rank Can Increase Under Intersection
    Authors: Bun, Mark ; Mande, Nikhil S. ; Thaler, Justin

    Abstract | Document (540 KB) | BibTeX

    Covert Computation in Self-Assembled Circuits
    Authors: Cantu, Angel A. ; Luchsinger, Austin ; Schweller, Robert ; Wylie, Tim

    Abstract | Document (1,656 KB) | BibTeX

    Randomness and Intractability in Kolmogorov Complexity
    Authors: Oliveira, Igor Carboni

    Abstract | Document (525 KB) | BibTeX

    The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation
    Authors: Chakraborty, Shantanav ; Gilyén, András ; Jeffery, Stacey

    Abstract | Document (481 KB) | BibTeX

    Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes
    Authors: Chalopin, Jérémie ; Chepoi, Victor ; Moran, Shay ; Warmuth, Manfred K.

    Abstract | Document (663 KB) | BibTeX

    Query-To-Communication Lifting for BPP Using Inner Product
    Authors: Chattopadhyay, Arkadev ; Filmus, Yuval ; Koroth, Sajin ; Meir, Or ; Pitassi, Toniann

    Abstract | Document (450 KB) | BibTeX

    Estimating the Frequency of a Clustered Signal
    Authors: Chen, Xue ; Price, Eric

    Abstract | Document (568 KB) | BibTeX

    Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes
    Authors: Cheng, Kuan ; Jin, Zhengzhong ; Li, Xin ; Wu, Ke

    Abstract | Document (485 KB) | BibTeX

    Restricted Max-Min Allocation: Approximation and Integrality Gap
    Authors: Cheng, Siu-Wing ; Mao, Yuchen

    Abstract | Document (537 KB) | BibTeX

    Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
    Authors: Cheraghchi, Mahdi ; Kabanets, Valentine ; Lu, Zhenjian ; Myrisiotis, Dimitrios

    Abstract | Document (643 KB) | BibTeX

    The Norms of Graph Spanners
    Authors: Chlamtác, Eden ; Dinitz, Michael ; Robinson, Thomas

    Abstract | Document (498 KB) | BibTeX

    On the Fixed-Parameter Tractability of Capacitated Clustering
    Authors: Cohen-Addad, Vincent ; Li, Jason

    Abstract | Document (513 KB) | BibTeX

    Tight FPT Approximations for k-Median and k-Means
    Authors: Cohen-Addad, Vincent ; Gupta, Anupam ; Kumar, Amit ; Lee, Euiwoong ; Li, Jason

    Abstract | Document (555 KB) | BibTeX

    Information-Theoretic and Algorithmic Thresholds for Group Testing
    Authors: Coja-Oghlan, Amin ; Gebhard, Oliver ; Hahn-Klimroth, Max ; Loick, Philipp

    Abstract | Document (512 KB) | BibTeX

    On Reachability Problems for Low-Dimensional Matrix Semigroups
    Authors: Colcombet, Thomas ; Ouaknine, Joël ; Semukhin, Pavel ; Worrell, James

    Abstract | Document (520 KB) | BibTeX

    Independent Sets in Vertex-Arrival Streams
    Authors: Cormode, Graham ; Dark, Jacques ; Konrad, Christian

    Abstract | Document (549 KB) | BibTeX

    Approximation Algorithms for Min-Distance Problems
    Authors: Dalirrooyfard, Mina ; Williams, Virginia Vassilevska ; Vyas, Nikhil ; Wein, Nicole ; Xu, Yinzhan ; Yu, Yuancheng

    Abstract | Document (519 KB) | BibTeX

    Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
    Authors: Dalirrooyfard, Mina ; Williams, Virginia Vassilevska ; Vyas, Nikhil ; Wein, Nicole

    Abstract | Document (492 KB) | BibTeX

    Faster Algorithms for All Pairs Non-Decreasing Paths Problem
    Authors: Duan, Ran ; Jin, Ce ; Wu, Hongxun

    Abstract | Document (514 KB) | BibTeX

    Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
    Authors: Ducoffe, Guillaume

    Abstract | Document (544 KB) | BibTeX

    Algorithmically Efficient Syntactic Characterization of Possibility Domains
    Authors: Díaz, Josep ; Kirousis, Lefteris ; Kokonezi, Sofia ; Livieratos, John

    Abstract | Document (451 KB) | BibTeX

    On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions
    Authors: Dörfler, Julian ; Ikenmeyer, Christian ; Panova, Greta

    Abstract | Document (524 KB) | BibTeX

    The Arboricity Captures the Complexity of Sampling Edges
    Authors: Eden, Talya ; Ron, Dana ; Rosenbaum, Will

    Abstract | Document (561 KB) | BibTeX

    A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
    Authors: Ene, Alina ; Nguyen, Huy L.

    Abstract | Document (535 KB) | BibTeX

    Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint
    Authors: Ene, Alina ; Nguyen, Huy L.

    Abstract | Document (528 KB) | BibTeX

    On the Complexity of String Matching for Graphs
    Authors: Equi, Massimo ; Grossi, Roberto ; Mäkinen, Veli ; Tomescu, Alexandru I.

    Abstract | Document (704 KB) | BibTeX

    Unique End of Potential Line
    Authors: Fearnley, John ; Gordon, Spencer ; Mehta, Ruta ; Savani, Rahul

    Abstract | Document (489 KB) | BibTeX

    Dichotomy for Symmetric Boolean PCSPs
    Authors: Ficak, Miron ; Kozik, Marcin ; Olsák, Miroslav ; Stankiewicz, Szymon

    Abstract | Document (442 KB) | BibTeX

    Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions
    Authors: Filmus, Yuval ; Hambardzumyan, Lianna ; Hatami, Hamed ; Hatami, Pooya ; Zuckerman, David

    Abstract | Document (479 KB) | BibTeX

    Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (496 KB) | BibTeX

    Decomposition of Map Graphs with Applications
    Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (636 KB) | BibTeX

    The Satisfiability Threshold for Non-Uniform Random 2-SAT
    Authors: Friedrich, Tobias ; Rothenberger, Ralf

    Abstract | Document (508 KB) | BibTeX

    Determinant Equivalence Test over Finite Fields and over Q
    Authors: Garg, Ankit ; Gupta, Nikhil ; Kayal, Neeraj ; Saha, Chandan

    Abstract | Document (582 KB) | BibTeX

    Non-Clairvoyant Precedence Constrained Scheduling
    Authors: Garg, Naveen ; Gupta, Anupam ; Kumar, Amit ; Singla, Sahil

    Abstract | Document (465 KB) | BibTeX

    A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity
    Authors: Gavinsky, Dmitry ; Lee, Troy ; Santha, Miklos ; Sanyal, Swagato

    Abstract | Document (602 KB) | BibTeX

    The Hairy Ball Problem is PPAD-Complete
    Authors: Goldberg, Paul W. ; Hollender, Alexandros

    Abstract | Document (464 KB) | BibTeX

    AC^0[p] Lower Bounds Against MCSP via the Coin Problem
    Authors: Golovnev, Alexander ; Ilango, Rahul ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina ; Tal, Avishay

    Abstract | Document (533 KB) | BibTeX

    Stochastic Online Metric Matching
    Authors: Gupta, Anupam ; Guruganesh, Guru ; Peng, Binghui ; Wajc, David

    Abstract | Document (527 KB) | BibTeX

    Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields
    Authors: Guruswami, Venkatesan ; Jin, Lingfei ; Xing, Chaoping

    Abstract | Document (469 KB) | BibTeX

    Quantum Chebyshev's Inequality and Applications
    Authors: Hamoudi, Yassine ; Magniez, Frédéric

    Abstract | Document (630 KB) | BibTeX

    Retracting Graphs to Cycles
    Authors: Haney, Samuel ; Liaee, Mehraneh ; Maggs, Bruce M. ; Panigrahi, Debmalya ; Rajaraman, Rajmohan ; Sundaram, Ravi

    Abstract | Document (560 KB) | BibTeX

    On Adaptive Algorithms for Maximum Matching
    Authors: Hegerfeld, Falko ; Kratsch, Stefan

    Abstract | Document (608 KB) | BibTeX

    Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
    Authors: Hrubes, Pavel ; Natarajan Ramamoorthy, Sivaramakrishnan ; Rao, Anup ; Yehudayoff, Amir

    Abstract | Document (513 KB) | BibTeX

    Scalable and Jointly Differentially Private Packing
    Authors: Huang, Zhiyi ; Zhu, Xue

    Abstract | Document (492 KB) | BibTeX

    Local Search Breaks 1.75 for Graph Balancing
    Authors: Jansen, Klaus ; Rohwedder, Lars

    Abstract | Document (562 KB) | BibTeX

    Near-Linear Time Algorithm for n-fold ILPs via Color Coding
    Authors: Jansen, Klaus ; Lassota, Alexandra ; Rohwedder, Lars

    Abstract | Document (501 KB) | BibTeX

    An Improved FPTAS for 0-1 Knapsack
    Authors: Jin, Ce

    Abstract | Document (456 KB) | BibTeX

    Testing the Complexity of a Valued CSP Language
    Authors: Kolmogorov, Vladimir

    Abstract | Document (562 KB) | BibTeX

    Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
    Authors: Kumar, Mrinal ; Oliveira, Rafael ; Saptharishi, Ramprasad

    Abstract | Document (529 KB) | BibTeX

    Sum-Of-Squares Bounds via Boolean Function Analysis
    Authors: Kurpisz, Adam

    Abstract | Document (497 KB) | BibTeX

    Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
    Authors: Kuszmaul, William

    Abstract | Document (487 KB) | BibTeX

    A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
    Authors: Lin, Bingkai

    Abstract | Document (553 KB) | BibTeX

    Maintaining Perfect Matchings at Low Cost
    Authors: Matuschke, Jannik ; Schmidt-Kraepelin, Ulrike ; Verschae, José

    Abstract | Document (493 KB) | BibTeX

    The Minimum Cost Query Problem on Matroids with Uncertainty Areas
    Authors: Merino, Arturo I. ; Soto, José A.

    Abstract | Document (511 KB) | BibTeX

    Short Proofs Are Hard to Find
    Authors: Mertz, Ian ; Pitassi, Toniann ; Wei, Yuanhao

    Abstract | Document (551 KB) | BibTeX

    A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
    Authors: Mizrachi, Eyal ; Schwartz, Roy ; Spoerhase, Joachim ; Uniyal, Sumedha

    Abstract | Document (594 KB) | BibTeX

    Scheduling to Approximate Minimization Objectives on Identical Machines
    Authors: Moseley, Benjamin

    Abstract | Document (521 KB) | BibTeX

    Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set
    Authors: Mustafa, Nabil H.

    Abstract | Document (492 KB) | BibTeX

    Tight Bounds for Online Weighted Tree Augmentation
    Authors: Naor, Joseph (Seffi) ; Umboh, Seeun William ; Williamson, David P.

    Abstract | Document (678 KB) | BibTeX

    Optimal Short Cycle Decomposition in Almost Linear Time
    Authors: Parter, Merav ; Yogev, Eylon

    Abstract | Document (579 KB) | BibTeX

    Satisfiability Thresholds for Regular Occupation Problems
    Authors: Panagiotou, Konstantinos ; Pasch, Matija

    Abstract | Document (488 KB) | BibTeX

    Toward a Dichotomy for Approximation of H-Coloring
    Authors: Rafiey, Akbar ; Rafiey, Arash ; Santos, Thiago

    Abstract | Document (615 KB) | BibTeX

    Beating Fredman-Komlós for Perfect k-Hashing
    Authors: Guruswami, Venkatesan ; Riazanov, Andrii

    Abstract | Document (484 KB) | BibTeX

    Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities
    Authors: Sauerwald, Thomas ; Zanetti, Luca

    Abstract | Document (506 KB) | BibTeX

    Querying a Matrix Through Matrix-Vector Products
    Authors: Sun, Xiaoming ; Woodruff, David P. ; Yang, Guang ; Zhang, Jialin

    Abstract | Document (608 KB) | BibTeX

    Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps
    Authors: Thorup, Mikkel ; Zamir, Or ; Zwick, Uri

    Abstract | Document (454 KB) | BibTeX

    Amplification with One NP Oracle Query
    Authors: Watson, Thomas

    Abstract | Document (536 KB) | BibTeX

    Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams
    Authors: Woodruff, David P. ; Yang, Guang

    Abstract | Document (539 KB) | BibTeX

    Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph
    Authors: Xing, Chaoping ; Yuan, Chen

    Abstract | Document (522 KB) | BibTeX

    Improvements in Quantum SDP-Solving with Applications
    Authors: van Apeldoorn, Joran ; Gilyén, András

    Abstract | Document (523 KB) | BibTeX

    Minimizing GFG Transition-Based Automata
    Authors: Abu Radi, Bader ; Kupferman, Orna

    Abstract | Document (525 KB) | BibTeX

    A Type System for Interactive JSON Schema Inference (Extended Abstract)
    Authors: Baazizi, Mohamed-Amine ; Colazzo, Dario ; Ghelli, Giorgio ; Sartiani, Carlo

    Abstract | Document (578 KB) | BibTeX

    On the Complexity of Value Iteration
    Authors: Balaji, Nikhil ; Kiefer, Stefan ; Novotný, Petr ; Pérez, Guillermo A. ; Shirmohammadi, Mahsa

    Abstract | Document (537 KB) | BibTeX

    Monadic Decomposability of Regular Relations
    Authors: Barceló, Pablo ; Hong, Chih-Duo ; Le, Xuan-Bach ; Lin, Anthony W. ; Niskanen, Reino

    Abstract | Document (533 KB) | BibTeX

    Boundedness of Conjunctive Regular Path Queries
    Authors: Barceló, Pablo ; Figueira, Diego ; Romero, Miguel

    Abstract | Document (586 KB) | BibTeX

    Polynomially Ambiguous Probabilistic Automata on Restricted Languages
    Authors: Bell, Paul C.

    Abstract | Document (465 KB) | BibTeX

    String-to-String Interpretations With Polynomial-Size Output
    Authors: Bojanczyk, Mikolaj ; Kiefer, Sandra ; Lhote, Nathan

    Abstract | Document (3,432 KB) | BibTeX

    A Kleene Theorem for Nominal Automata
    Authors: Brunet, Paul ; Silva, Alexandra

    Abstract | Document (589 KB) | BibTeX

    Completeness of Graphical Languages for Mixed States Quantum Mechanics
    Authors: Carette, Titouan ; Jeandel, Emmanuel ; Perdrix, Simon ; Vilmart, Renaud

    Abstract | Document (554 KB) | BibTeX

    Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
    Authors: Casel, Katrin ; Day, Joel D. ; Fleischmann, Pamela ; Kociumaka, Tomasz ; Manea, Florin ; Schmid, Markus L.

    Abstract | Document (617 KB) | BibTeX

    Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE
    Authors: Ciobanu, Laura ; Elder, Murray

    Abstract | Document (607 KB) | BibTeX

    Differential Logical Relations, Part I: The Simply-Typed Case
    Authors: Dal Lago, Ugo ; Gavazzo, Francesco ; Yoshimizu, Akira

    Abstract | Document (566 KB) | BibTeX

    Approximations of Isomorphism and Logics with Linear-Algebraic Operators
    Authors: Dawar, Anuj ; Grädel, Erich ; Pakusa, Wied

    Abstract | Document (535 KB) | BibTeX

    Counting Answers to Existential Questions
    Authors: Dell, Holger ; Roth, Marc ; Wellnitz, Philip

    Abstract | Document (503 KB) | BibTeX

    A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games
    Authors: Dorfman, Dani ; Kaplan, Haim ; Zwick, Uri

    Abstract | Document (626 KB) | BibTeX

    Reachability for Branching Concurrent Stochastic Games
    Authors: Etessami, Kousha ; Martinov, Emanuel ; Stewart, Alistair ; Yannakakis, Mihalis

    Abstract | Document (501 KB) | BibTeX

    FO = FO^3 for Linear Orders with Monotone Binary Relations
    Authors: Fortin, Marie

    Abstract | Document (522 KB) | BibTeX

    A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
    Authors: Grohe, Martin ; Kiefer, Sandra

    Abstract | Document (660 KB) | BibTeX

    Termination of Linear Loops over the Integers
    Authors: Hosseini, Mehran ; Ouaknine, Joël ; Worrell, James

    Abstract | Document (506 KB) | BibTeX

    Büchi Objectives in Countable MDPs
    Authors: Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa ; Totzke, Patrick

    Abstract | Document (549 KB) | BibTeX

    Determinization of Büchi Automata: Unifying the Approaches of Safra and Muller-Schupp
    Authors: Löding, Christof ; Pirogov, Anton

    Abstract | Document (565 KB) | BibTeX

    Optimal Regular Expressions for Permutations
    Authors: Molina Lovett, Antonio ; Shallit, Jeffrey

    Abstract | Document (436 KB) | BibTeX

    Equivalence of Finite-Valued Streaming String Transducers Is Decidable
    Authors: Muscholl, Anca ; Puppis, Gabriele

    Abstract | Document (575 KB) | BibTeX

    From Normal Functors to Logarithmic Space Queries
    Authors: Nguyen, Lê Thành Dung ; Pradic, Pierre

    Abstract | Document (587 KB) | BibTeX

    Automatic Semigroups vs Automaton Semigroups
    Authors: Picantin, Matthieu

    Abstract | Document (637 KB) | BibTeX

    A Mahler's Theorem for Word Functions
    Authors: Pin, Jean-Éric ; Reutenauer, Christophe

    Abstract | Document (528 KB) | BibTeX

    On All Things Star-Free
    Authors: Place, Thomas ; Zeitoun, Marc

    Abstract | Document (491 KB) | BibTeX

    From Nondeterministic to Multi-Head Deterministic Finite-State Transducers
    Authors: Raszyk, Martin ; Basin, David ; Traytel, Dmitriy

    Abstract | Document (546 KB) | BibTeX

    Sequentiality of String-to-Context Transducers
    Authors: Reynier, Pierre-Alain ; Villevalois, Didier

    Abstract | Document (648 KB) | BibTeX

    The Parametric Complexity of Lossy Counter Machines
    Authors: Schmitz, Sylvain

    Abstract | Document (605 KB) | BibTeX

    Varieties of Data Languages
    Authors: Urbat, Henning ; Milius, Stefan

    Abstract | Document (510 KB) | BibTeX

    How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs?
    Authors: Akrida, Eleni C. ; Mertzios, George B. ; Nikoletseas, Sotiris ; Raptopoulos, Christoforos ; Spirakis, Paul G. ; Zamaraev, Viktor

    Abstract | Document (523 KB) | BibTeX

    Distributed Detection of Cliques in Dynamic Networks
    Authors: Bonne, Matthias ; Censor-Hillel, Keren

    Abstract | Document (523 KB) | BibTeX

    On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies
    Authors: Caragiannis, Ioannis ; Fanelli, Angelo

    Abstract | Document (447 KB) | BibTeX

    Temporal Cliques Admit Sparse Spanners
    Authors: Casteigts, Arnaud ; Peters, Joseph G. ; Schoeters, Jason

    Abstract | Document (479 KB) | BibTeX

    Distributed Reconfiguration of Maximal Independent Sets
    Authors: Censor-Hillel, Keren ; Rabie, Mikaël

    Abstract | Document (498 KB) | BibTeX

    Stochastic Graph Exploration
    Authors: Anagnostopoulos, Aris ; Cohen, Ilan R. ; Leonardi, Stefano ; Lacki, Jakub

    Abstract | Document (535 KB) | BibTeX

    Energy Consumption of Group Search on a Line
    Authors: Czyzowicz, Jurek ; Georgiou, Konstantinos ; Killick, Ryan ; Kranakis, Evangelos ; Krizanc, Danny ; Lafond, Manuel ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil

    Abstract | Document (591 KB) | BibTeX

    Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
    Authors: Deligkas, Argyrios ; Fearnley, John ; Melissourgos, Themistoklis ; Spirakis, Paul G.

    Abstract | Document (670 KB) | BibTeX

    Exploration of High-Dimensional Grids by Finite Automata
    Authors: Dobrev, Stefan ; Narayanan, Lata ; Opatrny, Jaroslav ; Pankratov, Denis

    Abstract | Document (528 KB) | BibTeX

    Deterministic Leader Election in Programmable Matter
    Authors: Emek, Yuval ; Kutten, Shay ; Lavi, Ron ; Moses Jr., William K.

    Abstract | Document (482 KB) | BibTeX

    Two Moves per Time Step Make a Difference
    Authors: Erlebach, Thomas ; Kammer, Frank ; Luo, Kelin ; Sajenko, Andrej ; Spooner, Jakob T.

    Abstract | Document (547 KB) | BibTeX

    Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication
    Authors: Ghaffari, Mohsen ; Sayyadi, Ali

    Abstract | Document (499 KB) | BibTeX

    Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond
    Authors: Gupta, Siddharth ; Kosowski, Adrian ; Viennot, Laurent

    Abstract | Document (541 KB) | BibTeX

    Optimal Strategies for Patrolling Fences
    Authors: Haeupler, Bernhard ; Kuhn, Fabian ; Martinsson, Anders ; Petrova, Kalina ; Pfister, Pascal

    Abstract | Document (548 KB) | BibTeX

    Matroid Coflow Scheduling
    Authors: Im, Sungjin ; Moseley, Benjamin ; Pruhs, Kirk ; Purohit, Manish

    Abstract | Document (521 KB) | BibTeX

    Multi-Round Cooperative Search Games with Multiple Players
    Authors: Korman, Amos ; Rodeh, Yoav

    Abstract | Document (508 KB) | BibTeX

    Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader
    Authors: Kowalski, Dariusz R. ; Mosteiro, Miguel A.

    Abstract | Document (511 KB) | BibTeX

    Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol
    Authors: Mallmann-Trenn, Frederik ; Maus, Yannic ; Pajak, Dominik

    Abstract | Document (572 KB) | BibTeX

    Periodic Bandits and Wireless Network Selection
    Authors: Oh, Shunhao ; Appavoo, Anuja Meetoo ; Gilbert, Seth

    Abstract | Document (2,157 KB) | BibTeX

    On the Complexity of Local Graph Transformations
    Authors: Scheideler, Christian ; Setzer, Alexander

    Abstract | Document (525 KB) | BibTeX

    Network Investment Games with Wardrop Followers
    Authors: Schmand, Daniel ; Schröder, Marc ; Skopalik, Alexander

    Abstract | Document (437 KB) | BibTeX

      




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