Anshu, AnuragHøyer, PeterMhalla, MehdiPerdrix, Simon2024-02-072020-02Anshu, Anurag, Peter Høyer, Mehdi Mhalla, Simon Perdrix. "Contextuality in multipartite pseudo-telepathy graph games." Journal of Computer and System Sciences 107 (2020): 156-165. DOI: 10.1016/j.jcss.2019.06.005978366255750197836625575180022-0000https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37377723Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures that generate equivalent scenarios. We introduce a new tool called multipartiteness width to investigate which scenarios are harder to decompose and show that there exist graphs generating scenarios with a linear multipartiteness width.en-USApplied MathematicsComputational Theory and MathematicsComputer Networks and CommunicationsTheoretical Computer ScienceJournal Article2024-02-0710.1016/j.jcss.2019.06.005