default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID47th ICALP 2020: Saarbrücken, Germany (Virtual Conference)
- Artur Czumaj
, Anuj Dawar, Emanuela Merelli:
47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference). LIPIcs 168, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-138-2 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:36
- Andrew Chi-Chih Yao:
An Incentive Analysis of Some Bitcoin Fee Designs (Invited Talk). 1:1-1:12 - Robert Krauthgamer:
Sketching Graphs and Combinatorial Optimization (Invited Talk). 2:1-2:1 - Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke, Dominik Wojtczak:
How to Play in Infinite MDPs (Invited Talk). 3:1-3:18 - Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling Lower Bounds via AND Subset Sum. 4:1-4:15 - Amir Abboud, Shon Feller, Oren Weimann:
On the Fine-Grained Complexity of Parity Problems. 5:1-5:19 - Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, Andrew Suh:
Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. 6:1-6:19 - Dan Alistarh, Giorgi Nadiradze, Amirmojtaba Sabour:
Dynamic Averaging Load Balancing on Cycles. 7:1-7:16 - Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, S. Matthew Weinberg:
Asynchronous Majority Dynamics in Preferential Attachment Trees. 8:1-8:14 - Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan:
The Power of Many Samples in Query Complexity. 9:1-9:18 - Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, Yann Vaxès:
Medians in Median Graphs and Their Cube Complexes in Linear Time. 10:1-10:17 - Suman K. Bera, Amit Chakrabarti, Prantar Ghosh:
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. 11:1-11:21 - Aaron Bernstein:
Improved Bounds for Matching in Random-Order Streams. 12:1-12:13 - Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch:
An Optimal Algorithm for Online Multiple Knapsack. 13:1-13:17 - Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro, Eva Rotenberg:
Space Efficient Construction of Lyndon Arrays in Linear Time. 14:1-14:18 - Greg Bodwin, Keerti Choudhary, Merav Parter, Noa Shahar:
New Fault Tolerant Subset Preservers. 15:1-15:19 - Marin Bougeret, Bart M. P. Jansen, Ignasi Sau:
Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel. 16:1-16:19 - Alex Brandts, Marcin Wrochna, Stanislav Zivný:
The Complexity of Promise SAT on Non-Boolean Domains. 17:1-17:13 - Milutin Brankovic, Nikola Grujic, André van Renssen, Martin P. Seybold:
A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions. 18:1-18:18 - Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz:
Faster Minimization of Tardy Processing Time on a Single Machine. 19:1-19:12 - Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, Marcel Roeloffzen:
Fréchet Distance for Uncertain Curves. 20:1-20:20 - Andrei A. Bulatov, Amineh Dadsetan:
Counting Homomorphisms in Plain Exponential Time. 21:1-21:18 - Jin-Yi Cai, Zhiguo Fu, Shuai Shao:
From Holant to Quantum Entanglement and Back. 22:1-22:16 - Jin-Yi Cai, Tianyu Liu:
Counting Perfect Matchings and the Eight-Vertex Model. 23:1-23:18 - Ruoxu Cen, Ran Duan, Yong Gu:
Roundtrip Spanners with (2k-1) Stretch. 24:1-24:11 - Diptarka Chakraborty, Keerti Choudhary:
New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures. 25:1-25:20 - Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', Kristýna Pekárková:
Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming. 26:1-26:19 - Panagiotis Charalampopoulos, Pawel Gawrychowski, Karol Pokorski:
Dynamic Longest Common Substring in Polylogarithmic Time. 27:1-27:19 - Rohit Chatterjee, Xiao Liang, Omkant Pandey:
Improved Black-Box Constructions of Composable Secure Computation. 28:1-28:20 - Shiri Chechik, Moran Nechushtan:
Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs. 29:1-29:12 - Yu Chen, Sampath Kannan, Sanjeev Khanna:
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. 30:1-30:19 - Man-Kwun Chiu, Aruni Choudhary, Wolfgang Mulzer:
Computational Complexity of the α-Ham-Sandwich Problem. 31:1-31:18 - George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, Clara Waldmann:
Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. 32:1-32:18 - Julia Chuzhoy, Merav Parter, Zihan Tan:
On Packing Low-Diameter Spanning Trees. 33:1-33:18 - Ilan Reuven Cohen, Sungjin Im, Debmalya Panigrahi:
Online Two-Dimensional Load Balancing. 34:1-34:21 - Mina Dalirrooyfard, Virginia Vassilevska Williams:
Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph. 35:1-35:20 - Anuj Dawar, Gregory Wilsenach:
Symmetric Arithmetic Circuits. 36:1-36:18 - Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey:
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. 37:1-37:18 - Argyrios Deligkas, John Fearnley, Rahul Savani:
Tree Polymatrix Games Are PPAD-Hard. 38:1-38:14 - Dean Doron, Jack Murtagh, Salil P. Vadhan, David Zuckerman:
Spectral Sparsification via Bounded-Independence Sampling. 39:1-39:21 - Jan Dreier, Henri Lotze, Peter Rossmanith:
Hard Problems on Random Graphs. 40:1-40:14 - Ran Duan, Haoqing He, Tianyi Zhang:
A Scaling Algorithm for Weighted f-Factors in General Graphs. 41:1-41:17 - Shaddin Dughmi:
The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem. 42:1-42:18 - Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg:
Extending Partial 1-Planar Drawings. 43:1-43:19 - Uriel Feige, Vadim Grinberg:
How to Hide a Clique? 44:1-44:13 - Hendrik Fichtenberger, Mingze Gao, Pan Peng:
Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time. 45:1-45:13 - Andrés Fielbaum, Ignacio Morales, José Verschae:
A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems. 46:1-46:15 - Arnold Filtser:
Scattering and Sparse Partitions, and Their Applications. 47:1-47:20 - Arnold Filtser, Omrit Filtser, Matthew J. Katz:
Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic. 48:1-48:19 - Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi:
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. 49:1-49:18 - Dimitris Fotakis, Anthimos Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, Stratis Skoulakis:
Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games. 50:1-50:19 - Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, Manolis Vardas:
The Online Min-Sum Set Cover Problem. 51:1-51:16 - Martin Fürer, Carlos Hoppen, Vilmar Trevisan:
Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth. 52:1-52:18 - Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Kuan Yang:
Counting Solutions to Random CNF Formulas. 53:1-53:14 - Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi:
Robust Algorithms for TSP and Steiner Tree. 54:1-54:18 - Chaya Ganesh, Bernardo Magri, Daniele Venturi:
Cryptographic Reverse Firewalls for Interactive Proof Systems. 55:1-55:16 - Paritosh Garg, Sagar Kale, Lars Rohwedder, Ola Svensson:
Robust Algorithms Under Adversarial Injections. 56:1-56:15 - Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Minimum Cut in O(m log² n) Time. 57:1-57:15 - Anna C. Gilbert, Albert Gu, Christopher Ré, Atri Rudra, Mary Wootters:
Sparse Recovery for Orthogonal Polynomial Transforms. 58:1-58:16 - Alexander Göke, Dániel Marx, Matthias Mnich:
Hitting Long Directed Cycles Is Fixed-Parameter Tractable. 59:1-59:18 - Petr Gregor, Ondrej Micka, Torsten Mütze:
On the Central Levels Problem. 60:1-60:17 - Rohit Gurjar, Rajat Rathi:
Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization. 61:1-61:15 - Venkatesan Guruswami, Sai Sandeep:
d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. 62:1-62:12 - Tuomas Hakoniemi:
Feasible Interpolation for Polynomial Calculus and Sums-Of-Squares. 63:1-63:14 - Sariel Har-Peled, Mitchell Jones, Saladi Rahul:
Active Learning a Convex Body in Low Dimensions. 64:1-64:17 - Hiroshi Hirai, Motoki Ikeda:
Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity. 65:1-65:19 - Artem Govorov, Jin-Yi Cai, Martin E. Dyer:
A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. 66:1-66:18 - Taisuke Izumi, Yota Otachi:
Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs. 67:1-67:17 - Susanne Albers, Maximilian Janke:
Scheduling in the Random-Order Model. 68:1-68:18 - Zhihao Jiang, Debmalya Panigrahi, Kevin Sun:
Online Algorithms for Weighted Paging with Predictions. 69:1-69:18 - Telikepalli Kavitha:
Popular Matchings with One-Sided Bias. 70:1-70:18 - Bart de Keijzer, Maria Kyropoulou, Carmine Ventre:
Obviously Strategyproof Single-Minded Combinatorial Auctions. 71:1-71:17 - Thomas Kesselheim, Marco Molinaro:
Knapsack Secretary with Bursty Adversary. 72:1-72:15 - Sandra Kiefer, Brendan D. McKay:
The Iteration Number of Colour Refinement. 73:1-73:19 - Tsvi Kopelowitz, Virginia Vassilevska Williams:
Towards Optimal Set-Disjointness and Set-Intersection Data Structures. 74:1-74:16 - Matias Korman, André van Renssen, Marcel Roeloffzen, Frank Staals:
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon. 75:1-75:17 - Thijs Laarhoven:
Polytopes, Lattices, and Spherical Codes for the Nearest Neighbor Problem. 76:1-76:14 - Yi Li, Vasileios Nakos:
Deterministic Sparse Fourier Transform with an ℓ∞ Guarantee. 77:1-77:14 - Andrea Lincoln, Adam Yedidia:
Faster Random k-CNF Satisfiability. 78:1-78:12 - Mingmou Liu, Yitong Yin, Huacheng Yu:
Succinct Filters for Sets of Unknown Sizes. 79:1-79:19 - Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, Saket Saurabh:
A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion. 80:1-80:16 - Shiri Chechik, Ofer Magen:
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. 81:1-81:17 - Frédéric Magniez, Ashwin Nayak:
Quantum Distributed Complexity of Set Disjointness on a Line. 82:1-82:18 - Mohammad Mahmoody, Caleb Smith, David J. Wu:
Can Verifiable Delay Functions Be Based on Random Oracles? 83:1-83:17 - Arturo Merino, Andreas Wiese:
On the Two-Dimensional Knapsack Problem for Convex Polygons. 84:1-84:16 - Evi Micha, Nisarg Shah:
Proportionally Fair Clustering Revisited. 85:1-85:16 - Tobias Mömke, Andreas Wiese:
Breaking the Barrier of 2 for the Storage Allocation Problem. 86:1-86:19 - Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen:
On the Complexity of Zero Gap MIP. 87:1-87:12 - Daniel Neuen:
Hypergraph Isomorphism for Groups with Restricted Composition Factors. 88:1-88:19 - Taihei Oki:
On Solving (Non)commutative Weighted Edmonds' Problem. 89:1-89:14 - Pál András Papp, Roger Wattenhofer:
A General Stabilization Bound for Influence Propagation in Graphs. 90:1-90:15 - Pál András Papp, Roger Wattenhofer:
Network-Aware Strategies in Financial Systems. 91:1-91:17 - Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. 92:1-92:19 - Aditya Potukuchi:
A Spectral Bound on Hypergraph Discrepancy. 93:1-93:14 - Bryce Sandlund, Yinzhan Xu:
Faster Dynamic Range Mode. 94:1-94:14 - Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos:
An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes. 95:1-95:20 - Shuai Shao, Yuxin Sun:
Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems. 96:1-96:15 - Nobutaka Shimizu, Takeharu Shiraga:
Quasi-Majority Functional Voting on Expander Graphs. 97:1-97:19 - Rogers Epstein, Sandeep Silwal:
Property Testing of LP-Type Problems. 98:1-98:18 - Hsin-Hao Su, Nicole Wein:
Lower Bounds for Dynamic Distributed Task Allocation. 99:1-99:14 - Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng:
On the Degree of Boolean Functions as Polynomials over ℤm. 100:1-100:19 - Magnus Wahlström:
On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems. 101:1-101:14 - Armin Weiß:
Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis. 102:1-102:19 - Daniel Wiebking:
Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth. 103:1-103:16 - Michal Wlodarczyk:
Parameterized Inapproximability for Steiner Orientation by Gap Amplification. 104:1-104:19 - Hongxun Wu:
Near-Optimal Algorithm for Constructing Greedy Consensus Tree. 105:1-105:14 - Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, Dan Suciu:
Decision Problems in Information Theory. 106:1-106:20 - Shaull Almagor, Edon Kelmendi, Joël Ouaknine, James Worrell:
Invariants for Continuous Linear Dynamical Systems. 107:1-107:15 - Boaz Barak, Raphaëlle Crubillé, Ugo Dal Lago:
On Higher-Order Cryptography. 108:1-108:16 - David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys:
Cost Automata, Safe Schemes, and Downward Closures. 109:1-109:18 - Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote:
Sensitive Instances of the Constraint Satisfaction Problem. 110:1-110:18 - Pascal Baumann, Rupak Majumdar, Ramanathan S. Thinniyam, Georg Zetzsche:
The Complexity of Bounded Context Switching with Dynamic Thread Creation. 111:1-111:16 - Michael Benedikt, Egor V. Kostylev, Tony Tan:
Two Variable Logic with Ultimately Periodic Counting. 112:1-112:16 - Mikolaj Bojanczyk, Rafal Stefanski:
Single-Use Automata and Transducers for Infinite Alphabets. 113:1-113:14 - Alin Bostan, Arnaud Carayol, Florent Koechlin, Cyril Nicaud:
Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series. 114:1-114:16 - Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu, Jonathan Tanner:
On the Size of Finite Rational Matrix Semigroups. 115:1-115:13 - Michaël Cadilhac, Dmitry Chistikov, Georg Zetzsche:
Rational Subsets of Baumslag-Solitar Groups. 116:1-116:16 - Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michal Pilipczuk, Géraud Sénizergues:
On Polynomial Recursive Sequences. 117:1-117:17 - Titouan Carette, Emmanuel Jeandel:
A Recipe for Quantum Graphical Languages. 118:1-118:17 - Dmitry Chistikov, Christoph Haase:
On the Power of Ordering in Linear Arithmetic Theories. 119:1-119:15 - Laura Ciobanu, Alan D. Logan:
The Post Correspondence Problem and Equalisers for Certain Free Group and Monoid Morphisms. 120:1-120:16 - Lorenzo Clemente, Slawomir Lasota, Radoslaw Piórkowski:
Timed Games and Deterministic Separability. 121:1-121:16 - Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume:
Dynamic Complexity of Reachability: How Many Changes Can We Handle? 122:1-122:19 - Laure Daviaud, Marcin Jurdzinski, K. S. Thejaswini:
The Strahler Number of a Parity Game. 123:1-123:19 - Joel D. Day, Florin Manea:
On the Structure of Solution Sets to Regular Word Equations. 124:1-124:16 - Alberto Dennunzio, Enrico Formenti, Darij Grinberg, Luciano Margara:
From Linear to Additive Cellular Automata. 125:1-125:13 - Michael Figelius, Moses Ganardi, Markus Lohrey, Georg Zetzsche:
The Complexity of Knapsack Problems in Wreath Products. 126:1-126:18 - Emmanuel Filiot, Raffaella Gentilini, Jean-François Raskin:
The Adversarial Stackelberg Value in Quantitative Games. 127:1-127:18 - Pierre Fraigniaud, Ami Paz:
The Topology of Local Computing in Networks. 128:1-128:18 - Marco Gaboardi, Kobbi Nissim, David Purser:
The Complexity of Verifying Loop-Free Programs as Differentially Private. 129:1-129:17 - Maciej Gazda, Mohammad Reza Mousavi:
Logical Characterisation of Hybrid Conformance. 130:1-130:18 - Pierre Gillibert, Julius Jonusas, Michael Kompatscher, Antoine Mottet, Michael Pinsker:
Hrushovski's Encoding and ω-Categorical CSP Monsters. 131:1-131:17 - Mathieu Hoyrup:
Descriptive Complexity on Non-Polish Spaces II. 132:1-132:17 - Rupak Majumdar, Mahmoud Salamati, Sadegh Soudjani:
On Decidability of Time-Bounded Reachability in CTMDPs. 133:1-133:19 - Sebastian Maneth, Helmut Seidl:
When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic? 134:1-134:18 - Lê Thành Dung Nguyên, Cécilia Pradic:
Implicit Automata in Typed λ-Calculi I: Aperiodicity in a Non-Commutative Logic. 135:1-135:20 - Damian Niwinski, Marcin Przybylko, Michal Skrzypczak:
Computing Measures of Weak-MSO Definable Sets of Trees. 136:1-136:18 - Erik Paul:
Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata. 137:1-137:15 - Jakob Piribauer, Christel Baier:
On Skolem-Hardness and Saturation Points in Markov Decision Processes. 138:1-138:17 - Zachary Remscrim:
The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem. 139:1-139:18 - Aleksi Saarela:
Hardness Results for Constant-Free Pattern Languages and Word Equations. 140:1-140:15 - Wenbo Zhang, Qiang Yin, Huan Long, Xian Xu:
Bisimulation Equivalence of Pushdown Automata Is Ackermann-Complete. 141:1-141:14
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-02-20 19:48 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
