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


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

Algorithms for Noisy Broadcast with Erasures

Ofer Grossman, Bernhard Haeupler, Sidhanth Mohanty

Algorithms for Noisy Broadcast with Erasures

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

A PTAS for a Class of Stochastic Dynamic Programs

Hao Fu, Jian Li, Pan Xu

A PTAS for a Class of Stochastic Dynamic Programs

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

A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes

Koyo Hayashi

A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes

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

NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors

Amey Bhangale

NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors

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

Improved Bounds for Shortest Paths in Dense Distance Graphs

Pawel Gawrychowski, Adam Karczmarz

Improved Bounds for Shortest Paths in Dense Distance Graphs

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

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels

Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels

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

Gaifman Normal Forms for Counting Extensions of First-Order Logic

Dietrich Kuske, Nicole Schweikardt

Gaifman Normal Forms for Counting Extensions of First-Order Logic

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

Fully Dynamic MIS in Uniformly Sparse Graphs

Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

Fully Dynamic MIS in Uniformly Sparse Graphs

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

Demand-Independent Optimal Tolls

Riccardo Colini-Baldeschi, Max Klimm, Marco Scarsini

Demand-Independent Optimal Tolls

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

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d

Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d

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

Resolving SINR Queries in a Dynamic Setting

Boris Aronov, Gali Bar-On, Matthew J. Katz

Resolving SINR Queries in a Dynamic Setting

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

Rollercoasters and Caterpillars

Therese C. Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, Jeffrey Shallit

Rollercoasters and Caterpillars

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

Separating Without Any Ambiguity

Thomas Place, Marc Zeitoun

Separating Without Any Ambiguity

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

Byzantine Gathering in Polynomial Time

Sébastien Bouchard, Yoann Dieudonné, Anissa Lamani

Byzantine Gathering in Polynomial Time

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

Polynomial Vector Addition Systems With States

Jérôme Leroux

Polynomial Vector Addition Systems With States

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

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

Marco L. Carmosino, Russell Impagliazzo, Manuel Sabin

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

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

Approximate Convex Hull of Data Streams

Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, Lin F. Yang

Approximate Convex Hull of Data Streams

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

An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences

Dirk Nowotka, Aleksi Saarela

An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences

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

Improved Algorithms for Adaptive Compressed Sensing

Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang

Improved Algorithms for Adaptive Compressed Sensing

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

New algorithms for Steiner tree reoptimization

Davide Bilò

New algorithms for Steiner tree reoptimization

Details
Author Comments:
Discussion Comments: 0
Sharing: Other
Verification: Author has verified information

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

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

Maximizing Profit with Convex Costs in the Random-order Model

Anupam Gupta, Ruta Mehta, Marco Molinaro

Maximizing Profit with Convex Costs in the Random-order Model

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

Synchronization Strings: List Decoding for Insertions and Deletions

Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan

Synchronization Strings: List Decoding for Insertions and Deletions

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

Small Bias Requires Large Formulas

Andrej Bogdanov

Small Bias Requires Large Formulas

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

Practical and Provably Secure Onion Routing

Megumi Ando, Anna Lysyanskaya, Eli Upfal

Practical and Provably Secure Onion Routing

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

The Bottleneck Complexity of Secure Multiparty Computation

Elette Boyle, Abhishek Jain, Manoj Prabhakaran, Ching-Hua Yu

The Bottleneck Complexity of Secure Multiparty Computation

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

The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE

Géraud Sénizergues, Armin Weiß

The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE

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

On the Probe Complexity of Local Computation Algorithms

Uriel Feige, Boaz Patt-Shamir, Shai Vardi

On the Probe Complexity of Local Computation Algorithms

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

A Faster Construction of Greedy Consensus Trees

Pawel Gawrychowski, Gad M. Landau, Wing-Kin Sung, Oren Weimann

A Faster Construction of Greedy Consensus Trees

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

Tight Bounds on Online Checkpointing Algorithms

Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, Adi Shamir

Tight Bounds on Online Checkpointing Algorithms

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

The Beta-Bernoulli process and algebraic effects

Sam Staton, Dario Stein, Hongseok Yang, Nathanael Leedom Ackerman, Cameron E. Freer, Daniel M. Roy

The Beta-Bernoulli process and algebraic effects

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

Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

Buddhima Gamlath, Sangxia Huang, Ola Svensson

Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

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

Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable

Mingyu Xiao, Hiroshi Nagamochi

Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable

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

Semicomputable Geometry

Mathieu Hoyrup, Diego Nava Saucedo, Don M. Stull

Semicomputable Geometry

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

One-Way Trail Orientations

