Intl. Colloquium on Automata, Languages, and Programming, ICALP 2017


Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion

Tung Mai, Ioannis Panageas, Vijay V. Vazirani

Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Richard Cleve, Chunhao Wang

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Details
Discussion Comments: 0
Verification: Authors have not verified information

Embeddings of Schatten Norms with Applications to Data Streams

Yi Li, David P. Woodruff

Embeddings of Schatten Norms with Applications to Data Streams

Details
Discussion Comments: 0
Verification: Authors have not verified information

Finding Detours is Fixed-Parameter Tractable

Ivona Bezáková, Radu Curticapean, Holger Dell, Fedor V. Fomin

Finding Detours is Fixed-Parameter Tractable

Details
Discussion Comments: 0
Verification: Authors have not verified information

Randomized Rumor Spreading Revisited

Benjamin Doerr, Anatolii Kostrygin

Randomized Rumor Spreading Revisited

Details
Discussion Comments: 0
Verification: Authors have not verified information

Covering Vectors by Spaces: Regular Matroids

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh

Covering Vectors by Spaces: Regular Matroids

Details
Discussion Comments: 0
Verification: Authors have not verified information

Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems

Andreas Galanis, Leslie Ann Goldberg, Kuan Yang

Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems

Vittorio Bilò, Ioannis Caragiannis, Angelo Fanelli, Michele Flammini, Gianpiero Monaco

Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Synchronizability of Communicating Finite State Machines is not Decidable

Alain Finkel, Étienne Lozes

Synchronizability of Communicating Finite State Machines is not Decidable

Details
Discussion Comments: 0
Verification: Authors have not verified information

Automata-Based Stream Processing

Rajeev Alur, Konstantinos Mamouras, Caleb Stanford

Automata-Based Stream Processing

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Testable Bounded Degree Graph Properties Are Random Order Streamable

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, Christian Sohler

Testable Bounded Degree Graph Properties Are Random Order Streamable

Details
Discussion Comments: 0
Verification: Authors have not verified information

Subspace-Invariant AC^0 Formulas

Benjamin Rossman

Subspace-Invariant AC^0 Formulas

Details
Discussion Comments: 0
Verification: Author has not verified information

On the Metric-Based Approximate Minimization of Markov Chains

Giovanni Bacci, Giorgio Bacci, Kim G. Larsen, Radu Mardare

On the Metric-Based Approximate Minimization of Markov Chains

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Universal Ordinary Differential Equation

Olivier Bournez, Amaury Pouly

A Universal Ordinary Differential Equation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, Nikos Parotsidis

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Definability by Horn Formulas and Linear Time on Cellular Automata

Nicolas Bacquey, Etienne Grandjean, Frédéric Olive

Definability by Horn Formulas and Linear Time on Cellular Automata

Details
Discussion Comments: 0
Verification: Authors have not verified information

Continuity and Rational Functions

Michaël Cadilhac, Olivier Carton, Charles Paperman

Continuity and Rational Functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Combinatorial Secretary Problems with Ordinal Information

Martin Hoefer, Bojana Kodric

Combinatorial Secretary Problems with Ordinal Information

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers

Chengyu Lin, Shengyu Zhang

Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes

Raphaël Berthon, Mickael Randour, Jean-François Raskin

Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Power of Shared Randomness in Uncertain Communication

Badih Ghazi, Madhu Sudan

The Power of Shared Randomness in Uncertain Communication

Details
Discussion Comments: 0
Verification: Authors have not verified information

Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs

Sara Ahmadian, Zachary Friggstad

Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Pumping Lemma for Higher-order Languages

Kazuyuki Asada, Naoki Kobayashi

Pumping Lemma for Higher-order Languages

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed Monitoring of Network Properties: The Power of Hybrid Networks

Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Christian Sohler

Distributed Monitoring of Network Properties: The Power of Hybrid Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces

Matthias Kohler, Harald Räcke

Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces

Details
Discussion Comments: 0
Verification: Authors have not verified information

Randomized Load Balancing on Networks with Stochastic Inputs

Leran Cai, Thomas Sauerwald

Randomized Load Balancing on Networks with Stochastic Inputs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One

Diego Figueira, Ranko Lazic, Jérôme Leroux, Filip Mazowiecki, Grégoire Sutre

Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One

Details
Discussion Comments: 0
Verification: Authors have not verified information

Saving Critical Nodes with Firefighters is FPT

Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, M. S. Ramanujan

Saving Critical Nodes with Firefighters is FPT

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exact Algorithms via Multivariate Subroutines

