33 citations · 65 across the 7 of their papers we have counts for
8 papers
Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs
Dmitry Chistikov, Matthias Englert, Ranko Lazic
We prove that, for the fundamental regression task of learning a single neuron, training a one-hidden layer ReLU network of any width by gradient flow from a small initialisation c…
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
Matthias Englert, Heiko Röglin, Berthold Vöcking
2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on real world Euclidean instances both with respect to running t…
Adversarial Reprogramming Revisited
Matthias Englert, Ranko Lazic
Adversarial reprogramming, introduced by Elsayed, Goodfellow, and Sohl-Dickstein, seeks to repurpose a neural network to perform a different task, by manipulating its input without…
Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
Matthias Englert, Nicolaos Matsakis, Pavel Veselý
In the Shortest Superstring problem, we are given a set of strings and we are asking for a common superstring, which has the minimum number of characters. The Shortest Superstring…
Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis +1
We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output…
Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
Matthias Englert, Ranko Lazić, Patrick Totzke
Blondin et al. showed at LICS 2015 that two-dimensional vector addition systems with states have reachability witnesses of length exponential in the number of states and polynomial…
Logical Limitations to Machine Ethics with Consequences to Lethal Autonomous Weapons
Matthias Englert, Sandra Siebert, Martin Ziegler
Lethal Autonomous Weapons promise to revolutionize warfare -- and raise a multitude of ethical and legal questions. It has thus been suggested to program values and principles of c…
Vertex Sparsifiers: New Results from Old Techniques
Matthias Englert, Anupam Gupta, Robert Krauthgamer +3
Given a capacitated graph and a set of terminals , how should we produce a graph only on the terminals so that every (multicommodity) flow betwee…