ICALP 2020 July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)



Artur Czumaj and Anuj Dawar and Emanuela Merelli (Eds.)
ISBN 978-3-95977-138-2, LIPICS Vol. 168 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 76 MB)
Search Publication Server


Authors
  • Abboud, Amir
  • Abo Khamis, Mahmoud
  • Alaluf, Naor
  • Albers, Susanne
  • Alistarh, Dan
  • Almagor, Shaull
  • Bahrani, Maryam
  • Baier, Christel
  • Barak, Boaz
  • Barozzini, David
  • Barto, Libor
  • Bassilakis, Andrew
  • Baumann, Pascal
  • Benedikt, Michael
  • Bera, Suman K.
  • Bernstein, Aaron
  • Bienkowski, Marcin
  • Bille, Philip
  • Bodwin, Greg
  • Bojańczyk, Mikołaj
  • Bostan, Alin
  • Bougeret, Marin
  • Brandts, Alex
  • Brankovic, Milutin
  • Bringmann, Karl
  • Buchin, Kevin
  • Bulatov, Andrei A.
  • Bumpus, Georgina
  • Bénéteau, Laurine
  • Cadilhac, Michaël
  • Cai, Jin-Yi
  • Carayol, Arnaud
  • Carette, Titouan
  • Cen, Ruoxu
  • Chakrabarti, Amit
  • Chakraborty, Diptarka
  • Chalopin, Jérémie
  • Chan, Timothy F. N.
  • Charalampopoulos, Panagiotis
  • Chatterjee, Rohit
  • Chechik, Shiri
  • Chen, Yu
  • Chepoi, Victor
  • Chistikov, Dmitry
  • Chiu, Man-Kwun
  • Choudhary, Aruni
  • Choudhary, Keerti
  • Christodoulou, George
  • Chuzhoy, Julia
  • Ciobanu, Laura
  • Clemente, Lorenzo
  • Cohen, Ilan
  • Colcombet, Thomas
  • Cooper, Jacob W.
  • Crubillé, Raphaëlle
  • Czumaj, Artur
  • Dadsetan, Amineh
  • Dal Lago, Ugo
  • Dalirrooyfard, Mina
  • Datta, Samir
  • Daviaud, Laure
  • Dawar, Anuj
  • Day, Joel D.
  • de Keijzer, Bart
  • De, Anindya
  • Deligkas, Argyrios
  • Dennunzio, Alberto
  • Doron, Dean
  • Dreier, Jan
  • Drucker, Andrew
  • Duan, Ran
  • Dughmi, Shaddin
  • Dyer, Martin
  • Eiben, Eduard
  • Ellert, Jonas
  • Ene, Alina
  • Epstein, Rogers
  • Fan, Chenglin
  • Fearnley, John
  • Feige, Uriel
  • Feldman, Moran
  • Feller, Shon
  • Fichtenberger, Hendrik
  • Fielbaum, Andrés
  • Figelius, Michael
  • Filiot, Emmanuel
  • Filtser, Arnold
  • Filtser, Omrit
  • Fischer, Johannes
  • Fischer, Nick
  • Fomin, Fedor V.
  • Formenti, Enrico
  • Fotakis, Dimitris
  • Fraigniaud, Pierre
  • Fu, Zhiguo
  • Fürer, Martin
  • Gaboardi, Marco
  • Gairing, Martin
  • Galanis, Andreas
  • Ganardi, Moses
  • Ganesh, Arun
  • Ganesh, Chaya
  • Ganian, Robert
  • Gao, Mingze
  • Garg, Paritosh
  • Gawrychowski, Paweł
  • Gazda, Maciej
  • Gentilini, Raffaella
  • Ghosh, Prantar
  • Giannakopoulos, Yiannis
  • Gilbert, Anna
  • Gillibert, Pierre
  • Goldberg, Leslie Ann
  • Govorov, Artem
  • Gregor, Petr
  • Grinberg, Darij
  • Grinberg, Vadim
  • Grujic, Nikola
  • Gu, Albert
  • Gu, Yong
  • Guo, Heng
  • Gurjar, Rohit
  • Guruswami, Venkatesan
  • Göke, Alexander
  • Göös, Mika
  • Gørtz, Inge Li
  • Haase, Christoph
  • Hakoniemi, Tuomas
  • Hamm, Thekla
  • Har-Peled, Sariel
  • He, Haoqing
  • Hermelin, Danny
  • Hirai, Hiroshi
  • Hoppen, Carlos
  • Hoyrup, Mathieu
  • Hu, Lunjia
  • Ikeda, Motoki
  • Im, Sungjin
  • Immorlica, Nicole
  • Izumi, Taisuke
  • Janke, Maximilian
  • Jansen, Bart M. P.
  • Jeandel, Emmanuel
  • Jiang, Zhihao
  • Jones, Mitchell
  • Jonušas, Julius
  • Jurdziński, Marcin
  • Kale, Sagar
  • Kandiros, Vardis
  • Kannan, Sampath
  • Katz, Matthew J.
  • Kavitha, Telikepalli
  • Kavouras, Loukas
  • Kelmendi, Edon
  • Kesselheim, Thomas
  • Khanna, Sanjeev
  • Kiefer, Sandra
  • Kiefer, Stefan
  • Klute, Fabian
  • Koechlin, Florent
  • Kolaitis, Phokion G.
  • Kompatscher, Michael
  • Kopelowitz, Tsvi
  • Korman, Matias
  • Kostylev, Egor V.
  • Koumoutsos, Grigorios
  • Koutecký, Martin
  • Kozik, Marcin
  • Krauthgamer, Robert
  • Král', Daniel
  • Kumar, Pankaj
  • Kurpicz, Florian
  • Kyropoulou, Maria
  • Laarhoven, Thijs
  • Lasota, Sławomir
  • Li, Huan
  • Li, Yi
  • Lianeas, Thanasis
  • Liang, Xiao
  • Lincoln, Andrea
  • Liu, Mingmou
  • Liu, Tianyu
  • Logan, Alan D.
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Long, Huan
  • Lotze, Henri
  • Löffler, Maarten
  • Ma, Weiyun
  • Magen, Ofer
  • Maggs, Bruce M.
  • Magniez, Frédéric
  • Magri, Bernardo
  • Mahmoody, Mohammad
  • Majumdar, Rupak
  • Manea, Florin
  • Maneth, Sebastian
  • Margara, Luciano
  • Marx, Dániel
  • Mayr, Richard
  • Mazowiecki, Filip
  • McKay, Brendan D.
  • Merelli, Emanuela
  • Merino, Arturo
  • Micha, Evi
  • Mihajlin, Ivan
  • Misra, Pranabendu
  • Mička, Ondřej
  • Mnich, Matthias
  • Mohan, Divyarthi
  • Molinaro, Marco
  • Morales, Ignacio
  • Mottet, Antoine
  • Mousavi, Hamoon
  • Mousavi, Mohammad Reza
  • Mouzakis, Nikos
  • Mozes, Shay
  • Mukherjee, Anish
  • Mulzer, Wolfgang
  • Munro, J. Ian
  • Murtagh, Jack
  • Mömke, Tobias
  • Mütze, Torsten
  • Nadiradze, Giorgi
  • Nakos, Vasileios
  • Nayak, Ashwin
  • Nechushtan, Moran
  • Neuen, Daniel
  • Nezhadi, Seyed Sajjad
  • Ngo, Hung Q.
  • Nguyen, Huy L.
  • Nguyễn, Lê Thành Dũng
  • Nicaud, Cyril
  • Nikpey, Hesam
  • Nissim, Kobbi
  • Niwiński, Damian
  • Nöllenburg, Martin
  • Oki, Taihei
  • Otachi, Yota
  • Ouaknine, Joël
  • Pacut, Maciej
  • Pandey, Omkant
  • Panigrahi, Debmalya
  • Panolan, Fahad
  • Paperman, Charles
  • Papp, Pál András
  • Parter, Merav
  • Parys, Paweł
  • Patsilinakos, Panagiotis
  • Paul, Erik
  • Paz, Ami
  • Pekárková, Kristýna
  • Peng, Pan
  • Philip, Geevarghese
  • Piecuch, Krzysztof
  • Pilipczuk, Michał
  • Pinsker, Michael
  • Piribauer, Jakob
  • Pitassi, Toniann
  • Piórkowski, Radosław
  • Pokorski, Karol
  • Popov, Aleksandr
  • Potukuchi, Aditya
  • Poças, Diogo
  • Pradic, Pierre
  • Przybyłko, Marcin
  • Purser, David
  • Rahul, Saladi
  • Raichel, Benjamin
  • Raskin, Jean-François
  • Rathi, Rajat
  • Remscrim, Zachary
  • Roeloffzen, Marcel
  • Rohwedder, Lars
  • Rossmanith, Peter
  • Rotenberg, Eva
  • Rudra, Atri
  • Ré, Christopher
  • Saarela, Aleksi
  • Sabour, Amirmojtaba
  • Salamati, Mahmoud
  • Sandeep, Sai
  • Sandlund, Bryce
  • Sau, Ignasi
  • Saurabh, Saket
  • Savani, Rahul
  • Seidl, Helmut
  • Seybold, Martin P.
  • Shabtay, Dvir
  • Shah, Nisarg
  • Shahar, Noa
  • Shao, Shuai
  • Shimizu, Nobutaka
  • Shiraga, Takeharu
  • Shirley, Morgan
  • Shirmohammadi, Mahsa
  • Silwal, Sandeep
  • Skoulakis, Stratis
  • Skrzypczak, Michał
  • Smith, Caleb
  • Soudjani, Sadegh
  • Staals, Frank
  • Stamoulis, Giannos
  • Stefański, Rafał
  • Stoienescu, Paul-Ioan
  • Su, Hsin-Hao
  • Suciu, Dan
  • Suh, Andrew
  • Sun, Kevin
  • Sun, Xiaoming
  • Sun, Yuan
  • Sun, Yuxin
  • Svensson, Ola
  • Sénizergues, Géraud
  • Tan, Johnson
  • Tan, Li-Yang
  • Tan, Tony
  • Tan, Zihan
  • Tanner, Jonathan
  • Tawari, Anuj
  • Thejaswini, K. S.
  • Thilikos, Dimitrios M.
  • Thinniyam, Ramanathan S.
  • Totzke, Patrick
  • Trevisan, Vilmar
  • Vadhan, Salil
  • Valeriote, Matt
  • van Renssen, André
  • Vardas, Manolis
  • Vassilevska Williams, Virginia
  • Vaxès, Yann
  • Ventre, Carmine
  • Venturi, Daniele
  • Verschae, José
  • Vortmeier, Nils
  • Wahlström, Magnus
  • Waldmann, Clara
  • Wang, Jiaheng
  • Watson, Thomas
  • Wattenhofer, Roger
  • Weimann, Oren
  • Wein, Nicole
  • Weinberg, S. Matthew
  • Weiß, Armin
  • Wellnitz, Philip
  • Wiebking, Daniel
  • Wiese, Andreas
  • Wilsenach, Gregory
  • Wojtczak, Dominik
  • Wootters, Mary
  • Worrell, James
  • Wrochna, Marcin
  • Wu, David J.
  • Wu, Hongxun
  • Wu, Kewen
  • Włodarczyk, Michał
  • Xia, Zhiyu
  • Xu, Xian
  • Xu, Yinzhan
  • Yang, Kuan
  • Yao, Andrew Chi chih
  • Yedidia, Adam
  • Yin, Qiang
  • Yin, Yitong
  • Yu, Huacheng
  • Yuen, Henry
  • Zehavi, Meirav
  • Zetzsche, Georg
  • Zeume, Thomas
  • Zhang, Tianyi
  • Zhang, Wenbo
  • Zheng, Yufan
  • Zuckerman, David
  • Živný, Stanislav

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Czumaj, Artur ; Dawar, Anuj ; Merelli, Emanuela

    Abstract | Document (484 KB) | BibTeX

    An Incentive Analysis of Some Bitcoin Fee Designs (Invited Talk)
    Authors: Yao, Andrew Chi chih

    Abstract | Document (448 KB) | BibTeX

    Sketching Graphs and Combinatorial Optimization (Invited Talk)
    Authors: Krauthgamer, Robert

    Abstract | Document (169 KB) | BibTeX

    How to Play in Infinite MDPs (Invited Talk)
    Authors: Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa ; Totzke, Patrick ; Wojtczak, Dominik

    Abstract | Document (560 KB) | BibTeX

    Scheduling Lower Bounds via AND Subset Sum
    Authors: Abboud, Amir ; Bringmann, Karl ; Hermelin, Danny ; Shabtay, Dvir

    Abstract | Document (537 KB) | BibTeX

    On the Fine-Grained Complexity of Parity Problems
    Authors: Abboud, Amir ; Feller, Shon ; Weimann, Oren

    Abstract | Document (810 KB) | BibTeX

    Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints
    Authors: Alaluf, Naor ; Ene, Alina ; Feldman, Moran ; Nguyen, Huy L. ; Suh, Andrew

    Abstract | Document (633 KB) | BibTeX

    Dynamic Averaging Load Balancing on Cycles
    Authors: Alistarh, Dan ; Nadiradze, Giorgi ; Sabour, Amirmojtaba

    Abstract | Document (765 KB) | BibTeX

    Asynchronous Majority Dynamics in Preferential Attachment Trees
    Authors: Bahrani, Maryam ; Immorlica, Nicole ; Mohan, Divyarthi ; Weinberg, S. Matthew

    Abstract | Document (552 KB) | BibTeX

    The Power of Many Samples in Query Complexity
    Authors: Bassilakis, Andrew ; Drucker, Andrew ; Göös, Mika ; Hu, Lunjia ; Ma, Weiyun ; Tan, Li-Yang

    Abstract | Document (599 KB) | BibTeX

    Medians in Median Graphs and Their Cube Complexes in Linear Time
    Authors: Bénéteau, Laurine ; Chalopin, Jérémie ; Chepoi, Victor ; Vaxès, Yann

    Abstract | Document (711 KB) | BibTeX

    Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
    Authors: Bera, Suman K. ; Chakrabarti, Amit ; Ghosh, Prantar

    Abstract | Document (666 KB) | BibTeX

    Improved Bounds for Matching in Random-Order Streams
    Authors: Bernstein, Aaron

    Abstract | Document (591 KB) | BibTeX

    An Optimal Algorithm for Online Multiple Knapsack
    Authors: Bienkowski, Marcin ; Pacut, Maciej ; Piecuch, Krzysztof

    Abstract | Document (731 KB) | BibTeX

    Space Efficient Construction of Lyndon Arrays in Linear Time
    Authors: Bille, Philip ; Ellert, Jonas ; Fischer, Johannes ; Gørtz, Inge Li ; Kurpicz, Florian ; Munro, J. Ian ; Rotenberg, Eva

    Abstract | Document (631 KB) | BibTeX

    New Fault Tolerant Subset Preservers
    Authors: Bodwin, Greg ; Choudhary, Keerti ; Parter, Merav ; Shahar, Noa

    Abstract | Document (621 KB) | BibTeX

    Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
    Authors: Bougeret, Marin ; Jansen, Bart M. P. ; Sau, Ignasi

    Abstract | Document (1,261 KB) | BibTeX

    The Complexity of Promise SAT on Non-Boolean Domains
    Authors: Brandts, Alex ; Wrochna, Marcin ; Živný, Stanislav

    Abstract | Document (542 KB) | BibTeX

    A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions
    Authors: Brankovic, Milutin ; Grujic, Nikola ; van Renssen, André ; Seybold, Martin P.

    Abstract | Document (905 KB) | BibTeX

    Faster Minimization of Tardy Processing Time on a Single Machine
    Authors: Bringmann, Karl ; Fischer, Nick ; Hermelin, Danny ; Shabtay, Dvir ; Wellnitz, Philip

    Abstract | Document (496 KB) | BibTeX

    Fréchet Distance for Uncertain Curves
    Authors: Buchin, Kevin ; Fan, Chenglin ; Löffler, Maarten ; Popov, Aleksandr ; Raichel, Benjamin ; Roeloffzen, Marcel

    Abstract | Document (750 KB) | BibTeX

    Counting Homomorphisms in Plain Exponential Time
    Authors: Bulatov, Andrei A. ; Dadsetan, Amineh

    Abstract | Document (568 KB) | BibTeX

    From Holant to Quantum Entanglement and Back
    Authors: Cai, Jin-Yi ; Fu, Zhiguo ; Shao, Shuai

    Abstract | Document (621 KB) | BibTeX

    Counting Perfect Matchings and the Eight-Vertex Model
    Authors: Cai, Jin-Yi ; Liu, Tianyu

    Abstract | Document (1,150 KB) | BibTeX

    Roundtrip Spanners with (2k-1) Stretch
    Authors: Cen, Ruoxu ; Duan, Ran ; Gu, Yong

    Abstract | Document (488 KB) | BibTeX

    New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures
    Authors: Chakraborty, Diptarka ; Choudhary, Keerti

    Abstract | Document (650 KB) | BibTeX

    Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming
    Authors: Chan, Timothy F. N. ; Cooper, Jacob W. ; Koutecký, Martin ; Král', Daniel ; Pekárková, Kristýna

    Abstract | Document (540 KB) | BibTeX

    Dynamic Longest Common Substring in Polylogarithmic Time
    Authors: Charalampopoulos, Panagiotis ; Gawrychowski, Paweł ; Pokorski, Karol

    Abstract | Document (678 KB) | BibTeX

    Improved Black-Box Constructions of Composable Secure Computation
    Authors: Chatterjee, Rohit ; Liang, Xiao ; Pandey, Omkant

    Abstract | Document (619 KB) | BibTeX

    Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs
    Authors: Chechik, Shiri ; Nechushtan, Moran

    Abstract | Document (881 KB) | BibTeX

    Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
    Authors: Chen, Yu ; Kannan, Sampath ; Khanna, Sanjeev

    Abstract | Document (536 KB) | BibTeX

    Computational Complexity of the α-Ham-Sandwich Problem
    Authors: Chiu, Man-Kwun ; Choudhary, Aruni ; Mulzer, Wolfgang

    Abstract | Document (731 KB) | BibTeX

    Existence and Complexity of Approximate Equilibria in Weighted Congestion Games
    Authors: Christodoulou, George ; Gairing, Martin ; Giannakopoulos, Yiannis ; Poças, Diogo ; Waldmann, Clara

    Abstract | Document (587 KB) | BibTeX

    On Packing Low-Diameter Spanning Trees
    Authors: Chuzhoy, Julia ; Parter, Merav ; Tan, Zihan

    Abstract | Document (634 KB) | BibTeX

    Online Two-Dimensional Load Balancing
    Authors: Cohen, Ilan ; Im, Sungjin ; Panigrahi, Debmalya

    Abstract | Document (602 KB) | BibTeX

    Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph
    Authors: Dalirrooyfard, Mina ; Vassilevska Williams, Virginia

    Abstract | Document (774 KB) | BibTeX

    Symmetric Arithmetic Circuits
    Authors: Dawar, Anuj ; Wilsenach, Gregory

    Abstract | Document (589 KB) | BibTeX

    An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs
    Authors: De, Anindya ; Khanna, Sanjeev ; Li, Huan ; Nikpey, Hesam

    Abstract | Document (637 KB) | BibTeX

    Tree Polymatrix Games Are PPAD-Hard
    Authors: Deligkas, Argyrios ; Fearnley, John ; Savani, Rahul

    Abstract | Document (621 KB) | BibTeX

    Spectral Sparsification via Bounded-Independence Sampling
    Authors: Doron, Dean ; Murtagh, Jack ; Vadhan, Salil ; Zuckerman, David

    Abstract | Document (580 KB) | BibTeX

    Hard Problems on Random Graphs
    Authors: Dreier, Jan ; Lotze, Henri ; Rossmanith, Peter

    Abstract | Document (577 KB) | BibTeX

    A Scaling Algorithm for Weighted f-Factors in General Graphs
    Authors: Duan, Ran ; He, Haoqing ; Zhang, Tianyi

    Abstract | Document (643 KB) | BibTeX

    The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem
    Authors: Dughmi, Shaddin

    Abstract | Document (529 KB) | BibTeX

    Extending Partial 1-Planar Drawings
    Authors: Eiben, Eduard ; Ganian, Robert ; Hamm, Thekla ; Klute, Fabian ; Nöllenburg, Martin

    Abstract | Document (850 KB) | BibTeX

    How to Hide a Clique?
    Authors: Feige, Uriel ; Grinberg, Vadim

    Abstract | Document (457 KB) | BibTeX

    Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time
    Authors: Fichtenberger, Hendrik ; Gao, Mingze ; Peng, Pan

    Abstract | Document (551 KB) | BibTeX

    A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems
    Authors: Fielbaum, Andrés ; Morales, Ignacio ; Verschae, José

    Abstract | Document (490 KB) | BibTeX

    Scattering and Sparse Partitions, and Their Applications
    Authors: Filtser, Arnold

    Abstract | Document (735 KB) | BibTeX

    Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic
    Authors: Filtser, Arnold ; Filtser, Omrit ; Katz, Matthew J.

    Abstract | Document (586 KB) | BibTeX

    Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
    Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Mihajlin, Ivan ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (3,332 KB) | BibTeX

    Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games
    Authors: Fotakis, Dimitris ; Kandiros, Vardis ; Lianeas, Thanasis ; Mouzakis, Nikos ; Patsilinakos, Panagiotis ; Skoulakis, Stratis

    Abstract | Document (865 KB) | BibTeX

    The Online Min-Sum Set Cover Problem
    Authors: Fotakis, Dimitris ; Kavouras, Loukas ; Koumoutsos, Grigorios ; Skoulakis, Stratis ; Vardas, Manolis

    Abstract | Document (479 KB) | BibTeX

    Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth
    Authors: Fürer, Martin ; Hoppen, Carlos ; Trevisan, Vilmar

    Abstract | Document (536 KB) | BibTeX

    Counting Solutions to Random CNF Formulas
    Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Guo, Heng ; Yang, Kuan

    Abstract | Document (533 KB) | BibTeX

    Robust Algorithms for TSP and Steiner Tree
    Authors: Ganesh, Arun ; Maggs, Bruce M. ; Panigrahi, Debmalya

    Abstract | Document (580 KB) | BibTeX

    Cryptographic Reverse Firewalls for Interactive Proof Systems
    Authors: Ganesh, Chaya ; Magri, Bernardo ; Venturi, Daniele

    Abstract | Document (532 KB) | BibTeX

    Robust Algorithms Under Adversarial Injections
    Authors: Garg, Paritosh ; Kale, Sagar ; Rohwedder, Lars ; Svensson, Ola

    Abstract | Document (575 KB) | BibTeX

    Minimum Cut in O(m log² n) Time
    Authors: Gawrychowski, Paweł ; Mozes, Shay ; Weimann, Oren

    Abstract | Document (601 KB) | BibTeX

    Sparse Recovery for Orthogonal Polynomial Transforms
    Authors: Gilbert, Anna ; Gu, Albert ; Ré, Christopher ; Rudra, Atri ; Wootters, Mary

    Abstract | Document (593 KB) | BibTeX

    Hitting Long Directed Cycles Is Fixed-Parameter Tractable
    Authors: Göke, Alexander ; Marx, Dániel ; Mnich, Matthias

    Abstract | Document (638 KB) | BibTeX

    On the Central Levels Problem
    Authors: Gregor, Petr ; Mička, Ondřej ; Mütze, Torsten

    Abstract | Document (854 KB) | BibTeX

    Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization
    Authors: Gurjar, Rohit ; Rathi, Rajat

    Abstract | Document (520 KB) | BibTeX

    d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors
    Authors: Guruswami, Venkatesan ; Sandeep, Sai

    Abstract | Document (475 KB) | BibTeX

    Feasible Interpolation for Polynomial Calculus and Sums-Of-Squares
    Authors: Hakoniemi, Tuomas

    Abstract | Document (442 KB) | BibTeX

    Active Learning a Convex Body in Low Dimensions
    Authors: Har-Peled, Sariel ; Jones, Mitchell ; Rahul, Saladi

    Abstract | Document (732 KB) | BibTeX

    Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity
    Authors: Hirai, Hiroshi ; Ikeda, Motoki

    Abstract | Document (575 KB) | BibTeX

    A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights
    Authors: Govorov, Artem ; Cai, Jin-Yi ; Dyer, Martin

    Abstract | Document (686 KB) | BibTeX

    Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs
    Authors: Izumi, Taisuke ; Otachi, Yota

    Abstract | Document (737 KB) | BibTeX

    Scheduling in the Random-Order Model
    Authors: Albers, Susanne ; Janke, Maximilian

    Abstract | Document (486 KB) | BibTeX

    Online Algorithms for Weighted Paging with Predictions
    Authors: Jiang, Zhihao ; Panigrahi, Debmalya ; Sun, Kevin

    Abstract | Document (571 KB) | BibTeX

    Popular Matchings with One-Sided Bias
    Authors: Kavitha, Telikepalli

    Abstract | Document (552 KB) | BibTeX

    Obviously Strategyproof Single-Minded Combinatorial Auctions
    Authors: de Keijzer, Bart ; Kyropoulou, Maria ; Ventre, Carmine

    Abstract | Document (531 KB) | BibTeX

    Knapsack Secretary with Bursty Adversary
    Authors: Kesselheim, Thomas ; Molinaro, Marco

    Abstract | Document (615 KB) | BibTeX

    The Iteration Number of Colour Refinement
    Authors: Kiefer, Sandra ; McKay, Brendan D.

    Abstract | Document (582 KB) | BibTeX

    Towards Optimal Set-Disjointness and Set-Intersection Data Structures
    Authors: Kopelowitz, Tsvi ; Vassilevska Williams, Virginia

    Abstract | Document (635 KB) | BibTeX

    Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
    Authors: Korman, Matias ; van Renssen, André ; Roeloffzen, Marcel ; Staals, Frank

    Abstract | Document (744 KB) | BibTeX

    Polytopes, Lattices, and Spherical Codes for the Nearest Neighbor Problem
    Authors: Laarhoven, Thijs

    Abstract | Document (873 KB) | BibTeX

    Deterministic Sparse Fourier Transform with an 𝓁_{∞} Guarantee
    Authors: Li, Yi ; Nakos, Vasileios

    Abstract | Document (542 KB) | BibTeX

    Faster Random k-CNF Satisfiability
    Authors: Lincoln, Andrea ; Yedidia, Adam

    Abstract | Document (633 KB) | BibTeX

    Succinct Filters for Sets of Unknown Sizes
    Authors: Liu, Mingmou ; Yin, Yitong ; Yu, Huacheng

    Abstract | Document (546 KB) | BibTeX

    A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion
    Authors: Lokshtanov, Daniel ; Misra, Pranabendu ; Panolan, Fahad ; Philip, Geevarghese ; Saurabh, Saket

    Abstract | Document (678 KB) | BibTeX

    Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
    Authors: Chechik, Shiri ; Magen, Ofer

    Abstract | Document (563 KB) | BibTeX

    Quantum Distributed Complexity of Set Disjointness on a Line
    Authors: Magniez, Frédéric ; Nayak, Ashwin

    Abstract | Document (1,787 KB) | BibTeX

    Can Verifiable Delay Functions Be Based on Random Oracles?
    Authors: Mahmoody, Mohammad ; Smith, Caleb ; Wu, David J.

    Abstract | Document (522 KB) | BibTeX

    On the Two-Dimensional Knapsack Problem for Convex Polygons
    Authors: Merino, Arturo ; Wiese, Andreas

    Abstract | Document (635 KB) | BibTeX

    Proportionally Fair Clustering Revisited
    Authors: Micha, Evi ; Shah, Nisarg

    Abstract | Document (508 KB) | BibTeX

    Breaking the Barrier of 2 for the Storage Allocation Problem
    Authors: Mömke, Tobias ; Wiese, Andreas

    Abstract | Document (599 KB) | BibTeX

    On the Complexity of Zero Gap MIP*
    Authors: Mousavi, Hamoon ; Nezhadi, Seyed Sajjad ; Yuen, Henry

    Abstract | Document (541 KB) | BibTeX

    Hypergraph Isomorphism for Groups with Restricted Composition Factors
    Authors: Neuen, Daniel

    Abstract | Document (557 KB) | BibTeX

    On Solving (Non)commutative Weighted Edmonds' Problem
    Authors: Oki, Taihei

    Abstract | Document (470 KB) | BibTeX

    A General Stabilization Bound for Influence Propagation in Graphs
    Authors: Papp, Pál András ; Wattenhofer, Roger

    Abstract | Document (491 KB) | BibTeX

    Network-Aware Strategies in Financial Systems
    Authors: Papp, Pál András ; Wattenhofer, Roger

    Abstract | Document (442 KB) | BibTeX

    Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity
    Authors: Pitassi, Toniann ; Shirley, Morgan ; Watson, Thomas

    Abstract | Document (611 KB) | BibTeX

    A Spectral Bound on Hypergraph Discrepancy
    Authors: Potukuchi, Aditya

    Abstract | Document (532 KB) | BibTeX

    Faster Dynamic Range Mode
    Authors: Sandlund, Bryce ; Xu, Yinzhan

    Abstract | Document (515 KB) | BibTeX

    An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes
    Authors: Sau, Ignasi ; Stamoulis, Giannos ; Thilikos, Dimitrios M.

    Abstract | Document (951 KB) | BibTeX

    Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
    Authors: Shao, Shuai ; Sun, Yuxin

    Abstract | Document (572 KB) | BibTeX

    Quasi-Majority Functional Voting on Expander Graphs
    Authors: Shimizu, Nobutaka ; Shiraga, Takeharu

    Abstract | Document (661 KB) | BibTeX

    Property Testing of LP-Type Problems
    Authors: Epstein, Rogers ; Silwal, Sandeep

    Abstract | Document (556 KB) | BibTeX

    Lower Bounds for Dynamic Distributed Task Allocation
    Authors: Su, Hsin-Hao ; Wein, Nicole

    Abstract | Document (430 KB) | BibTeX

    On the Degree of Boolean Functions as Polynomials over ℤ_m
    Authors: Sun, Xiaoming ; Sun, Yuan ; Wang, Jiaheng ; Wu, Kewen ; Xia, Zhiyu ; Zheng, Yufan

    Abstract | Document (554 KB) | BibTeX

    On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems
    Authors: Wahlström, Magnus

    Abstract | Document (530 KB) | BibTeX

    Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis
    Authors: Weiß, Armin

    Abstract | Document (655 KB) | BibTeX

    Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth
    Authors: Wiebking, Daniel

    Abstract | Document (579 KB) | BibTeX

    Parameterized Inapproximability for Steiner Orientation by Gap Amplification
    Authors: Włodarczyk, Michał

    Abstract | Document (799 KB) | BibTeX

    Near-Optimal Algorithm for Constructing Greedy Consensus Tree
    Authors: Wu, Hongxun

    Abstract | Document (525 KB) | BibTeX

    Decision Problems in Information Theory
    Authors: Abo Khamis, Mahmoud ; Kolaitis, Phokion G. ; Ngo, Hung Q. ; Suciu, Dan

    Abstract | Document (702 KB) | BibTeX

    Invariants for Continuous Linear Dynamical Systems
    Authors: Almagor, Shaull ; Kelmendi, Edon ; Ouaknine, Joël ; Worrell, James

    Abstract | Document (553 KB) | BibTeX

    On Higher-Order Cryptography
    Authors: Barak, Boaz ; Crubillé, Raphaëlle ; Dal Lago, Ugo

    Abstract | Document (640 KB) | BibTeX

    Cost Automata, Safe Schemes, and Downward Closures
    Authors: Barozzini, David ; Clemente, Lorenzo ; Colcombet, Thomas ; Parys, Paweł

    Abstract | Document (574 KB) | BibTeX

    Sensitive Instances of the Constraint Satisfaction Problem
    Authors: Barto, Libor ; Kozik, Marcin ; Tan, Johnson ; Valeriote, Matt

    Abstract | Document (572 KB) | BibTeX

    The Complexity of Bounded Context Switching with Dynamic Thread Creation
    Authors: Baumann, Pascal ; Majumdar, Rupak ; Thinniyam, Ramanathan S. ; Zetzsche, Georg

    Abstract | Document (651 KB) | BibTeX

    Two Variable Logic with Ultimately Periodic Counting
    Authors: Benedikt, Michael ; Kostylev, Egor V. ; Tan, Tony

    Abstract | Document (675 KB) | BibTeX

    Single-Use Automata and Transducers for Infinite Alphabets
    Authors: Bojańczyk, Mikołaj ; Stefański, Rafał

    Abstract | Document (1,125 KB) | BibTeX

    Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series
    Authors: Bostan, Alin ; Carayol, Arnaud ; Koechlin, Florent ; Nicaud, Cyril

    Abstract | Document (582 KB) | BibTeX

    On the Size of Finite Rational Matrix Semigroups
    Authors: Bumpus, Georgina ; Haase, Christoph ; Kiefer, Stefan ; Stoienescu, Paul-Ioan ; Tanner, Jonathan

    Abstract | Document (673 KB) | BibTeX

    Rational Subsets of Baumslag-Solitar Groups
    Authors: Cadilhac, Michaël ; Chistikov, Dmitry ; Zetzsche, Georg

    Abstract | Document (548 KB) | BibTeX

    On Polynomial Recursive Sequences
    Authors: Cadilhac, Michaël ; Mazowiecki, Filip ; Paperman, Charles ; Pilipczuk, Michał ; Sénizergues, Géraud

    Abstract | Document (724 KB) | BibTeX

    A Recipe for Quantum Graphical Languages
    Authors: Carette, Titouan ; Jeandel, Emmanuel

    Abstract | Document (602 KB) | BibTeX

    On the Power of Ordering in Linear Arithmetic Theories
    Authors: Chistikov, Dmitry ; Haase, Christoph

    Abstract | Document (740 KB) | BibTeX

    The Post Correspondence Problem and Equalisers for Certain Free Group and Monoid Morphisms
    Authors: Ciobanu, Laura ; Logan, Alan D.

    Abstract | Document (554 KB) | BibTeX

    Timed Games and Deterministic Separability
    Authors: Clemente, Lorenzo ; Lasota, Sławomir ; Piórkowski, Radosław

    Abstract | Document (619 KB) | BibTeX

    Dynamic Complexity of Reachability: How Many Changes Can We Handle?
    Authors: Datta, Samir ; Kumar, Pankaj ; Mukherjee, Anish ; Tawari, Anuj ; Vortmeier, Nils ; Zeume, Thomas

    Abstract | Document (579 KB) | BibTeX

    The Strahler Number of a Parity Game
    Authors: Daviaud, Laure ; Jurdziński, Marcin ; Thejaswini, K. S.

    Abstract | Document (507 KB) | BibTeX

    On the Structure of Solution Sets to Regular Word Equations
    Authors: Day, Joel D. ; Manea, Florin

    Abstract | Document (585 KB) | BibTeX

    From Linear to Additive Cellular Automata
    Authors: Dennunzio, Alberto ; Formenti, Enrico ; Grinberg, Darij ; Margara, Luciano

    Abstract | Document (516 KB) | BibTeX

    The Complexity of Knapsack Problems in Wreath Products
    Authors: Figelius, Michael ; Ganardi, Moses ; Lohrey, Markus ; Zetzsche, Georg

    Abstract | Document (600 KB) | BibTeX

    The Adversarial Stackelberg Value in Quantitative Games
    Authors: Filiot, Emmanuel ; Gentilini, Raffaella ; Raskin, Jean-François

    Abstract | Document (632 KB) | BibTeX

    The Topology of Local Computing in Networks
    Authors: Fraigniaud, Pierre ; Paz, Ami

    Abstract | Document (1,117 KB) | BibTeX

    The Complexity of Verifying Loop-Free Programs as Differentially Private
    Authors: Gaboardi, Marco ; Nissim, Kobbi ; Purser, David

    Abstract | Document (704 KB) | BibTeX

    Logical Characterisation of Hybrid Conformance
    Authors: Gazda, Maciej ; Mousavi, Mohammad Reza

    Abstract | Document (688 KB) | BibTeX

    Hrushovski’s Encoding and ω-Categorical CSP Monsters
    Authors: Gillibert, Pierre ; Jonušas, Julius ; Kompatscher, Michael ; Mottet, Antoine ; Pinsker, Michael

    Abstract | Document (631 KB) | BibTeX

    Descriptive Complexity on Non-Polish Spaces II
    Authors: Hoyrup, Mathieu

    Abstract | Document (531 KB) | BibTeX

    On Decidability of Time-Bounded Reachability in CTMDPs
    Authors: Majumdar, Rupak ; Salamati, Mahmoud ; Soudjani, Sadegh

    Abstract | Document (637 KB) | BibTeX

    When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?
    Authors: Maneth, Sebastian ; Seidl, Helmut

    Abstract | Document (545 KB) | BibTeX

    Implicit Automata in Typed λ-Calculi I: Aperiodicity in a Non-Commutative Logic
    Authors: Nguyễn, Lê Thành Dũng ; Pradic, Pierre

    Abstract | Document (605 KB) | BibTeX

    Computing Measures of Weak-MSO Definable Sets of Trees
    Authors: Niwiński, Damian ; Przybyłko, Marcin ; Skrzypczak, Michał

    Abstract | Document (560 KB) | BibTeX

    Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata
    Authors: Paul, Erik

    Abstract | Document (581 KB) | BibTeX

    On Skolem-Hardness and Saturation Points in Markov Decision Processes
    Authors: Piribauer, Jakob ; Baier, Christel

    Abstract | Document (609 KB) | BibTeX

    The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem
    Authors: Remscrim, Zachary

    Abstract | Document (522 KB) | BibTeX

    Hardness Results for Constant-Free Pattern Languages and Word Equations
    Authors: Saarela, Aleksi

    Abstract | Document (415 KB) | BibTeX

    Bisimulation Equivalence of Pushdown Automata Is Ackermann-Complete
    Authors: Zhang, Wenbo ; Yin, Qiang ; Long, Huan ; Xu, Xian

    Abstract | Document (618 KB) | BibTeX

      




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