Serge Gaspers, Edward J. Lee

Exact Algorithms via Multivariate Subroutines

Details
Discussion Comments: 0
Verification: Authors have not verified information

Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols

Ran Cohen, Sandro Coretti, Juan A. Garay, Vassilis Zikas

Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols

Details
Discussion Comments: 0
Verification: Authors have not verified information

Rerouting Flows When Links Fail

Jannik Matuschke, S. Thomas McCormick, Gianpaolo Oriolo

Rerouting Flows When Links Fail

Details
Discussion Comments: 0
Verification: Authors have not verified information

Non-Uniform Attacks Against Pseudoentropy

Krzysztof Pietrzak, Maciej Skorski

Non-Uniform Attacks Against Pseudoentropy

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximation Strategies for Generalized Binary Search in Weighted Trees

Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski, Mengchuan Zou

Approximation Strategies for Generalized Binary Search in Weighted Trees

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

A Counterexample to Thiagarajan's Conjecture on Regular Event Structures

Jérémie Chalopin, Victor Chepoi

A Counterexample to Thiagarajan's Conjecture on Regular Event Structures

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk)

Monika Henzinger

Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Reusable Garbled Deterministic Finite Automata from Learning With Errors

Shweta Agrawal, Ishaan Preet Singh

Reusable Garbled Deterministic Finite Automata from Learning With Errors

Details
Discussion Comments: 0
Verification: Authors have not verified information

Word Equations in Nondeterministic Linear Space

Artur Jez

Word Equations in Nondeterministic Linear Space

Details
Discussion Comments: 0
Verification: Author has not verified information

On Reversible Transducers

Luc Dartois, Paulin Fournier, Ismaël Jecker, Nathan Lhote

On Reversible Transducers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Randomized Communication vs. Partition Number

Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson

Randomized Communication vs. Partition Number

Details
Discussion Comments: 0
Verification: Authors have not verified information

Selling Complementary Goods: Dynamics, Efficiency and Revenue

Moshe Babaioff, Liad Blumrosen, Noam Nisan

Selling Complementary Goods: Dynamics, Efficiency and Revenue

Details
Discussion Comments: 0
Verification: Authors have not verified information

Characterizing Definability in Decidable Fixpoint Logics

Michael Benedikt, Pierre Bourhis, Michael Vanden Boom

Characterizing Definability in Decidable Fixpoint Logics

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Polytope-Collision Problem

Shaull Almagor, Joël Ouaknine, James Worrell

The Polytope-Collision Problem

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model

Mikhail Raskin

A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Author has verified information

The Parameterized Complexity of Positional Games

Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine

The Parameterized Complexity of Positional Games

Details
Discussion Comments: 0
Verification: Authors have not verified information

Near-Optimal Closeness Testing of Discrete Histogram Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

Near-Optimal Closeness Testing of Discrete Histogram Distributions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Polynomial-Time Rademacher Theorem, Porosity and Randomness

Alex Galicki

Polynomial-Time Rademacher Theorem, Porosity and Randomness

Details
Discussion Comments: 0
Verification: Author has not verified information

When the Optimum is also Blind: a New Perspective on Universal Optimization

Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi, Michal Wlodarczyk

When the Optimum is also Blind: a New Perspective on Universal Optimization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Streaming Communication Protocols

Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez

Streaming Communication Protocols

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online Covering with Sum of $ell_q$-Norm Objectives

Viswanath Nagarajan, Xiangkun Shen

Online Covering with Sum of $ell_q$-Norm Objectives

Details
Discussion Comments: 0
Verification: Authors have not verified information

Tight Lower Bounds for Multiplicative Weights Algorithmic Families

Nick Gravin, Yuval Peres, Balasubramanian Sivan

Tight Lower Bounds for Multiplicative Weights Algorithmic Families

Details
Discussion Comments: 0
Verification: Authors have not verified information

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs

Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Mikkel Abrahamsen, Stephen Alstrup, Stephen Holm, Mathias Bæk Tejs Knudsen, Morten Stöckel

Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder

Aviad Rubinstein

Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder

Details
Discussion Comments: 0
Verification: Author has not verified information

Additive Spanners and Distance Oracles in Quadratic Time

Mathias Bæk Tejs Knudsen

Additive Spanners and Distance Oracles in Quadratic Time

Details
Discussion Comments: 0
Verification: Author has not verified information

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Omer Gold, Micha Sharir

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Details
Discussion Comments: 0
Verification: Authors have not verified information

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Complexity of Quantified Integer Programming

