Computational complexity/paper list

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

ด้านล่างเป็นรายการงานวิจัยสำหรับเขียนสรุปส่ง

  • Space Complexity
    • Omer Reingold, Undirected connectivity in log-space, JACM 2008. [1]
      • notes: [2] by Emanuele Vioa
  • Polynomial hierarchy
    • Christopher Umans, Hardness of Approximating Minimization Problems, FOCS'99. [3] .ps
  • Time-space trade-off
    • Williams. Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Computational Complexity vol. 17, pp 179–219(2008) [4] or pdf
    • (upperbound for specific problems) Lincoln, Andrea & Williams, Virginia & Wang, Joshua & Williams, Richard. (2016). Deterministic Time-Space Tradeoffs for k-SUM. ICALP2016. pdf or arxiv
  • Derandomization
    • Nisan & Wigderson, Hardness vs randomness, JCSS, 1994. [5]
  • Zero knowledge proofs
    • Goldwasser, Micali & Rackoff. The knowledge complexity of interactive proof-systems. STOC'85. [6] Journal version: pdf
    • Goldreich, Micali, Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. JACM'91 [7] pdf
  • PCP & Property Test
    • Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. STOC 1990: 73-83
    • Jaikumar Radhakrishnan, Madhu Sudan: On Dinur’s Proof of the PCP Theorem. APPROX 2021
    • Johan Håstad: Some optimal inapproximability results