Overview
Welcome to our reading group dedicated to a broad exploration around Classical and Quantum PCPs (Probabilistically Checkable Proofs). This means that we can effectively discuss most, if not all, areas of TCS (such as codes, expanders, optimization, approximation algorithms, crypto, etc) since the study of PCPs intersect all of them. For instance, we can cover a paper about code constructions, or about area laws (anything that can be seen as broadly related to PCPs).
Tentative Format
We can have usual ~1 hour talks, or, ideally, more intense (and fun ;) ~3 hours gatherings depending on the speaker interests.- First Part (~1 hour): general presentation about the work with context, motivation, and overview of technical results possibly with some simpler proofs.
- Break (~30 minutes): recharge and socialize.
- Second Part (~1 hour + x minutes): present (some of) the technical part and proofs in more detail.
- Final Part (~30- x minutes): more questions, free speculations, and socialization.
Tentative Schedule
A tentative schedule with speakers is given below. Please note that this is under construction. (Students and postdocs have priority over faculty in presenting papers. Email the organizers (or directly talk to us) if you want to present.)
- (02/06) Organizational meeting
- (02/13) Aman Singh
- (02/20) Qizhao Huang
- (02/27) QIP (no reading group)
- (03/06) Arjun Aggarwal
- (03/13) Dagstuhl Seminar (no reading group)
- (03/20) Mehrdad Tahmasbi
- (04/27) Ruta Jawale
- (04/03) K. T.
- (04/10) Bowen Li
- (04/17) Makrand Sinha
- (04/24) Fernando Granha Jeronimo
A List of Papers
You are welcome to present any paper broadly related to our main topic. A (non-exhaustive and under construction) list of papers.
- The Quantum PCP Conjecture survey by Aharonov, Arad, Vidick
- Circuit-to-Hamiltonian from tensor networks and fault tolerance by Anshu, Breuckmann, Nguyen
- Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes by Dinur, Lin, Vidick
- Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier by Hsieh, Lin, Mohanty, O'Donnell and Zhang
- NLTS Hamiltonians from good quantum codes by Anshu, Breuckmann, Nirkhe
- Quasi-Linear Size PCPs with Small Soundness from HDX by Bafna, Minzer, Vyas
- Decoding quantum Tanner codes by Leverrier and Zémor
- Quasi-quantum states and the quasi-quantum PCP theorem by Arad and Santha
- Asymptotically Good Quantum and Locally Testable Classical LDPC Codes by Panteleev and Kalachev
- Maximally Extendable Product Codes are Good Coboundary Expanders by Panteleev and Kalachev
- Good Locally Testable Codes by Dinur, Evra, Livne, Lubotzky and Mozes
- Sparser Abelian High Dimensional Expanders by Dikstein, Liu and Wigderson
- The Detectability Lemma and Quantum Gap Amplification by Aharonov, Arad, Landau and Vazirani
- Ramanujan Property and Edge Universality of Random Regular Graphs by Huang, Mckenzie and Yau
- Transversal non-Clifford gates for quantum LDPC codes on sheaves by Lin
- Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes by Golowich and Lin
- Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs by Dikstein, Dinur and Lubotzky
- Near Optimal Alphabet-Soundness Tradeoff PCPs by Minzer and Zheng
- Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares by Hopkins and Lin
- Decoding Quasi-Cyclic Quantum LDPC Codes by Golowich and Guruswami
- Quantum LDPC Codes of Almost Linear Distance via Homological Products by Golowich and Guruswami
- Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds by Chen and Zhang
- AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets by Alrabiah, Guruswami, Li
- Locality vs Quantum Codes by Dai and Li
- The complexity of quantum spin systems on a two-dimensional square lattice by Oliveira and Terhal
- A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians by Landau, Vazirani and Vidick
- An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games by Ellis, Kindler and Lifshitz
- List-Decoding Capacity Implies Capacity on the q-ary Symmetric Channel by Pernice, Sprumont, Wootters
- Subexponential algorithms for unique games and related problems by Arora, Barak, and Steurer