default search action
44th ICALP 2017: Warsaw, Poland
- Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl:
44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland. LIPIcs 80, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-041-5 - Front Matter, Table of Contents, Preface, Organization, List of Authors. 0:i-0:xlii
- Mikolaj Bojanczyk:
Orbit-Finite Sets and Their Algorithms (Invited Talk). 1:1-1:14 - Monika Henzinger:
Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk). 2:1-2:1 - Ronitt Rubinfeld:
Local Computation Algorithms (Invited Talk). 3:1-3:1 - Mikkel Thorup
:
Fast and Powerful Hashing Using Tabulation (Invited Talk). 4:1-4:2 - Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. 5:1-5:14 - Guy Even, Reut Levi, Moti Medina
Sublinear Random Access Generators for Preferential Attachment Graphs. 6:1-6:15 - Talya Eden, Dana Ron
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. 7:1-7:13 - Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin:
Near-Optimal Closeness Testing of Discrete Histogram Distributions. 8:1-8:15 - Omri Ben-Eliezer, Simon Korman, Daniel Reichman:
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays. 9:1-9:14 - Susanne Albers, Dennis Kraft:
On the Value of Penalties in Time-Inconsistent Planning. 10:1-10:12 - Jing Chen, Bo Li
Efficient Approximations for the Online Dispersion Problem. 11:1-11:15 - Viswanath Nagarajan, Xiangkun Shen:
Online Covering with Sum of $ell_q$-Norm Objectives. 12:1-12:12 - Marcin Bienkowski
Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration. 13:1-13:14 - Christian Coester
The Infinite Server Problem. 14:1-14:14 - Guy Kindler, Ryan O'Donnell:
Quantum Automata Cannot Detect Biased Coins, Even in the Limit. 15:1-15:8 - Miriam Backens
A New Holant Dichotomy Inspired by Quantum Computation. 16:1-16:14 - Richard Cleve, Chunhao Wang:
Efficient Quantum Algorithms for Simulating Lindblad Evolution. 17:1-17:14 - Catalin Dohotaru, Peter Høyer
Controlled Quantum Amplification. 18:1-18:13 - Rajesh Jayaram, Barna Saha:
Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!. 19:1-19:15 - Robert Krauthgamer, Ohad Trabelsi:
Conditional Lower Bounds for All-Pairs Max-Flow. 20:1-20:13 - Marvin Künnemann, Ramamohan Paturi, Stefan Schneider:
On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. 21:1-21:15 - Marek Cygan
On Problems Equivalent to (min, +)-Convolution. 22:1-22:15 - Marc Bury, Chris Schwiegelshohn:
On Finding the Jaccard Center. 23:1-23:14 - Shaull Almagor
The Polytope-Collision Problem. 24:1-24:14 - Omer Gold, Micha Sharir:
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier. 25:1-25:14 - Guy E. Blelloch, Yan Gu, Yihan Sun:
Efficient Construction of Probabilistic Tree Embeddings. 26:1-26:14 - Andreas Galanis, Leslie Ann Goldberg, Kuan Yang:
Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems. 27:1-27:14 - Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Inapproximability of the Independent Set Polynomial Below the Shearer Threshold. 28:1-28:13 - Jiabao Lin, Hanpin Wang:
The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights. 29:1-29:14 - Alex Galicki:
Polynomial-Time Rademacher Theorem, Porosity and Randomness. 30:1-30:13 - Antonios Antoniadis, Ruben Hoeksma
A QPTAS for the General Scheduling Problem with Identical Release Dates. 31:1-31:14 - André Linhares, Chaitanya Swamy:
Improved Algorithms for MST and Metric-TSP Interdiction. 32:1-32:14 - Matthias Kohler
Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces. 33:1-33:12 - Shahar Chen, Dotan Di Castro, Zohar S. Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, Roy Schwartz:
Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification. 34:1-34:15 - Marek Adamczyk, Fabrizio Grandoni
When the Optimum is also Blind: a New Perspective on Universal Optimization. 35:1-35:15 - Shweta Agrawal, Ishaan Preet Singh:
Reusable Garbled Deterministic Finite Automata from Learning With Errors. 36:1-36:13 - Ran Cohen
Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols. 37:1-37:15 - Daniel Apon, Nico Döttling, Sanjam Garg
Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13. 38:1-38:16 - Krzysztof Pietrzak, Maciej Skorski
Non-Uniform Attacks Against Pseudoentropy. 39:1-39:13 - Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
Interactive Oracle Proofs with Constant Rate and Query Complexity. 40:1-40:15 - Josh Alman, Matthias Mnich
Dynamic Parameterized Problems and Algorithms. 41:1-41:16 - Loukas Georgiadis
Decremental Data Structures for Connectivity and Dominators in Directed Graphs. 42:1-42:15 - Aaron Bernstein, Yann Disser, Martin Groß:
General Bounds for Incremental Maximization. 43:1-43:14 - Aaron Bernstein:
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. 44:1-44:14 - Greg Bodwin:
Testing Core Membership in Public Goods Economies. 45:1-45:14 - Toni Böhnlein, Stefan Kratsch, Oliver Schaudt:
Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting. 46:1-46:13 - Yiannis Giannakopoulos
Online Market Intermediation. 47:1-47:14 - Nick Gravin, Yuval Peres, Balasubramanian Sivan:
Tight Lower Bounds for Multiplicative Weights Algorithmic Families. 48:1-48:14 - Badih Ghazi, Madhu Sudan:
The Power of Shared Randomness in Uncertain Communication. 49:1-49:14 - Benjamin Rossman, Srikanth Srinivasan
Separation of AC^0[oplus] Formulas and Circuits. 50:1-50:13 - Chengyu Lin
Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers. 51:1-51:13 - Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson:
Randomized Communication vs. Partition Number. 52:1-52:15 - Andrej Bogdanov, Christopher Williamson:
Approximate Bounded Indistinguishability. 53:1-53:11 - Ivona Bezáková, Radu Curticapean, Holger Dell
Finding Detours is Fixed-Parameter Tractable. 54:1-54:14 - Sara Ahmadian, Zachary Friggstad:
Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs. 55:1-55:13 - Fedor V. Fomin
Covering Vectors by Spaces: Regular Matroids. 56:1-56:15 - Archontia C. Giannopoulou
Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes. 57:1-57:15 - Gregory Z. Gutin, Felix Reidl
k-Distinct In- and Out-Branchings in Digraphs. 58:1-58:13 - Eric Price, Zhao Song, David P. Woodruff:
Fast Regression with an $ell_infty$ Guarantee. 59:1-59:14 - Yi Li
Embeddings of Schatten Norms with Applications to Data Streams. 60:1-60:14 - Vasileios Nakos:
On Fast Decoding of High-Dimensional Signals from One-Bit Measurements. 61:1-61:14 - Juha Kärkkäinen, Marcin Piatkowski
String Inference from Longest-Common-Prefix Array. 62:1-62:14 - Kord Eickmeyer
Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. 63:1-63:14 - Mathias Bæk Tejs Knudsen:
Additive Spanners and Distance Oracles in Quadratic Time. 64:1-64:12 - Fedor V. Fomin
Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. 65:1-65:15 - Pascal Schweitzer
A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry. 66:1-66:14 - Andreas Wiese
A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time. 67:1-67:13 - Yoichi Iwata:
Linear-Time Kernelization for Feedback Vertex Set. 68:1-68:14 - Serge Gaspers, Edward J. Lee:
Exact Algorithms via Multivariate Subroutines. 69:1-69:13 - Florian Barbero, Christophe Paul
Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs. 70:1-70:13 - Daniel Lokshtanov, Amer E. Mouawad
Packing Cycles Faster Than Erdos-Posa. 71:1-71:15 - Surender Baswana, Keerti Choudhary
An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model. 72:1-72:15 - Greg Bodwin, Fabrizio Grandoni
Preserving Distances in Very Faulty Graphs. 73:1-73:14 - Loukas Georgiadis
All-Pairs 2-Reachability in O(n^w log n) Time. 74:1-74:14 - Lena Schlipf, Jens M. Schmidt
Edge-Orders. 75:1-75:14 - Laura Mancinska, David E. Roberson
Relaxations of Graph Isomorphism. 76:1-76:14 - Aviad Rubinstein:
Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder. 77:1-77:13 - Pasin Manurangsi, Prasad Raghavendra:
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. 78:1-78:15 - Pasin Manurangsi:
Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis. 79:1-79:14 - Prasad Raghavendra, Benjamin Weitz:
On the Bit Complexity of Sum-of-Squares Proofs. 80:1-80:13 - Amos Korman, Yoav Rodeh:
The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback. 81:1-81:13 - Sebastian Brandt, Yuval Emek, Jara Uitto, Roger Wattenhofer:
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game. 82:1-82:13 - Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis:
Stochastic Control via Entropy Compression. 83:1-83:13 - Dariusz Dereniowski
Approximation Strategies for Generalized Binary Search in Weighted Trees. 84:1-84:14 - Pavel Pudlák, Dominik Scheder
Tighter Hard Instances for PPSZ. 85:1-85:13 - Venkatesan Guruswami, Chaoping Xing
Subspace Designs Based on Algebraic Function Fields. 86:1-86:10 - Shafi Goldwasser, Ofer Grossman:
Bipartite Perfect Matching in Pseudo-Deterministic NC. 87:1-87:13 - Mikhail A. Raskin
A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model. 88:1-88:12 - Jannik Matuschke, S. Thomas McCormick, Gianpaolo Oriolo:
Rerouting Flows When Links Fail. 89:1-89:13 - Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine:
The Parameterized Complexity of Positional Games. 90:1-90:14 - Andreas Björklund, Petteri Kaski, Ioannis Koutis
Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. 91:1-91:14 - Euiwoong Lee
Improved Hardness for Cut, Interdiction, and Firefighter Problems. 92:1-92:14 - Benjamin Rossman:
Subspace-Invariant AC^0 Formulas. 93:1-93:11 - Dmitry Chistikov, Christoph Haase
On the Complexity of Quantified Integer Programming. 94:1-94:13 - Artur Jez
Word Equations in Nondeterministic Linear Space. 95:1-95:13 - Volker Diekert, Murray Elder
Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups. 96:1-96:14 - Kazuyuki Asada, Naoki Kobayashi
Pumping Lemma for Higher-order Languages. 97:1-97:14 - Samir Datta
A Strategy for Dynamic Programs: Start over and Muddle Through. 98:1-98:14 - Nicolas Bacquey, Etienne Grandjean, Frédéric Olive:
Definability by Horn Formulas and Linear Time on Cellular Automata. 99:1-99:14 - Fabian Reiter
Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment. 100:1-100:14 - Jérémie Chalopin, Victor Chepoi
A Counterexample to Thiagarajan's Conjecture on Regular Event Structures. 101:1-101:14 - Gilles Barthe
*-Liftings for Differential Privacy. 102:1-102:12 - Borja Balle, Pascale Gourdeau, Prakash Panangaden:
Bisimulation Metrics for Weighted Automata. 103:1-103:14 - Giovanni Bacci
On the Metric-Based Approximate Minimization of Markov Chains. 104:1-104:14 - Nathanaël Fijalkow
Expressiveness of Probabilistic Modal Logics, Revisited. 105:1-105:12 - Mikolaj Bojanczyk, Hugo Gimbert, Edon Kelmendi:
Emptiness of Zero Automata Is Decidable. 106:1-106:13 - Michael Benedikt, Pierre Bourhis, Michael Vanden Boom:
Characterizing Definability in Decidable Fixpoint Logics. 107:1-107:14 - Jean Christoph Jung
Conservative Extensions in Guarded and Two-Variable Fragments. 108:1-108:14 - Gilles Dowek
Models and Termination of Proof Reduction in the lambda Pi-Calculus Modulo Theory. 109:1-109:14 - Albert Atserias, Joanna Ochremiak:
Proof Complexity Meets Algebra. 110:1-110:14 - Antoine Amarilli, Pierre Bourhis, Louis Jachiet, Stefan Mengel:
A Circuit-Based Approach to Efficient Enumeration. 111:1-111:15 - Rajeev Alur, Konstantinos Mamouras, Caleb Stanford
Automata-Based Stream Processing. 112:1-112:15 - Luc Dartois
On Reversible Transducers. 113:1-113:12 - Mikolaj Bojanczyk, Laure Daviaud
Which Classes of Origin Graphs Are Generated by Transducers. 114:1-114:13 - Michaël Cadilhac
Continuity and Rational Functions. 115:1-115:14 - Olivier Bournez, Amaury Pouly:
A Universal Ordinary Differential Equation. 116:1-116:14 - Lorenzo Clemente, Wojciech Czerwinski
Regular Separability of Parikh Automata. 117:1-117:13 - Bernard Boigelot, Isabelle Mainz, Victor Marsault, Michel Rigo
An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention. 118:1-118:14 - Diego Figueira
Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One. 119:1-119:14 - Laura Bozzelli, Alberto Molinari
Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption. 120:1-120:14 - Raphaël Berthon
Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes. 121:1-121:15 - Alain Finkel, Étienne Lozes:
Synchronizability of Communicating Finite State Machines is not Decidable. 122:1-122:14 - Nicolas Basset, Gilles Geeraerts, Jean-François Raskin
Admissiblity in Concurrent Games. 123:1-123:14 - Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. 124:1-124:16 - Vittorio Bilò
Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems. 125:1-125:13 - Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, Saeed Seddighin:
Stochastic k-Server: How Should Uber Work?. 126:1-126:14 - Manoj Gupta, Shahbaz Khan
Multiple Source Dual Fault Tolerant BFS Trees. 127:1-127:15 - Mikkel Abrahamsen
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs. 128:1-128:14 - Eyjólfur Ingi Ásgeirsson, Magnús M. Halldórsson
Universal Framework for Wireless Scheduling Problems. 129:1-129:15 - Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez
Streaming Communication Protocols. 130:1-130:14 - Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, Christian Sohler
Testable Bounded Degree Graph Properties Are Random Order Streamable. 131:1-131:14 - Barun Gorain, Andrzej Pelc:
Deterministic Graph Exploration with Advice. 132:1-132:14 - Martin Hoefer, Bojana Kodric
Combinatorial Secretary Problems with Ordinal Information. 133:1-133:14 - Moshe Babaioff, Liad Blumrosen, Noam Nisan:
Selling Complementary Goods: Dynamics, Efficiency and Revenue. 134:1-134:14 - Jayesh Choudhari, Anirban Dasgupta
Saving Critical Nodes with Firefighters is FPT. 135:1-135:13 - Othon Michail, George Skretas, Paul G. Spirakis:
On the Transformation Capability of Feasible Mechanisms for Programmable Matter. 136:1-136:15 - Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Christian Sohler:
Distributed Monitoring of Network Properties: The Power of Hybrid Networks. 137:1-137:15 - Benjamin Doerr, Anatolii Kostrygin:
Randomized Rumor Spreading Revisited. 138:1-138:14 - Leran Cai, Thomas Sauerwald:
Randomized Load Balancing on Networks with Stochastic Inputs. 139:1-139:14 - Tung Mai, Ioannis Panageas, Vijay V. Vazirani:
Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion. 140:1-140:14 - Amanda Belleville, David Doty
Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols. 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-11-14 22:25 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: