【論文速遞】ITCS'25（交互式證明、量子證明、折疊、學習理論和混淆、列表解碼）
https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-325
Sparsity Lower Bounds for Probabilistic Polynomials https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.3 Josh Alman, Arkadev Chattopadhyay, and Ryan Williams Doubly Sub-Linear Interactive Proofs of Proximity https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.6 Noga Amir, Oded Goldreich, and Guy N. Rothblum Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.7 Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen Single-Round Proofs of Quantumness from Knowledge Assumptions https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.8 Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, and Tony Metger The Local Hamiltonian Problem for Quasi-Quantum States: A Toy Model for the Quantum PCP Conjecture https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.9 Itai Arad and Miklos Santha Accumulation Without Homomorphism https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.23 Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, and William Wang Backdoor Defense, Learnability and Obfuscation https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.38 Paul Christiano, Jacob Hilton, Victor Lecomte, and Mark Xu Error Correction for Message Streams https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.59 Meghal Gupta and Rachel Yun Zhang List Decoding Bounds for Binary Codes with Noiseless Feedback https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.60 Meghal Gupta and Rachel Yun Zhang Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.82 Nicolas Resch, Chen Yuan, and Yihan Zhang Toward the Impossibility of Perfect Complete Quantum PKE from OWFs https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.71 Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu On White-Box Learning and Public-Key Encryption https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.73 Yanyi Liu, Noam Mazor, and Rafael Pass A Quantum Unique Games Conjecture https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.76 Hamoon Mousavi and Taro Spirig Toward Separating QMA from QCMA with a Classical Oracle https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.95 Mark Zhandry