30 citations · 69 across the 13 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
math.OC2024
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…
cs.GT2024
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…