8 papers
Inapproximability of Counting Permutation Patterns
Michal Opler
Detecting and counting copies of permutation patterns are fundamental algorithmic problems, with applications in the analysis of rankings, nonparametric statistics, and property te…
Linear clique-width and modular decomposition
Robert Brignall, Michal Opler, Vincent Vatter
A hereditary class of graphs has bounded clique-width if and only if its prime members do, but this lifting property fails for linear clique-width. We prove that a hereditary class…
Fast and simple multiplication of bounded twin-width matrices
László Kozma, Michal Opler
Matrix multiplication is a fundamental task in almost all computational fields, including machine learning and optimization, computer graphics, signal processing, and graph algorit…
Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma, Michal Opler
Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complex…
Monadic Second-Order Logic of Permutations
VÃt JelÃnek, Michal Opler
Permutations can be viewed as pairs of linear orders, or more formally as models over a signature consisting of two binary relation symbols. This approach was adopted by Albert, Bo…
Compact representations of pattern-avoiding permutations
László Kozma, Michal Opler
Pattern-avoiding permutations are a central object of study in both combinatorics and theoretical computer science. In this paper we design a data structure that can store any size…