# A Bridge between Polynomial Optimization and Games with Imperfect Recall

arXiv: https://arxiv.org/abs/2002.09941 · HTML: https://mlsanity.com/paper/2002.09941/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2020.

## Built on by (most cited first, 4 of 4)

- [The Computational Complexity of Single-Player Imperfect-Recall Games](https://mlsanity.com/paper/2305.17805/) (2023)
- [Imperfect-Recall Games: Equilibrium Concepts and Their Complexity](https://mlsanity.com/paper/2406.15970/) (2024)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)

## Abstract (arXiv)

We provide several positive and negative complexity results for solving games with imperfect recall. Using a one-to-one correspondence between these games on one side and multivariate polynomials on the other side, we show that solving games with imperfect recall is as hard as solving certain problems of the first order theory of reals. We establish square root sum hardness even for the specific class of A-loss games. On the positive side, we find restrictions on games and strategies motivated by Bridge bidding that give polynomial-time complexity.