49 citations · 185 across the 18 of their papers we have counts for
25 papers
Fluctuations of Nonlinear Observables in Mean Field Neural Network Training
Arnaud Descours, Geoffrey Lacour
Mean field limits describe the training dynamics of wide neural networks through the evolution of the empirical distribution of their parameters. Although functional central limit…
Continuous Computational Social Choice: A Case Study in Bribery
Martin Koutecký, Nikolaos Melissinos, Tung Anh Vu +1
Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly mode…
Bolzano: Case Studies in LLM-Assisted Mathematical Research
Martin Balko, Jan Grebík, Pavel Hubáček +5
We report new results on eight problems in mathematics and theoretical computer science, produced with the assistance of Bolzano, an open-source multi-agent LLM system. Bolzano orc…
(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
Christoph Hunkenschröder, Martin Koutecký, Asaf Levin +1
We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mat…
Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
Marcin Brianski, Martin Koutecky, Daniel Kral +2
An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix and the n…
A Note on Coloring -free graphs with a
Martin Koutecký
Even-hole-free graphs are a graph class of much interest. Foley et al. [Graphs Comb. 36(1): 125-138 (2020)] have recently studied -free graphs, which form a subcl…
Uniform and Monotone Line Sum Optimization
Martin Koutecky, Shmuel Onn
The {\em line sum optimization problem} asks for a -matrix minimizing the sum of given functions evaluated at its row and column sums. We show that the {\em uniform} problem…
Opinion Diffusion and Campaigning on Society Graphs
Piotr Faliszewski, Rica Gonen, Martin Koutecký +1
We study the effects of campaigning, where the society is partitioned into voter clusters and a diffusion process propagates opinions in a network connecting the clusters. Our mode…
Multitype Integer Monoid Optimization and Applications
Dušan Knop, Martin Koutecký, Asaf Levin +2
Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 19…
Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecky +2
A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree…
An Algorithmic Theory of Integer Programming
Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein +3
We study the general integer programming problem where the number of variables is a variable part of the input. We consider two natural parameters of the constraint matrix :…
Voting and Bribing in Single-Exponential Time
Dušan Knop, Martin Koutecký, Matthias Mnich
We introduce a general problem about bribery in voting systems. In the -Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired…
Approximating Max-Cut under Graph-MSO Constraints
Martin Koutecký, Jon Lee, Viswanath Nagarajan +1
We consider the max-cut and max--cut problems under graph-based constraints. Our approach can handle any constraint specified using monadic second-order (MSO) logic on graphs of…
A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
Martin Koutecký, Asaf Levin, Shmuel Onn
The theory of -fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an -fold integer program (IP) consists of pa…
Evaluating and Tuning n-fold Integer Programming
Kateřina Altmanová, Dušan Knop, Martin Koutecký
In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying the theory of so-called -fold integer program…
A Unifying Framework for Manipulation Problems
Dušan Knop, Martin Koutecký, Matthias Mnich
Manipulation models for electoral systems are a core research theme in social choice theory; they include bribery (unweighted, weighted, swap, shift, ...), control (by adding or de…
Integer Programming in Parameterized Complexity: Three Miniatures
Tomáš Gavenčiak, Dušan Knop, Martin Koutecký
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's…
Approximate Shifted Combinatorial Optimization
Martin Koutecky, Asaf Levin, Syed M. Meesum +1
Shifted combinatorial optimization is a new nonlinear optimization framework, which is a broad extension of standard combinatorial optimization, involving the choice of several fea…
Combinatorial n-fold Integer Programming and Applications
Dušan Knop, Martin Koutecký, Matthias Mnich
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension o…
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
Dušan Knop, Martin Koutecký, Tomáš Masařík +1
This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidt…
Parameterized Shifted Combinatorial Optimization
Jakub Gajarský, Petr Hliněný, Martin Koutecký +1
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feas…
Scheduling meets n-fold Integer Programming
Dušan Knop, Martin Koutecký
Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact…
Extension Complexity, MSO Logic, and Treewidth
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
We consider the convex hull of all satisfying assignments of a given MSO formula on a given graph . We show that there exists an extended formulation of the polytop…
Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems
Jiří Fiala, Tomáš Gavenčiak, Dušan Knop +2
We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neigh…