research
∙
03/29/2023
Training Neural Networks is NP-Hard in Fixed Dimension
We study the parameterized complexity of training two-layer neural netwo...
share
research
∙
10/28/2022
Terrain-like Graphs and the Median Genocchi Numbers
A graph with vertex set {1,…,n} is terrain-like if, for any edge pair {a...
research
∙
06/29/2022
There and Back Again: On Applying Data Reduction Rules by Undoing Others
Data reduction rules are an established method in the algorithmic toolbo...
research
∙
04/06/2022
Disentangling the Computational Complexity of Network Untangling
We study the network untangling problem introduced by Rozenshtein, Tatti...
research
∙
12/06/2021
Modification-Fair Cluster Editing
The classic Cluster Editing problem (also known as Correlation Clusterin...
research
∙
05/18/2021
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Understanding the computational complexity of training simple neural net...
research
∙
05/13/2021
Equilibria in Schelling Games: Computational Complexity and Robustness
In the simplest game-theoretic formulation of Schelling's model of segre...
research
∙
05/12/2021
Two Influence Maximization Games on Graphs Made Temporal
To address the dynamic nature of real-world networks, we generalize comp...
research
∙
02/12/2020
Complexity of Combinatorial Matrix Completion With Diameter Constraints
We thoroughly study a novel and still basic combinatorial matrix complet...
research
∙
02/04/2020
Faster Binary Mean Computation Under Dynamic Time Warping
Many consensus string problems are based on Hamming distance. We replace...
research
∙
02/03/2020
Parameterized Algorithms for Matrix Completion With Radius Constraints
Considering matrices with missing entries, we study NP-hard matrix compl...
research
∙
11/12/2019
Terrain Visibility Graphs and Cyclic Polytope Triangulations
We prove a bijection between the triangulations of the 3-dimensional cyc...
research
∙
09/30/2019
An Average-Compress Algorithm for the Sample Mean Problem under Dynamic Time Warping
Computing a sample mean of time series under dynamic time warping (DTW) ...
research
∙
05/10/2019
Good Things Come to Those Who Swap Objects on Paths
We study a simple exchange market, introduced by Gourvés, Lesca and Wilc...
research
∙
04/18/2019
Advancing Through Terrains
We study terrain visibility graphs, a well-known graph class closely rel...
research
∙
03/07/2019
Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
Dynamic Time Warping (DTW) is a well-known similarity measure for time s...
research
∙
10/15/2018
Comparing Temporal Graphs Using Dynamic Time Warping
The connections within many real-world networks change over time. Thus, ...
research
∙
04/09/2018
Hardness of Consensus Problems for Circular Strings and Time Series Averaging
Consensus problems for strings and sequences appear in numerous applicat...
research
∙
11/06/2017