default search action
46th ICALP 2019: Patras, Greece
- Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi:
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. LIPIcs 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019, ISBN 978-3-95977-109-2 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:38
- Michal Feldman:
Auction Design under Interdependent Values (Invited Talk). 1:1-1:1 - Martin Grohe
:
Symmetry and Similarity (Invited Talk). 2:1-2:1 - Ola Svensson
Approximately Good and Modern Matchings (Invited Talk). 3:1-3:1 - Frits W. Vaandrager
Automata Learning and Galois Connections (Invited Talk). 4:1-4:1 - Mihalis Yannakakis:
Fixed Point Computation Problems and Facets of Complexity (Invited Talk). 5:1-5:1 - Scott Aaronson, Alexandru Cojocaru
Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. 6:1-6:13 - Amir Abboud, Loukas Georgiadis
Faster Algorithms for All-Pairs Bounded Min-Cuts. 7:1-7:15 - Amir Abboud:
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. 8:1-8:13 - Mikkel Abrahamsen
Geometric Multicut. 9:1-9:15 - Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen:
Lower Bounds for Multiplication via Network Coding. 10:1-10:12 - Akanksha Agrawal
Path Contraction Faster Than 2n. 11:1-11:13 - Noga Alon, Shiri Chechik, Sarel Cohen:
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. 12:1-12:14 - Bertie Ancona, Monika Henzinger
Algorithms and Hardness for Diameter in Dynamic Graphs. 13:1-13:14 - Alexandr Andoni, Clifford Stein, Peilin Zhong:
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. 14:1-14:16 - Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki:
Two Party Distribution Testing: Communication and Security. 15:1-15:16 - Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar
Two New Results About Quantum Exact Learning. 16:1-16:15 - Sepehr Assadi, Shay Solomon:
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time. 17:1-17:17 - Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff:
Robust Communication-Optimal Distributed Clustering Algorithms. 18:1-18:16 - Kyriakos Axiotis, Christos Tzamos:
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. 19:1-19:13 - Yair Bartal, Nova Fandina, Ofer Neiman:
Covering Metric Spaces by Few Trees. 20:1-20:16 - Giulia Bernardini
Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication. 21:1-21:15 - Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
The Complexity of Approximating the Matching Polynomial in the Complex Plane. 22:1-22:13 - Therese Biedl
Finding Tutte Paths in Linear Time. 23:1-23:14 - Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi:
Approximate Counting of k-Paths: Deterministic and in Polynomial Space. 24:1-24:15 - Andreas Björklund, Ryan Williams:
Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. 25:1-25:14 - Andreas Björklund, Petteri Kaski, Ryan Williams:
Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. 26:1-26:13 - Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li
Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. 27:1-27:14 - Alex B. Grilo:
A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round. 28:1-28:13 - Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, Benoît Larose:
Dismantlability, Connectedness, and Mixing in Relational Structures. 29:1-29:15 - Mark Bun, Nikhil S. Mande
Sign-Rank Can Increase Under Intersection. 30:1-30:14 - Angel A. Cantu, Austin Luchsinger, Robert T. Schweller, Tim Wylie:
Covert Computation in Self-Assembled Circuits. 31:1-31:14 - Igor Carboni Oliveira:
Randomness and Intractability in Kolmogorov Complexity. 32:1-32:14 - Shantanav Chakraborty
The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. 33:1-33:14 - Jérémie Chalopin, Victor Chepoi
Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. 34:1-34:15 - Arkadev Chattopadhyay, Yuval Filmus
Query-To-Communication Lifting for BPP Using Inner Product. 35:1-35:15 - Xue Chen, Eric Price:
Estimating the Frequency of a Clustered Signal. 36:1-36:13 - Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu:
Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. 37:1-37:15 - Siu-Wing Cheng
Restricted Max-Min Allocation: Approximation and Integrality Gap. 38:1-38:13 - Mahdi Cheraghchi
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. 39:1-39:14 - Eden Chlamtác, Michael Dinitz
The Norms of Graph Spanners. 40:1-40:15 - Vincent Cohen-Addad, Jason Li:
On the Fixed-Parameter Tractability of Capacitated Clustering. 41:1-41:14 - Vincent Cohen-Addad, Anupam Gupta, Amit Kumar
Tight FPT Approximations for k-Median and k-Means. 42:1-42:14 - Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth
Information-Theoretic and Algorithmic Thresholds for Group Testing. 43:1-43:14 - Thomas Colcombet
On Reachability Problems for Low-Dimensional Matrix Semigroups. 44:1-44:15 - Graham Cormode
Independent Sets in Vertex-Arrival Streams. 45:1-45:14 - Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu:
Approximation Algorithms for Min-Distance Problems. 46:1-46:14 - Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein:
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. 47:1-47:15 - Ran Duan, Ce Jin, Hongxun Wu:
Faster Algorithms for All Pairs Non-Decreasing Paths Problem. 48:1-48:13 - Guillaume Ducoffe:
Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs. 49:1-49:13 - Josep Díaz, Lefteris M. Kirousis
Algorithmically Efficient Syntactic Characterization of Possibility Domains. 50:1-50:13 - Julian Dörfler, Christian Ikenmeyer, Greta Panova:
On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions. 51:1-51:14 - Talya Eden, Dana Ron
The Arboricity Captures the Complexity of Sampling Edges. 52:1-52:14 - Alina Ene, Huy L. Nguyen:
A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. 53:1-53:12 - Alina Ene, Huy L. Nguyen:
Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint. 54:1-54:14 - Massimo Equi, Roberto Grossi, Veli Mäkinen
On the Complexity of String Matching for Graphs. 55:1-55:15 - John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani
Unique End of Potential Line. 56:1-56:15 - Miron Ficak
Dichotomy for Symmetric Boolean PCSPs. 57:1-57:12 - Yuval Filmus
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. 58:1-58:13 - Fedor V. Fomin
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. 59:1-59:13 - Fedor V. Fomin
Decomposition of Map Graphs with Applications. 60:1-60:15 - Tobias Friedrich
The Satisfiability Threshold for Non-Uniform Random 2-SAT. 61:1-61:14 - Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha:
Determinant Equivalence Test over Finite Fields and over Q. 62:1-62:15 - Naveen Garg
Non-Clairvoyant Precedence Constrained Scheduling. 63:1-63:14 - Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. 64:1-64:13 - Paul W. Goldberg
The Hairy Ball Problem is PPAD-Complete. 65:1-65:14 - Alexander Golovnev, Rahul Ilango, Russell Impagliazzo
AC0[p] Lower Bounds Against MCSP via the Coin Problem. 66:1-66:15 - Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc
Stochastic Online Metric Matching. 67:1-67:14 - Venkatesan Guruswami, Lingfei Jin
Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. 68:1-68:14 - Yassine Hamoudi
Quantum Chebyshev's Inequality and Applications. 69:1-69:16 - Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram:
Retracting Graphs to Cycles. 70:1-70:15 - Falko Hegerfeld
On Adaptive Algorithms for Maximum Matching. 71:1-71:16 - Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff:
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. 72:1-72:14 - Zhiyi Huang, Xue Zhu:
Scalable and Jointly Differentially Private Packing. 73:1-73:12 - Klaus Jansen, Lars Rohwedder
Local Search Breaks 1.75 for Graph Balancing. 74:1-74:14 - Klaus Jansen, Alexandra Lassota
Near-Linear Time Algorithm for n-fold ILPs via Color Coding. 75:1-75:13 - Ce Jin:
An Improved FPTAS for 0-1 Knapsack. 76:1-76:14 - Vladimir Kolmogorov:
Testing the Complexity of a Valued CSP Language. 77:1-77:12 - Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi:
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. 78:1-78:15 - Adam Kurpisz
Sum-Of-Squares Bounds via Boolean Function Analysis. 79:1-79:15 - William Kuszmaul:
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation. 80:1-80:15 - Bingkai Lin
A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. 81:1-81:15 - Jannik Matuschke, Ulrike Schmidt-Kraepelin, José Verschae:
Maintaining Perfect Matchings at Low Cost. 82:1-82:14 - Arturo Merino
The Minimum Cost Query Problem on Matroids with Uncertainty Areas. 83:1-83:14 - Ian Mertz
Short Proofs Are Hard to Find. 84:1-84:16 - Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. 85:1-85:15 - Benjamin Moseley:
Scheduling to Approximate Minimization Objectives on Identical Machines. 86:1-86:14 - Nabil H. Mustafa:
Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set. 87:1-87:12 - Joseph (Seffi) Naor, Seeun William Umboh
Tight Bounds for Online Weighted Tree Augmentation. 88:1-88:14 - Merav Parter, Eylon Yogev:
Optimal Short Cycle Decomposition in Almost Linear Time. 89:1-89:14 - Konstantinos Panagiotou, Matija Pasch:
Satisfiability Thresholds for Regular Occupation Problems. 90:1-90:14 - Akbar Rafiey
Toward a Dichotomy for Approximation of H-Coloring. 91:1-91:16 - Venkatesan Guruswami
Beating Fredman-Komlós for Perfect k-Hashing. 92:1-92:14 - Thomas Sauerwald, Luca Zanetti:
Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities. 93:1-93:15 - Xiaoming Sun
Querying a Matrix Through Matrix-Vector Products. 94:1-94:16 - Mikkel Thorup
Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps. 95:1-95:13 - Thomas Watson:
Amplification with One NP Oracle Query. 96:1-96:13 - David P. Woodruff, Guang Yang:
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. 97:1-97:14 - Chaoping Xing
Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph. 98:1-98:13 - Joran van Apeldoorn, András Gilyén:
Improvements in Quantum SDP-Solving with Applications. 99:1-99:15 - Bader Abu Radi, Orna Kupferman:
Minimizing GFG Transition-Based Automata. 100:1-100:16 - Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, Carlo Sartiani:
A Type System for Interactive JSON Schema Inference (Extended Abstract). 101:1-101:13 - Nikhil Balaji
On the Complexity of Value Iteration. 102:1-102:15 - Pablo Barceló
Monadic Decomposability of Regular Relations. 103:1-103:14 - Pablo Barceló
Boundedness of Conjunctive Regular Path Queries. 104:1-104:15 - Paul C. Bell
Polynomially Ambiguous Probabilistic Automata on Restricted Languages. 105:1-105:14 - Mikolaj Bojanczyk, Sandra Kiefer
String-to-String Interpretations With Polynomial-Size Output. 106:1-106:14 - Paul Brunet
A Kleene Theorem for Nominal Automata. 107:1-107:13 - Titouan Carette, Emmanuel Jeandel
Completeness of Graphical Languages for Mixed States Quantum Mechanics. 108:1-108:15 - Katrin Casel, Joel D. Day
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number. 109:1-109:16 - Laura Ciobanu
Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE. 110:1-110:15 - Ugo Dal Lago
Differential Logical Relations, Part I: The Simply-Typed Case. 111:1-111:14 - Anuj Dawar
Approximations of Isomorphism and Logics with Linear-Algebraic Operators. 112:1-112:14 - Holger Dell
Counting Answers to Existential Questions. 113:1-113:15 - Dani Dorfman, Haim Kaplan, Uri Zwick:
A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games. 114:1-114:14 - Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis:
Reachability for Branching Concurrent Stochastic Games. 115:1-115:14 - Marie Fortin:
FO = FO3 for Linear Orders with Monotone Binary Relations. 116:1-116:13 - Martin Grohe, Sandra Kiefer
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus. 117:1-117:15 - Mehran Hosseini
Termination of Linear Loops over the Integers. 118:1-118:13 - Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke
Büchi Objectives in Countable MDPs. 119:1-119:14 - Christof Löding, Anton Pirogov
Determinization of Büchi Automata: Unifying the Approaches of Safra and Muller-Schupp. 120:1-120:13 - Antonio Molina Lovett
Optimal Regular Expressions for Permutations. 121:1-121:12 - Anca Muscholl, Gabriele Puppis
Equivalence of Finite-Valued Streaming String Transducers Is Decidable. 122:1-122:15 - Lê Thành Dung Nguyên
From Normal Functors to Logarithmic Space Queries. 123:1-123:15 - Matthieu Picantin
Automatic Semigroups vs Automaton Semigroups. 124:1-124:15 - Jean-Éric Pin, Christophe Reutenauer:
A Mahler's Theorem for Word Functions. 125:1-125:13 - Thomas Place, Marc Zeitoun:
On All Things Star-Free. 126:1-126:14 - Martin Raszyk
From Nondeterministic to Multi-Head Deterministic Finite-State Transducers. 127:1-127:14 - Pierre-Alain Reynier, Didier Villevalois:
Sequentiality of String-to-Context Transducers. 128:1-128:14 - Sylvain Schmitz
The Parametric Complexity of Lossy Counter Machines. 129:1-129:15 - Henning Urbat, Stefan Milius:
Varieties of Data Languages. 130:1-130:14 - Eleni C. Akrida
How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs? 131:1-131:14 - Matthias Bonne, Keren Censor-Hillel:
Distributed Detection of Cliques in Dynamic Networks. 132:1-132:15 - Ioannis Caragiannis, Angelo Fanelli
On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies. 133:1-133:12 - Arnaud Casteigts
Temporal Cliques Admit Sparse Spanners. 134:1-134:14 - Keren Censor-Hillel, Mikaël Rabie:
Distributed Reconfiguration of Maximal Independent Sets. 135:1-135:14 - Aris Anagnostopoulos
Stochastic Graph Exploration. 136:1-136:14 - Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, Sunil M. Shende:
Energy Consumption of Group Search on a Line. 137:1-137:15 - Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. 138:1-138:14 - Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov:
Exploration of High-Dimensional Grids by Finite Automata. 139:1-139:16 - Yuval Emek, Shay Kutten, Ron Lavi
Deterministic Leader Election in Programmable Matter. 140:1-140:14 - Thomas Erlebach
Two Moves per Time Step Make a Difference. 141:1-141:14 - Mohsen Ghaffari, Ali Sayyadi:
Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication. 142:1-142:14 - Siddharth Gupta, Adrian Kosowski, Laurent Viennot:
Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. 143:1-143:15 - Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, Pascal Pfister:
Optimal Strategies for Patrolling Fences. 144:1-144:13 - Sungjin Im, Benjamin Moseley, Kirk Pruhs, Manish Purohit:
Matroid Coflow Scheduling. 145:1-145:14 - Amos Korman
Multi-Round Cooperative Search Games with Multiple Players. 146:1-146:14 - Dariusz R. Kowalski, Miguel A. Mosteiro:
Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader. 147:1-147:15 - Frederik Mallmann-Trenn, Yannic Maus, Dominik Pajak
Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol. 148:1-148:16 - Shunhao Oh, Anuja Meetoo Appavoo, Seth Gilbert
Periodic Bandits and Wireless Network Selection. 149:1-149:15 - Christian Scheideler
On the Complexity of Local Graph Transformations. 150:1-150:14 - Daniel Schmand
Network Investment Games with Wardrop Followers. 151:1-151: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 2024-09-26 23:31 CEST 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: