A projection game, also called a label-cover instance, consists of a bipartite graph 
,
finite label sets 
and 
, and, for every edge 
, a projection 
. A labeling satisfies 
when the label of 
equals the projection of the label of 
. The value of the game is the largest fraction of edges that
can be satisfied simultaneously.
The projection games conjecture asserts that there is a constant 
such that, for every 
, a satisfiability instance of size 
can be reduced in polynomial
time to a projection game of size 
, alphabet size 
, perfect completeness, and soundness at most
(Moshkovitz 2015). The conjecture is a strengthening of the PCP
theorem.
-Approximating Set-Cover." Theory Comput. 11,
221-235, 2015.