ICALP - RankMe

143 papers

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