30 citations · 69 across the 13 of their papers we have counts for
18 papers
Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph
Bruno Loff, Mateusz Skomra
Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algo…
Duality attainment and strict feasibility of the generalized moment problem and its relaxations
Sami Halaseh, Victor Magron, Mateusz Skomra
The generalized moment problem (GMP) is an infinite dimensional linear problem over the cone of finite nonnegative Borel measures. When a GMP instance involves finitely many polyno…
Finite Convergence of the Moment-SOS Hierarchy on the Product of Spheres
Sami Halaseh, Victor Magron, Mateusz Skomra
We study the polynomial optimization problem of minimizing a multihomogeneous polynomial over the product of spheres. This polynomial optimization problem models the tensor optimiz…
Cycle Patterns and Mean Payoff Games
Georg Loho, Matthew Maat, Mateusz Skomra
We introduce the concept of a \emph{cycle pattern} for directed graphs as functions from the set of cycles to the set . The key example for such a pattern is derived fro…
Reducing Stochastic Games to Semidefinite Program Feasibility
Manuel Bodirsky, Georg Loho, Mateusz Skomra
We present a polynomial-time reduction from max-plus-average constraints to the feasibility problem for semidefinite programs. This shows that Condon's simple stochastic games, sto…
Smoothed analysis of deterministic discounted and mean-payoff games
Bruno Loff, Mateusz Skomra
We devise a policy-iteration algorithm for deterministic two-player discounted and mean-payoff games, that runs in polynomial time with high probability, on any input where each pa…
Games on Graphs: From Logic and Automata to Algorithms
Nathanaël Fijalkow, C. Aiswarya, Guy Avni +22
The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared…
Signed tropical halfspaces and convexity
Georg Loho, Mateusz Skomra
We extend the fundamentals for tropical convexity beyond the tropically positive orthant expanding the theory developed by Loho and Végh (ITCS 2020). We study two notions of convex…
Universal Complexity Bounds Based on Value Iteration for Stochastic Mean Payoff Games and Entropy Games
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz +1
We develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on a…
Optimal bounds for bit-sizes of stationary distributions in finite Markov chains
Mateusz Skomra
An irreducible stochastic matrix with rational entries has a stationary distribution given by a vector of rational numbers. We give an upper bound on the lowest common denominator…
Derandomization and absolute reconstruction for sums of powers of linear forms
Pascal Koiran, Mateusz Skomra
We study the decomposition of multivariate polynomials as sums of powers of linear forms. As one of our main results we give an algorithm for the following problem: given a homogen…
Intersection multiplicity of a sparse curve and a low-degree curve
Pascal Koiran, Mateusz Skomra
Let be a polynomial of degree and let be a polynomial with monomials. We want to estimate the maximal multiplicit…
Convexly independent subsets of Minkowski sums of convex polygons
Mateusz Skomra, Stéphan Thomassé
We show that there exist convex -gons and such that the largest convex polygon in the Minkowski sum has size . This matches an upper bound of Tiwary.
Individual Security and Network Design with Malicious Nodes
Tomasz Janus, Mateusz Skomra, Marcin Dziubiński
Networks are beneficial to those being connected but can also be used as carriers of contagious hostile attacks. These attacks are often facilitated by exploiting corrupt network u…
Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz +1
Semidefinite programming can be considered over any real closed field, including fields of Puiseux series equipped with their nonarchimedean valuation. Nonarchimedean semidefinite…
The tropical analogue of the Helton-Nie conjecture is true
Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra
Helton and Nie conjectured that every convex semialgebraic set over the field of real numbers can be written as the projection of a spectrahedron. Recently, Scheiderer disproved th…
Tropical spectrahedra
Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra
We introduce tropical spectrahedra, defined as the images by the nonarchimedean valuation of spectrahedra over the field of real Puiseux series. We provide an explicit polyhedral c…
Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra
A general issue in computational optimization is to develop combinatorial algorithms for semidefinite programming. We address this issue when the base field is nonarchimedean. We p…