cover_image

【论文速递】ITCS'24（理论密码学、计算复杂性理论、理论量子计算、理论机器学习）

Kurt Pan XPTY
2024年04月26日 17:47
  • 超链接🔗可点击最下面👇「阅读原文」查看。（We cannot imagine a so-called "Internet" that does not have hyperlinks.）

http://itcs-conf.org/itcs24/itcs24-program.html

  • One-Way Functions vs. TFNP: Simpler and Improved video,  paperLukáš Folwarczný (Czech Academy of Sciences and Charles University), Mika Göös (EPFL), Pavel Hubáček (Czech Academy of Sciences and Charles University), Gilbert Maystre (EPFL) and Weiqiang Yuan (EPFL)

  • Intersection Classes in TFNP and Proof Complexity video, paperYuhao Li (Columbia), William Pires (Columbia) and Robert Robere (McGill)

  • TFNP Intersections through the Lens of Feasible Disjunction video, paperPavel Hubáček (Czech Academy of Sciences and Charles University), Erfan Khaniki (Czech Academy of Sciences and Charles University) and Neil Thapen (Czech Academy of Sciences)

  • Total NP Search Problems with Abundant Solutions video, paperJiawei Li (University of Texas at Austin)

  • Lower Bounds for Planar Arithmetic Circuits video, paperRamya C (Institute of Mathematical Sciences) and Pratik Shastri (Institute of Mathematical Sciences)

  • A VLSI Circuit Model Accounting for Wire Delay video, paperNathaniel Young (Unaffiliated), Ce Jin (MIT) and Ryan Williams (MIT)

  • On Parallel Repetition of PCPs video, paper
    Alessandro Chiesa (EPFL), Ziyi Guan (EPFL) and Burcu Yildiz (EPFL)

  • Quantum Merlin-Arthur and proofs without relative phase video, paperRoozbeh Bassirian (University of Chicago), Bill Fefferman (University of Chicago) and Kunal Marwaha (University of Chicago)

  • Quantum Money from Abelian Group Actions video, paperMark Zhandry (NTT Research)

  • The Space-Time Cost of Purifying Quantum Computations video, paperMark Zhandry (NTT Research)

  • Quantum Pseudoentanglement video, paperScott Aaronson (University of Texas, Austin), Adam Bouland (Stanford University), Bill Fefferman (University of Chicago), Soumik Ghosh (University of Chicago), Umesh Vazirani (University of California, Berkeley), Chenyi Zhang (Stanford University) and Zixin Zhou (Stanford University)

  • Pseudorandom Strings from Pseudorandom Quantum States video, paper
    Prabhanjan Ananth (UC Santa Barbara), Yao-Ting Lin (UC Santa Barbara) and Henry Yuen (Columbia University)

  • Classical Verification of Quantum Learning video, paperMatthias C. Caro (California Institute of Technology, Freie Universität Berlin), Marcel Hinsche (Freie Universität Berlin), Marios Ioannou (Freie Universität Berlin), Alexander Nietner (Freie Universität Berlin) and Ryan Sweke (IBM Quantum)

  • Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle video, paperXingjian Li (Tsinghua University), Qipeng Liu (UCSD), Angelos Pelecanos (UC Berkeley) and Takashi Yamakawa (NTT Social Informatics Laboratories)

  • A Qubit, a Coin, and an Advice String Walk Into a Relational Problem video, paperScott Aaronson (UT Austin/OpenAI), Harry Buhrman (QuSoft/CWI/University of Amsterdam) and William Kretschmer (Simons Institute/UC Berkeley)

  • Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election video, paperRex Fernando (CMU), Yuval Gelles (Hebrew University) and Ilan Komargodski (Hebrew University and NTT Research)

  • On The Black-Box Complexity of Correlation Intractability video, paperNico Dottling (Helmholtz Center for Information Security (CISPA)) and Tamer Mour (Weizmann Institute for Science)

  • Homomorphic Indistinguishability Obfuscation and its Applications video, paperKaartik Bhushan (Indian Institute of Technology, Mumbai), Venkata Koppula (Indian Institute of Technology, Delhi) and Manoj Prabhakaran (Indian Institute of Technology, Mumbai)

  • A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications video, paperKeller Blackwell (Stanford University) and Mary Wootters (Stanford University)

  • Pseudorandom Linear Codes are List-Decodable to Capacity video, paper
    Aaron (Louie) Putterman (Harvard University) and Edward Pyne (MIT)

  • Noisy decoding by shallow circuits with parities: classical and quantum video, paperJop Briet (CWI), Harry Buhrman (CWI, University of Amsterdam), Davi Castro-Silva (CWI) and Niels M. P. Neumann (CWI, TNO)

  • Distributional PAC-Learning from Nisan's Natural Proofs video, paperAri Karchmer (Boston University)

  • Learning Arithmetic Circuits in the Presence of Noise: A General Framework and Applications to Unsupervised Learning video, paper
    Pritam Chandra (Microsoft Research), Ankit Garg (Microsoft Research India), Tanmay Sinha (Microsoft Research), Neeraj Kayal (Microsoft Research) and Kunal Mittal (Princeton University)

  • Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness video, paper
    Iddo Tzameret (Imperial College London) and Lu-Ming Zhang (London School of Economics)

  • The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False video, paper
    Noam Mazor (Cornell Tech) and Rafael Pass (Tel Aviv University & Cornell Tech)

  • Towards Stronger Depth Lower Bounds video, paperGabriel Bathie (DI ENS, PSL Research University, and LaBRI, Université de Bordeaux) and Ryan Williams (MIT)

  • Proving Unsatisfiability with Hitting Formulas video, paper
    Yuval Filmus (Technion - Israel Institute of Technology, Haifa, Israel), Edward A. Hirsch (Ariel University, Ariel, Israel), Artur Riazanov (EPFL, Lausanne, Switzerland), Alexander Smal (Technion - Israel Institute of Technology, Haifa, Israel) and Marc Vinyals (University of Auckland, Auckland, New Zealand)

  • New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification video, paper
    Prantar Ghosh (Georgetown University) and Vihan Shah (University of Waterloo)

  • Extractors for polynomial sources over  video, paper
    Eshan Chattopadhyay (Cornell University), Jesse Goodman (Cornell University) and Mohit Gurumukhani (Cornell University)

  • A Computational Separation Between Quantum No-cloning and No-telegraphing paperBarak Nehoran (Princeton University) and Mark Zhandry (NTT Research & Princeton University)

  • Parity vs. AC0 with quantum preprocessing video, paper
    Joseph Slote (California Institute of Technology)

  • On the complexity of isomorphism problems for tensors, groups, and polynomials under the actions of classical groups video, paper
    Zhili Chen (University of Technology Sydney), Joshua Grochow (Departments of Computer Science and Mathematics, University of Colorado—Boulder, Boulder, CO 80309-0430, United States), Youming Qiao (Center for Quantum Software and Information, University of Technology, Ultimo NSW 2007, Australia), Gang Tang (University of Technology Sydney) and Chuanqi Zhang (University of Technology Sydney)

  • Determinants vs. Algebraic Branching Programs video, paper
    Abhranil Chatterjee (Indian Statistical Institute, Kolkata), Mrinal Kumar (TIFR Bombay) and Ben Lee Volk (Reichman University)

  • Homogeneous algebraic complexity theory and algebraic formulas video, paper
    Pranjal Dutta (School of Computing, National University of Singapore (NUS)), Fulvio Gesmundo (Saarland University), Christian Ikenmeyer (University of Warwick), Gorav Jindal (Max Planck Institute for Software Systems, Saarbrücken) and Vladimir Lysikov (Ruhr University Bochum)