Dmitry Chistikov, Christoph Haase

On the Complexity of Quantified Integer Programming

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Circuit-Based Approach to Efficient Enumeration

Antoine Amarilli, Pierre Bourhis, Louis Jachiet, Stefan Mengel

A Circuit-Based Approach to Efficient Enumeration

Details
Discussion Comments: 0
Verification: Authors have not verified information

Relaxations of Graph Isomorphism

Laura Mancinska, David E. Roberson, Robert Sámal, Simone Severini, Antonios Varvitsiotis

Relaxations of Graph Isomorphism

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Tight Lower Bound for the Capture Time of the Cops and Robbers Game

Sebastian Brandt, Yuval Emek, Jara Uitto, Roger Wattenhofer

A Tight Lower Bound for the Capture Time of the Cops and Robbers Game

Details
Discussion Comments: 0
Verification: Authors have not verified information

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes

Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Separation of AC^0[oplus] Formulas and Circuits

Benjamin Rossman, Srikanth Srinivasan

Separation of AC^0[oplus] Formulas and Circuits

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!

Rajesh Jayaram, Barna Saha

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast and Powerful Hashing Using Tabulation (Invited Talk)

Mikkel Thorup

Fast and Powerful Hashing Using Tabulation (Invited Talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Efficient Approximations for the Online Dispersion Problem

Jing Chen, Bo Li, Yingkai Li

Efficient Approximations for the Online Dispersion Problem

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration

Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha

Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration

Details
Discussion Comments: 0
Verification: Authors have not verified information

Tighter Hard Instances for PPSZ

Pavel Pudlák, Dominik Scheder, Navid Talebanfard

Tighter Hard Instances for PPSZ

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Bit Complexity of Sum-of-Squares Proofs

Prasad Raghavendra, Benjamin Weitz

On the Bit Complexity of Sum-of-Squares Proofs

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention

Bernard Boigelot, Isabelle Mainz, Victor Marsault, Michel Rigo

An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention

Details
Discussion Comments: 0
Verification: Authors have not verified information

Models and Termination of Proof Reduction in the lambda Pi-Calculus Modulo Theory

Gilles Dowek

Models and Termination of Proof Reduction in the lambda Pi-Calculus Modulo Theory

Details
Discussion Comments: 0
Verification: Author has not verified information

Emptiness of Zero Automata Is Decidable

Mikolaj Bojanczyk, Hugo Gimbert, Edon Kelmendi

Emptiness of Zero Automata Is Decidable

Details
Discussion Comments: 0
Verification: Authors have not verified information

Controlled Quantum Amplification

Catalin Dohotaru, Peter Høyer

Controlled Quantum Amplification

Details
Discussion Comments: 0
Verification: Authors have not verified information

Edge-Orders

Lena Schlipf, Jens M. Schmidt

Edge-Orders

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection

Talya Eden, Dana Ron, C. Seshadhri

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deterministic Graph Exploration with Advice

Barun Gorain, Andrzej Pelc

Deterministic Graph Exploration with Advice

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements

Vasileios Nakos

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements

Details
Discussion Comments: 0
Verification: Author has not verified information

Conditional Lower Bounds for All-Pairs Max-Flow

Robert Krauthgamer, Ohad Trabelsi

Conditional Lower Bounds for All-Pairs Max-Flow

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Infinite Server Problem

Christian Coester, Elias Koutsoupias, Philip Lazos

The Infinite Server Problem

Details
Discussion Comments: 0
Verification: Authors have not verified information

Inapproximability of the Independent Set Polynomial Below the Shearer Threshold

Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic

Inapproximability of the Independent Set Polynomial Below the Shearer Threshold

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online Market Intermediation

Yiannis Giannakopoulos, Elias Koutsoupias, Philip Lazos

Online Market Intermediation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient Construction of Probabilistic Tree Embeddings

Guy E. Blelloch, Yan Gu, Yihan Sun

Efficient Construction of Probabilistic Tree Embeddings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Stochastic Control via Entropy Compression

Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis

Stochastic Control via Entropy Compression

Details
Discussion Comments: 0
Verification: Authors have not verified information

Quantum Automata Cannot Detect Biased Coins, Even in the Limit

Guy Kindler, Ryan O'Donnell

Quantum Automata Cannot Detect Biased Coins, Even in the Limit

Details
Discussion Comments: 0
Verification: Authors have not verified information

Interactive Oracle Proofs with Constant Rate and Query Complexity

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Interactive Oracle Proofs with Constant Rate and Query Complexity

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

Details
Discussion Comments: 0
Verification: Authors have not verified information

Local Computation Algorithms (Invited Talk)

Ronitt Rubinfeld

Local Computation Algorithms (Invited Talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

*-Liftings for Differential Privacy

Gilles Barthe, Thomas Espitau, Justin Hsu, Tetsuya Sato, Pierre-Yves Strub

*-Liftings for Differential Privacy

Details
Discussion Comments: 0
Verification: Authors have not verified information

A QPTAS for the General Scheduling Problem with Identical Release Dates

Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, Andreas Wiese

A QPTAS for the General Scheduling Problem with Identical Release Dates

Details
Discussion Comments: 0
Verification: Authors have not verified information

Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols

Amanda Belleville, David Doty, David Soloveichik

Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry

Pascal Schweitzer

A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry

Details
Discussion Comments: 0
Verification: Author has not verified information

Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting

Toni Böhnlein, Stefan Kratsch, Oliver Schaudt

Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting

Details
Discussion Comments: 0
Verification: Authors have not verified information

Admissiblity in Concurrent Games

Nicolas Basset, Gilles Geeraerts, Jean-François Raskin, Ocan Sankur

Admissiblity in Concurrent Games

Details
Discussion Comments: 0
Verification: Authors have not verified information

Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis

Pasin Manurangsi

Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis

Details
Discussion Comments: 0
Verification: Author has not verified information

Conservative Extensions in Guarded and Two-Variable Fragments

Jean Christoph Jung, Carsten Lutz, Mauricio Martel, Thomas Schneider, Frank Wolter

Conservative Extensions in Guarded and Two-Variable Fragments

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sublinear Random Access Generators for Preferential Attachment Graphs

Guy Even, Reut Levi, Moti Medina, Adi Rosén

Sublinear Random Access Generators for Preferential Attachment Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Linear-Time Kernelization for Feedback Vertex Set

Yoichi Iwata

Linear-Time Kernelization for Feedback Vertex Set

Details
Discussion Comments: 0
Verification: Author has not verified information

Testing Core Membership in Public Goods Economies

Greg Bodwin

Testing Core Membership in Public Goods Economies

Details
Discussion Comments: 0
Verification: Author has not verified information

A Strategy for Dynamic Programs: Start over and Muddle Through

Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume

A Strategy for Dynamic Programs: Start over and Muddle Through

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast Regression with an $ell_infty$ Guarantee

Eric Price, Zhao Song, David P. Woodruff

Fast Regression with an $ell_infty$ Guarantee

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximate Bounded Indistinguishability

Andrej Bogdanov, Christopher Williamson

Approximate Bounded Indistinguishability

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Algorithms for MST and Metric-TSP Interdiction

André Linhares, Chaitanya Swamy

Improved Algorithms for MST and Metric-TSP Interdiction

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced artifacts
Verification: Authors have verified information

Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment

Fabian Reiter

Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Author has verified information

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Daniel Apon, Nico Döttling, Sanjam Garg, Pratyay Mukherjee

Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

Pasin Manurangsi, Prasad Raghavendra

A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs

Aaron Bernstein

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs

Details
Discussion Comments: 0
Verification: Author has not verified information

An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model

Surender Baswana, Keerti Choudhary, Liam Roditty

An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Value of Penalties in Time-Inconsistent Planning

Susanne Albers, Dennis Kraft

On the Value of Penalties in Time-Inconsistent Planning

Details
Discussion Comments: 0
Verification: Authors have not verified information

Which Classes of Origin Graphs Are Generated by Transducers

Mikolaj Bojanczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle

Which Classes of Origin Graphs Are Generated by Transducers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Subspace Designs Based on Algebraic Function Fields

Venkatesan Guruswami, Chaoping Xing, Chen Yuan

Subspace Designs Based on Algebraic Function Fields

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Transformation Capability of Feasible Mechanisms for Programmable Matter

Othon Michail, George Skretas, Paul G. Spirakis

On the Transformation Capability of Feasible Mechanisms for Programmable Matter

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic Parameterized Problems and Algorithms

Josh Alman, Matthias Mnich, Virginia Vassilevska Williams

Dynamic Parameterized Problems and Algorithms

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Finding the Jaccard Center

Marc Bury, Chris Schwiegelshohn

On Finding the Jaccard Center

Details
Discussion Comments: 0
Verification: Authors have not verified information

Bisimulation Metrics for Weighted Automata

Borja Balle, Pascale Gourdeau, Prakash Panangaden

Bisimulation Metrics for Weighted Automata

Details
Discussion Comments: 0
Verification: Authors have not verified information

A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time

Andreas Wiese

A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time

Details
Discussion Comments: 0
Verification: Author has not verified information

All-Pairs 2-Reachability in O(n^w log n) Time

Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, Przemyslaw Uznanski

All-Pairs 2-Reachability in O(n^w log n) Time

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Multiple Source Dual Fault Tolerant BFS Trees

Manoj Gupta, Shahbaz Khan

Multiple Source Dual Fault Tolerant BFS Trees

Details
Discussion Comments: 0
Verification: Authors have not verified information

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Andreas Björklund, Petteri Kaski, Ioannis Koutis

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Details
Discussion Comments: 0
Verification: Authors have not verified information

String Inference from Longest-Common-Prefix Array

Juha Kärkkäinen, Marcin Piatkowski, Simon J. Puglisi

String Inference from Longest-Common-Prefix Array

Details
Discussion Comments: 0
Verification: Authors have not verified information

General Bounds for Incremental Maximization

Aaron Bernstein, Yann Disser, Martin Groß

General Bounds for Incremental Maximization

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

Amos Korman, Yoav Rodeh

The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

Details
Discussion Comments: 0
Verification: Authors have not verified information

Proof Complexity Meets Algebra

Albert Atserias, Joanna Ochremiak

Proof Complexity Meets Algebra

Details
Discussion Comments: 0
Verification: Authors have not verified information

k-Distinct In- and Out-Branchings in Digraphs

Gregory Z. Gutin, Felix Reidl, Magnus Wahlström

k-Distinct In- and Out-Branchings in Digraphs

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Stochastic k-Server: How Should Uber Work?

Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, Saeed Seddighin

Stochastic k-Server: How Should Uber Work?

Details
Discussion Comments: 0
Verification: Authors have not verified information

Preserving Distances in Very Faulty Graphs

Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams

Preserving Distances in Very Faulty Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

A New Holant Dichotomy Inspired by Quantum Computation

Miriam Backens

A New Holant Dichotomy Inspired by Quantum Computation

Details
Discussion Comments: 0
Verification: Author has not verified information

The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights

Jiabao Lin, Hanpin Wang

The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs

Florian Barbero, Christophe Paul, Michal Pilipczuk

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays

Omri Ben-Eliezer, Simon Korman, Daniel Reichman

Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays

Details
Discussion Comments: 0
Verification: Authors have not verified information

Universal Framework for Wireless Scheduling Problems

Eyjólfur Ingi Ásgeirsson, Magnús M. Halldórsson, Tigran Tonoyan

Universal Framework for Wireless Scheduling Problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Fine-Grained Complexity of One-Dimensional Dynamic Programming

Marvin Künnemann, Ramamohan Paturi, Stefan Schneider

On the Fine-Grained Complexity of One-Dimensional Dynamic Programming

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Problems Equivalent to (min, +)-Convolution

Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk

On Problems Equivalent to (min, +)-Convolution

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs

Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger

Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption

Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron, Pietro Sala

Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption

Details
Discussion Comments: 0
Verification: Authors have not verified information

Packing Cycles Faster Than Erdos-Posa

Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, Meirav Zehavi

Packing Cycles Faster Than Erdos-Posa

Details
Discussion Comments: 0
Verification: Authors have not verified information

Orbit-Finite Sets and Their Algorithms (Invited Talk)

Mikolaj Bojanczyk

Orbit-Finite Sets and Their Algorithms (Invited Talk)

Details
Discussion Comments: 0
Verification: Author has not verified information

Regular Separability of Parikh Automata

Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, Charles Paperman

Regular Separability of Parikh Automata

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Hardness for Cut, Interdiction, and Firefighter Problems

Euiwoong Lee

Improved Hardness for Cut, Interdiction, and Firefighter Problems

Details
Discussion Comments: 0
Verification: Author has not verified information

Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

Volker Diekert, Murray Elder

Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

Details
Discussion Comments: 0
Verification: Authors have not verified information

Bipartite Perfect Matching in Pseudo-Deterministic NC

Shafi Goldwasser, Ofer Grossman

Bipartite Perfect Matching in Pseudo-Deterministic NC

Details
Discussion Comments: 0
Verification: Authors have not verified information

Expressiveness of Probabilistic Modal Logics, Revisited

Nathanaël Fijalkow, Bartek Klin, Prakash Panangaden

Expressiveness of Probabilistic Modal Logics, Revisited

Details
Discussion Comments: 0
Verification: Authors have not verified information