3 papers
cs.GT2026
The Complexity of Two-Team Polymatrix Games with Independent Adversaries
Alexandros Hollender, Gilbert Maystre, Sai Ganesh Nagarajan
Adversarial multiplayer games are an important object of study in multiagent learning. In particular, polymatrix zero-sum games are a multiplayer setting where Nash equilibria are…
cs.CC2025
Direct Sums for Parity Decision Trees
Tyler Besselman, Mika Göös, Siyao Guo +2
Direct sum theorems state that the cost of solving instances of a problem is at least times the cost of solving a single instance. We prove the first such results in th…
cs.CC2024
Supercritical Tradeoffs for Monotone Circuits
Mika Göös, Gilbert Maystre, Kilian Risse +1
We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the fi…