1 citations · 2 across the 9 of their papers we have counts for
12 papers
Counting Vanishing Matrix-Vector Products
Cornelius Brand, Viktoriia Korchemna, Michael Skotnica +1
Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let…
Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
Cornelius Brand, Robert Ganian, Sebastian Röder +1
In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly , where the number of bend…
A Parameterized Theory of PAC Learning
Cornelius Brand, Robert Ganian, Kirill Simonov
Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the clas…
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
Cornelius Brand, Esra Ceylan, Christian Hatschka +2
Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by tre…
Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises
Cornelius Brand, Martin Koutecký, Alexandra Lassota +1
An influential 1990 paper of Hochbaum and Shanthikumar made it common wisdom that "convex separable optimization is not much harder than linear optimization" [JACM 1990]. We exhibi…
A Note on the Approximability of Deepest-Descent Circuit Steps
Steffen Borgwardt, Cornelius Brand, Andreas Emil Feldmann +1
Linear programs (LPs) can be solved by polynomially many moves along the circuit direction improving the objective the most, so-called deepest-descent steps (dd-steps). Computing t…
An Algorithmic Method of Partial Derivatives
Cornelius Brand, Kevin Pratt
We study the following problem and its applications: given a homogeneous degree- polynomial as an arithmetic circuit, and a matrix whose entries are homogen…
Parameterized Algorithms for MILPs with Small Treedepth
Cornelius Brand, Martin Koutecký, Sebastian Ordyniak
Solving (mixed) integer linear programs, (M)ILPs for short, is a fundamental optimization task. While hard in general, recent years have brought about vast progress for solving str…
Extensor-Coding
Cornelius Brand, Holger Dell, Thore Husfeldt
We devise an algorithm that approximately computes the number of paths of length in a given directed graph with vertices up to a multiplicative error of …
Parameterized counting of trees, forests and matroid bases
Cornelius Brand, Marc Roth
We investigate the complexity of counting trees, forests and bases of matroids from a parameterized point of view. It turns out that the problems of computing the number of trees a…
Fine-grained dichotomies for the Tutte plane and Boolean #CSP
Cornelius Brand, Holger Dell, Marc Roth
Jaeger, Vertigan, and Welsh [15] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the rema…
On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
Cornelius Brand, Michael Sagraloff
Given a zero-dimensional polynomial system consisting of n integer polynomials in n variables, we propose a certified and complete method to compute all complex solutions of the sy…