Computational complexity/paper list

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

• 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]