Anders Aamand, Niklas Hjuler, Jacob Holm, Eva Rotenberg

One-Way Trail Orientations

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

Power of d Choices with Simple Tabulation

Anders Aamand, Mathias Bæk Tejs Knudsen, Mikkel Thorup

Power of d Choices with Simple Tabulation

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

Brief Announcement: Energy Constrained Depth First Search

Shantanu Das, Dariusz Dereniowski, Przemyslaw Uznanski

Brief Announcement: Energy Constrained Depth First Search

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

Finer Tight Bounds for Coloring on Clique-Width

Michael Lampis

Finer Tight Bounds for Coloring on Clique-Width

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

Ring Packing and Amortized FHEW Bootstrapping

Daniele Micciancio, Jessica Sorrell

Ring Packing and Amortized FHEW Bootstrapping

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

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies

Shashwat Garg

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies

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

Temporal Vertex Cover with a Sliding Time Window

Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, Viktor Zamaraev

Temporal Vertex Cover with a Sliding Time Window

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

Brief Announcement: Bayesian Auctions with Efficient Queries

Jing Chen, Bo Li, Yingkai Li, Pinyan Lu

Brief Announcement: Bayesian Auctions with Efficient Queries

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

Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication

Daniel Graf, Karim Labib, Przemyslaw Uznanski

Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication

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

Brief Announcement: MapReduce Algorithms for Massive Trees

MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Vahab S. Mirrokni

Brief Announcement: MapReduce Algorithms for Massive Trees

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

Price of Anarchy for Mechanisms with Risk-Averse Agents

Thomas Kesselheim, Bojana Kodric

Price of Anarchy for Mechanisms with Risk-Averse Agents

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

To Infinity and Beyond

Ines Klimann

To Infinity and Beyond

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

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

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

CacheShuffle: A Family of Oblivious Shuffles

Sarvar Patel, Giuseppe Persiano, Kevin Yeo

CacheShuffle: A Family of Oblivious Shuffles

Details
Author Comments:
Discussion Comments: 0
Sharing: Not able to share produced artifacts
Verification: Authors have verified information

Probability Theory from a Programming Perspective (Invited Paper)

Sam Staton

Probability Theory from a Programming Perspective (Invited Paper)

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

A Faster FPTAS for #Knapsack

Pawel Gawrychowski, Liran Markin, Oren Weimann

A Faster FPTAS for #Knapsack

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

Parameterized Low-Rank Binary Matrix Approximation

Fedor V. Fomin, Petr A. Golovach, Fahad Panolan

Parameterized Low-Rank Binary Matrix Approximation

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

Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams

Shay Golan, Tsvi Kopelowitz, Ely Porat

Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams

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

Almost Sure Productivity

Alejandro Aguirre, Gilles Barthe, Justin Hsu, Alexandra Silva

Almost Sure Productivity

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

A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton

Mikhail Raskin

A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton

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

How to Navigate Through Obstacles?

Eduard Eiben, Iyad A. Kanj

How to Navigate Through Obstacles?

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

Restricted Max-Min Fair Allocation

Siu-Wing Cheng, Yuchen Mao

Restricted Max-Min Fair Allocation

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

Sublinear Algorithms for MAXCUT and Correlation Clustering

Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian

Sublinear Algorithms for MAXCUT and Correlation Clustering

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

Gray Codes and Symmetric Chains

Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, Kaja Wille

Gray Codes and Symmetric Chains

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

Generalized Comparison Trees for Point-Location Problems

Daniel M. Kane, Shachar Lovett, Shay Moran

Generalized Comparison Trees for Point-Location Problems

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

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface

Albert Atserias, Stephan Kreutzer, Marc Noy

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface

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

Fully-Dynamic Bin Packing with Little Repacking

Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, David Wajc

Fully-Dynamic Bin Packing with Little Repacking

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

Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States

Chinmay Nirkhe, Umesh Vazirani, Henry Yuen

Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States

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

Unboundedness Problems for Languages of Vector Addition Systems

Wojciech Czerwinski, Piotr Hofman, Georg Zetzsche

Unboundedness Problems for Languages of Vector Addition Systems

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

Computing Tutte Paths

Andreas Schmid, Jens M. Schmidt

Computing Tutte Paths

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

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

Sixue Liu

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

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

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

Heng Guo, Mark Jerrum

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

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

Optimally Sorting Evolving Data

Juan José Besa Vial, William E. Devanny, David Eppstein, Michael T. Goodrich, Timothy Johnson

Optimally Sorting Evolving Data

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

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors

Sofya Raskhodnikova, Nithin M. Varma

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors

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

Randomized Sliding Window Algorithms for Regular Languages

