ผลต่างระหว่างรุ่นของ "Computational complexity/paper list"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 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] | ||
รุ่นแก้ไขเมื่อ 21:38, 11 พฤษภาคม 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
