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

รุ่นแก้ไขเมื่อ 21:42, 11 พฤษภาคม 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 $\Sigma _{2}^{p}$ 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]

@@ แถว 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]
 ** (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]