Quantum PCP Conjecture - Summer 2020

Welcome to the summer reading group on the quantum PCP conjecture!

This reading group is mainly inspired by: Prof. Vidick's seminar around the quantum PCP conjecture.

For comments or if you would like to present, please send to (islam at bu dot edu).

• Meeting Time: Every Friday 11 am - 12:30 PM (eastern time)
• Zoom Info: Meeting ID: 947 3899 9935 ; Password: 568255
• Mailing List: Sign-up
• Piazza (will host resources, discussions, and recordings of talks): access code: "quantum-is-spooky" without quotation marks
• Slack channel available please email to join.

Date	Topic	Speaker	Plan	Notes
July 10th	1. Introduction & Classical PCP Theorem	Islam Faisal	(show)	See Piazza for resources.
July 17th	2. Exponential-Sized PCPs and Games PCP	Islam Faisal	(show)	See Piazza for resources.
July 24th	3. Dinur's Gap Amplification Lemma	Islam Faisal	(show)	See Piazza for resources.
August 7th	4. Intro to quantum computation and its complexity classes (Part I)	Stephen Fenner	(show)	See Piazza for resources.
August 14th	5. Intro to quantum computation and its complexity classes (Part II)	Stephen Fenner	(show)	See Piazza for resources.
August 28th	6. Multiplayer games and the quantum games PCP conjecture	Mark Bun	(show)	See Piazza for resources.

References:

[ALM+92] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM 45, 3, 501–555.

[AB] Sanjeev Arora and Boaz Barak. 2009. Computational complexity: a modern approach. Cambridge University Press.

HTML Template from: BUNTES