Synchronous linear constraint system games
From MaRDI portal
Abstract: Synchronous linear constraint system games are nonlocal games that verify whether or not two players share a solution to a given system of equations. Two algebraic objects associated to these games encode information about the existence of perfect strategies. They are called the game algebra and the solution group. Here we show that these objects are essentially the same, i.e., that the game algebra is a suitable quotient of the group algebra of the solution group. We also demonstrate that linear constraint system games are equivalent to graph isomorphism games on a pair of graphs parameterized by the linear system.
Recommendations
- A synchronous game for binary constraint systems
- Concurrent reachability games
- scientific article; zbMATH DE number 7650328
- Games of constraints for complex systems
- Simulation of concurrent games
- Games with linear conjectures about system parameters
- Timed Concurrent Game Structures
- Products of synchronous games
- Multilinear games
Cites work
- A synchronous game for binary constraint systems
- Algebras, synchronous games, and chromatic numbers of graphs
- Bigalois extensions and the graph isomorphism game
- Characterization of binary constraint system games
- Estimating quantum chromatic numbers
- Perfect commuting-operator strategies for linear system games
- Perfect strategies for non-local games
- Quantum and non-signalling graph isomorphisms
- Quantum graph homomorphisms via operator systems
Cited in
(14)- Algebras, synchronous games, and chromatic numbers of graphs
- Synchronicity for quantum non-local games
- Bisynchronous games and factorizable maps
- Perfect commuting-operator strategies for linear system games
- A synchronous game for binary constraint systems
- Quantum semigroups from synchronous games
- Products of synchronous games
- \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
- Noncommutative nullstellensätze and perfect games
- Universality of graph homomorphism games and the quantum coloring problem
- Rounding near-optimal quantum strategies for nonlocal games to strategies using a maximally entangled state
- Satisfiability problems and algebras of Boolean constraint system games
- Solution group representations as quantum symmetries of graphs
- Approximate quantum 3-colorings of graphs and the quantum max 3-cut problem
This page was built for publication: Synchronous linear constraint system games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859115)
