ผลต่างระหว่างรุ่นของ "Computational complexity/paper list"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 4 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 9: แถว 9:
 
** Williams. Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Computational Complexity vol. 17, pp 179–219(2008) [https://link.springer.com/article/10.1007/s00037-008-0248-y] or [https://people.csail.mit.edu/rrw/mod-lbs-journal-final.pdf pdf]
 
** Williams. Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Computational Complexity vol. 17, pp 179–219(2008) [https://link.springer.com/article/10.1007/s00037-008-0248-y] or [https://people.csail.mit.edu/rrw/mod-lbs-journal-final.pdf pdf]
 
** (upperbound for specific problems) Lincoln, Andrea & Williams, Virginia & Wang, Joshua & Williams, Richard. (2016). Deterministic Time-Space Tradeoffs for k-SUM. ICALP2016.  [https://theory.stanford.edu/~virgi/ksumtradeoff.pdf pdf] or [https://arxiv.org/abs/1605.07285 arxiv]
 
** (upperbound for specific problems) Lincoln, Andrea & Williams, Virginia & Wang, Joshua & Williams, Richard. (2016). Deterministic Time-Space Tradeoffs for k-SUM. ICALP2016.  [https://theory.stanford.edu/~virgi/ksumtradeoff.pdf pdf] or [https://arxiv.org/abs/1605.07285 arxiv]
 +
* Derandomization
 +
** Nisan & Wigderson, Hardness vs randomness, JCSS, 1994. [https://www.sciencedirect.com/science/article/pii/S0022000005800431]
 +
* Zero knowledge proofs
 +
** Goldwasser, Micali & Rackoff. The knowledge complexity of interactive proof-systems. STOC'85. [https://dl.acm.org/doi/10.1145/22145.22178] Journal version: [https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf pdf]
 +
** Goldreich, Micali, Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. JACM'91 [https://dl.acm.org/doi/10.1145/116825.116852] [https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Proofs_That_Yield_Nothing_But_Their_Validity_or_All_Languages_in_NP_Have_Zero-Knowledge_Proof_Systems.pdf pdf]
 +
* PCP & Property Test
 +
** Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. STOC 1990: 73-83
 +
** Venkatesan Guruswami, Jakub Opršal, Sai Sandeep: Revisiting Alphabet Reduction in Dinur’s PCP. APPROX 2020
 +
** Johan Håstad: Some optimal inapproximability results, STOC'97, J.ACM'01

รุ่นแก้ไขปัจจุบันเมื่อ 03:39, 14 พฤษภาคม 2564

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

  • 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
    • Venkatesan Guruswami, Jakub Opršal, Sai Sandeep: Revisiting Alphabet Reduction in Dinur’s PCP. APPROX 2020
    • Johan Håstad: Some optimal inapproximability results, STOC'97, J.ACM'01
ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=Computational_complexity/paper_list&oldid=59166"