Moses Ganardi, Danny Hucke, Markus Lohrey

Randomized Sliding Window Algorithms for Regular Languages

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

Parameterized Algorithms for Zero Extension and Metric Labelling Problems

Felix Reidl, Magnus Wahlström

Parameterized Algorithms for Zero Extension and Metric Labelling Problems

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

Efficient Black-Box Reductions for Separable Cost Sharing

Tobias Harks, Martin Hoefer, Anja Huber, Manuel Surek

Efficient Black-Box Reductions for Separable Cost Sharing

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

High Probability Frequency Moment Sketches

Sumit Ganguly, David P. Woodruff

High Probability Frequency Moment Sketches

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

On Computing the Total Variation Distance of Hidden Markov Models

Stefan Kiefer

On Computing the Total Variation Distance of Hidden Markov Models

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

Brief Announcement: Towards an Abstract Model of User Retention Dynamics

Eli Ben-Sasson, Eden Saig

Brief Announcement: Towards an Abstract Model of User Retention Dynamics

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

Geodesic Obstacle Representation of Graphs

Prosenjit Bose, Paz Carmi, Vida Dujmovic, Saeed Mehrabi, Fabrizio Montecchiani, Pat Morin, Luís Fernando Schultz Xavier da Silveira

Geodesic Obstacle Representation of Graphs

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

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

Gill Barequet, David Eppstein, Michael T. Goodrich, Nil Mamano

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

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

Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

Amy Babay, Michael Dinitz, Zeyu Zhang

Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

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

Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance

Pawel Gawrychowski, Przemyslaw Uznanski

Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance

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

Tighter Connections Between Formula-SAT and Shaving Logs

Amir Abboud, Karl Bringmann

Tighter Connections Between Formula-SAT and Shaving Logs

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

On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings

Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul

On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings

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

Noise-Tolerant Testing of High Entanglement of Formation

Rotem Arnon Friedman, Henry Yuen

Noise-Tolerant Testing of High Entanglement of Formation

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

Brief Announcement: Give Me Some Slack: Efficient Network Measurements

Ran Ben-Basat, Gil Einziger, Roy Friedman

Brief Announcement: Give Me Some Slack: Efficient Network Measurements

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

Load Thresholds for Cuckoo Hashing with Overlapping Blocks

Stefan Walzer

Load Thresholds for Cuckoo Hashing with Overlapping Blocks

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

On the Complexity of Infinite Advice Strings

Gaëtan Douéneau-Tabot

On the Complexity of Infinite Advice Strings

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

Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

Ran Duan, Kaifeng Lyu, Yuanhang Xie

Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

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

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

Martin Koutecký, Asaf Levin, Shmuel Onn

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

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

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier

Moses Charikar, Shay Solomon

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier

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

Spectrally Robust Graph Isomorphism

Alexandra Kolla, Ioannis Koutis, Vivek Madan, Ali Kemal Sinop

Spectrally Robust Graph Isomorphism

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

Stabilizing Weighted Graphs

Zhuan Khye Koh, Laura Sanità

Stabilizing Weighted Graphs

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

Privacy Preserving Clustering with Constraints

Clemens Rösner, Melanie Schmidt

Privacy Preserving Clustering with Constraints

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

Binary Reachability of Timed Pushdown Automata via Quantifier Elimination and Cyclic Order Atoms

Lorenzo Clemente, Slawomir Lasota

Binary Reachability of Timed Pushdown Automata via Quantifier Elimination and Cyclic Order Atoms

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

On the Identity Problem for the Special Linear Group and the Heisenberg Group

Sang-Ki Ko, Reino Niskanen, Igor Potapov

On the Identity Problem for the Special Linear Group and the Heisenberg Group

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

Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations

Dariusz R. Kowalski, Miguel A. Mosteiro

Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations

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

Consistent Distributed Memory Services: Resilience and Efficiency (Invited Paper)

Theophanis Hadjistasi, Alexander A. Schwarzmann

Consistent Distributed Memory Services: Resilience and Efficiency (Invited Paper)

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

Brief Announcement: Zero-Knowledge Protocols for Search Problems

Ben Berger, Zvika Brakerski

Brief Announcement: Zero-Knowledge Protocols for Search Problems

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

Non-Preemptive Flow-Time Minimization via Rejections

Anupam Gupta, Amit Kumar, Jason Li

Non-Preemptive Flow-Time Minimization via Rejections

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

Sample-Optimal Identity Testing with High Probability

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

Sample-Optimal Identity Testing with High Probability

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

On the Complexity of Sampling Vertices Uniformly from a Graph

