You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
(=_=) (Apr 26 2020 at 08:42):Jalex Stark said:
I have a category of "games" and "simulations" such that the product and coproduct in this category correspond to some of the constructions in the CS literature.
What I'm curious about is how this differs from the category of "open games" that Jules Hedges defined. The most recent iteration of that is here, which Jules has characterised as generalising from lenses to optics.
Jules Hedges (Apr 26 2020 at 11:01):It's always safe to start out assuming that something from game semantics has no relation to something from game theory. It might do, but that would be a bonus
(=_=) (Apr 27 2020 at 01:26):Jules Hedges said:
It's always safe to start out assuming that something from game semantics has no relation to something from game theory. It might do, but that would be a bonus
Sorry, I'm confused by this statement. Could you clarify how the definition of MIP* is game-semantic but not game-theoretic in nature? Per the definitions in the Complexity Zoo:
MIP*: MIP With Quantum Provers
Same as MIP, except that the provers can share arbitrarily many entangled qubits. The verifier is classical, as are all messages between the provers and verifier.
MIP: Multi-Prover Interactive Proof
Same as IP, except that now the verifier can exchange messages with many provers, not just one. The provers cannot communicate with each other during the execution of the protocol, so the verifier can "cross-check" their assertions (as with suspects in separate interrogation rooms).
IP: Interactive Proof Systems
The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:
If the answer is "yes," the prover must be able to behave in such a way that the verifier accepts with probability at least 2/3 (over the choice of the verifier's random bits).
If the answer is "no," then however the prover behaves the verifier must reject with probability at least 2/3.
Jules Hedges (Apr 27 2020 at 13:43):Yes, anything where you have 2 players and you break the symmetry between them by considering one the "verifier" and one the "falsifier" is game semantics
Jules Hedges (Apr 27 2020 at 13:44):An example of a complexity class that is game-theoretic in nature is NASH, which contains the problem of approximating Brouwer -fixpoints
(=_=) (Apr 27 2020 at 14:08):Seems like there's a bonus.