ผลต่างระหว่างรุ่นของ "Computational complexity/paper list"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Bundit (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 5 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน) | |||
| แถว 1: | แถว 1: | ||
ด้านล่างเป็นรายการงานวิจัยสำหรับเขียนสรุปส่ง | ด้านล่างเป็นรายการงานวิจัยสำหรับเขียนสรุปส่ง | ||
| − | * Omer Reingold, ''Undirected connectivity in log-space'', JACM 2008. [https://dl.acm.org/doi/10.1145/1391289.1391291] | + | * Space Complexity |
| − | ** notes: [http://www.ccs.neu.edu/home/viola/classes/gems-08/lectures/le15-18.pdf] by Emanuele Vioa | + | ** Omer Reingold, ''Undirected connectivity in log-space'', JACM 2008. [https://dl.acm.org/doi/10.1145/1391289.1391291] |
| − | + | *** notes: [http://www.ccs.neu.edu/home/viola/classes/gems-08/lectures/le15-18.pdf] by Emanuele Vioa | |
| − | * Christopher Umans, ''Hardness of Approximating <math>\Sigma^p_2</math> Minimization Problems'', FOCS'99. [https://dl.acm.org/doi/10.5555/795665.796539] [http://users.cms.caltech.edu/~umans/papers/U99b.ps .ps] | + | * Polynomial hierarchy |
| + | ** Christopher Umans, ''Hardness of Approximating <math>\Sigma^p_2</math> Minimization Problems'', FOCS'99. [https://dl.acm.org/doi/10.5555/795665.796539] [http://users.cms.caltech.edu/~umans/papers/U99b.ps .ps] | ||
| + | * Time-space trade-off | ||
| + | ** 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] | ||
| + | * 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
- Polynomial hierarchy
- 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
- 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