Flavio Chierichetti, Shahrzad Haddadan

On the Complexity of Sampling Vertices Uniformly from a Graph

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

Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition

L. Sunil Chandran, Yun Kuen Cheung, Davis Issac

Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition

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

The Unfortunate-Flow Problem

Orna Kupferman, Gal Vardi

The Unfortunate-Flow Problem

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

Aperiodic Points in Z2-subshifts

Anaël Grandjean, Benjamin Hellouin de Menibus, Pascal Vanier

Aperiodic Points in Z2-subshifts

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

The Price of Stability of Weighted Congestion Games

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Paul G. Spirakis

The Price of Stability of Weighted Congestion Games

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

Reducing CMSO Model Checking to Highly Connected Graphs

Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi

Reducing CMSO Model Checking to Highly Connected Graphs

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

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

Ran Duan, Hanlin Ren

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

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

Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry

Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

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

An Operational Characterization of Mutual Information in Algorithmic Information Theory

Andrei E. Romashchenko, Marius Zimand

An Operational Characterization of Mutual Information in Algorithmic Information Theory

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

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median

Deeparnab Chakrabarty, Chaitanya Swamy

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median

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

Eigenvector Computation and Community Detection in Asynchronous Gossip Models

Frederik Mallmann-Trenn, Cameron Musco, Christopher Musco

Eigenvector Computation and Community Detection in Asynchronous Gossip Models

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

A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity

Tasuku Soma, Yuichi Yoshida

A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity

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

A Note on Two-Colorability of Nonuniform Hypergraphs

Lech Duraj, Grzegorz Gutowski, Jakub Kozik

A Note on Two-Colorability of Nonuniform Hypergraphs

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

Uniformization Problems for Synchronizations of Automatic Relations on Words

Sarah Winter

Uniformization Problems for Synchronizations of Automatic Relations on Words

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

Union of Hypercubes and 3D Minkowski Sums with Random Sizes

Pankaj K. Agarwal, Haim Kaplan, Micha Sharir

Union of Hypercubes and 3D Minkowski Sums with Random Sizes

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

Towards Blackbox Identity Testing of Log-Variate Circuits

Michael A. Forbes, Sumanta Ghosh, Nitin Saxena

Towards Blackbox Identity Testing of Log-Variate Circuits

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

Congestion-Free Rerouting of Flows on DAGs

Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, Sebastian Wiederrecht

Congestion-Free Rerouting of Flows on DAGs

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

When is Containment Decidable for Probabilistic Automata?

Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, Filip Mazowiecki, Guillermo A. Pérez, James Worrell

When is Containment Decidable for Probabilistic Automata?

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

Spanning Trees With Edge Conflicts and Wireless Connectivity

Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan

Spanning Trees With Edge Conflicts and Wireless Connectivity

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

An Exponential Separation Between MA and AM Proofs of Proximity

Tom Gur, Yang P. Liu, Ron D. Rothblum

An Exponential Separation Between MA and AM Proofs of Proximity

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

Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

Anand Louis, Rakesh Venkat

Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

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

Lower Bounds by Algorithm Design: A Progress Report (Invited Paper)

Richard Ryan Williams

Lower Bounds by Algorithm Design: A Progress Report (Invited Paper)

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

Costs and Rewards in Priced Timed Automata

Martin Fränzle, Mahsa Shirmohammadi, Mani Swaminathan, James Worrell

Costs and Rewards in Priced Timed Automata

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

Reachability Switching Games

John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani

Reachability Switching Games

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

Sparsity - an Algorithmic Perspective (Invited Paper)

Jaroslav Nesetril

Sparsity - an Algorithmic Perspective (Invited Paper)

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

New Approximation Algorithms for (1, 2)-TSP

Anna Adamaszek, Matthias Mnich, Katarzyna Paluch

New Approximation Algorithms for (1, 2)-TSP

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

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

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

Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC

Navneet Agarwal, Sanat Anand, Manoj Prabhakaran

Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC

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

Topological Sorting with Regular Constraints

Antoine Amarilli, Charles Paperman

Topological Sorting with Regular Constraints

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

Faster Algorithms for Integer Programs with Block Structure

Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein

Faster Algorithms for Integer Programs with Block Structure

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

Fast Reed-Solomon Interactive Oracle Proofs of Proximity

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

Fast Reed-Solomon Interactive Oracle Proofs of Proximity

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

Optimal Hashing in External Memory

Alexander Conway, Martin Farach-Colton, Philip Shilane

Optimal Hashing in External Memory

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

Resynchronizing Classes of Word Relations

María Emilia Descotte, Diego Figueira, Gabriele Puppis

Resynchronizing Classes of Word Relations

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

