New answers tagged pcp
3
votes
Accepted
From CHSH inequality to CHSH game
I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games ...
Top 50 recent answers are included
Related Tags
pcp × 51cc.complexity-theory × 37
approximation-hardness × 11
unique-games-conjecture × 5
complexity-classes × 4
interactive-proofs × 4
reference-request × 3
quantum-computing × 3
coding-theory × 3
polynomials × 3
np-hardness × 2
sat × 2
algebra × 2
csp × 2
nexp × 2
ds.algorithms × 1
lo.logic × 1
approximation-algorithms × 1
boolean-functions × 1
reductions × 1
graph-isomorphism × 1
quantum-information × 1
np × 1
gt.game-theory × 1
oracles × 1