Greedy Algorithms for Online Survivable Network Design

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

Greedy Algorithms for Online Survivable Network Design

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

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas

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

An Improved Isomorphism Test for Bounded-Tree-Width Graphs

Martin Grohe, Daniel Neuen, Pascal Schweitzer, Daniel Wiebking

An Improved Isomorphism Test for Bounded-Tree-Width Graphs

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

Generic Single Edge Fault Tolerant Exact Distance Oracle

Manoj Gupta, Aditi Singh

Generic Single Edge Fault Tolerant Exact Distance Oracle

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

O-Minimal Invariants for Linear Loops

Shaull Almagor, Dmitry Chistikov, Joël Ouaknine, James Worrell

O-Minimal Invariants for Linear Loops

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

A Complete Dichotomy for Complex-Valued Holant^c

Miriam Backens

A Complete Dichotomy for Complex-Valued Holant^c

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

Finding Cliques in Social Networks: A New Distribution-Free Model

Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, Nicole Wein

Finding Cliques in Social Networks: A New Distribution-Free Model

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

Brief Announcement: Approximation Schemes for Geometric Coverage Problems

Steven Chaplick, Minati De, Alexander Ravsky, Joachim Spoerhase

Brief Announcement: Approximation Schemes for Geometric Coverage Problems

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

Ranking with Fairness Constraints

L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi

Ranking with Fairness Constraints

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

Revisiting Frequency Moment Estimation in Random Order Streams

Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang

Revisiting Frequency Moment Estimation in Random Order Streams

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

Proportional Approval Voting, Harmonic k-median, and Negative Association

Jaroslaw Byrka, Piotr Skowron, Krzysztof Sornat

Proportional Approval Voting, Harmonic k-median, and Negative Association

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

Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration

Rafail Ostrovsky, Yuval Rabani, Arman Yousefi

Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration

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

(Delta+1) Coloring in the Congested Clique Model

Merav Parter

(Delta+1) Coloring in the Congested Clique Model

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

Reachability and Distances under Multiple Changes

Samir Datta, Anish Mukherjee, Nils Vortmeier, Thomas Zeume

Reachability and Distances under Multiple Changes

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

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Achim Blumensath, Felix Wolf

Bisimulation Invariant Monadic-Second Order Logic in the Finite

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

Finding Branch-Decompositions of Matroids, Hypergraphs, and More

Jisu Jeong, Eun Jung Kim, Sang-il Oum

Finding Branch-Decompositions of Matroids, Hypergraphs, and More

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

Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS

Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, Meirav Zehavi

Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS

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

Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions

Bernhard Haeupler, Amirbehshad Shahrasbi, Ellen Vitercik

Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions

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

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

Ran Duan, Yong Gu, Le Zhang

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

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

Lovász Meets Weisfeiler and Leman

Holger Dell, Martin Grohe, Gaurav Rattan

Lovász Meets Weisfeiler and Leman

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

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

Heng Guo, Mark Jerrum

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

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

First-Order Interpretations of Bounded Expansion Classes

Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

First-Order Interpretations of Bounded Expansion Classes

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

A Centralized Local Algorithm for the Sparse Spanning Graph Problem

Christoph Lenzen, Reut Levi

A Centralized Local Algorithm for the Sparse Spanning Graph Problem

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

Generalized Center Problems with Outliers

Deeparnab Chakrabarty, Maryam Negahbani

Generalized Center Problems with Outliers

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

Edit Distance between Unrooted Trees in Cubic Time

Bartlomiej Dudek, Pawel Gawrychowski

Edit Distance between Unrooted Trees in Cubic Time

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

How Hard Is It to Satisfy (Almost) All Roommates?

Jiehua Chen, Danny Hermelin, Manuel Sorge, Harel Yedidsion

How Hard Is It to Satisfy (Almost) All Roommates?

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

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

Piotr Sankowski

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

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

Uniform Mixed Equilibria in Network Congestion Games with Link Failures

Vittorio Bilò, Luca Moscardelli, Cosimo Vinci

Uniform Mixed Equilibria in Network Congestion Games with Link Failures

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

Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes

Zdenek Dvorák, Ken-ichi Kawarabayashi

Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes

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

Unambiguous Languages Exhaust the Index Hierarchy

Michal Skrzypczak

Unambiguous Languages Exhaust the Index Hierarchy

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

Approximate Sparse Linear Regression

Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi

Approximate Sparse Linear Regression

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

ARRIVAL: Next Stop in CLS

Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, Veronika Slívová

ARRIVAL: Next Stop in CLS

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

A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error

Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, Maximilian Wötzel

A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error

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

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

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

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

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