Computational complexity/paper list - ประวัติรุ่นแก้ไข

Bundit เมื่อ 03:39, 14 พฤษภาคม 2564

2021-05-14T03:39:43Z

Bundit เมื่อ 03:38, 14 พฤษภาคม 2564

2021-05-14T03:38:31Z

Bundit เมื่อ 03:35, 14 พฤษภาคม 2564

2021-05-14T03:35:25Z

Jittat เมื่อ 21:51, 11 พฤษภาคม 2564

2021-05-11T21:51:13Z

Jittat เมื่อ 21:42, 11 พฤษภาคม 2564

2021-05-11T21:42:31Z

Jittat เมื่อ 21:38, 11 พฤษภาคม 2564

2021-05-11T21:38:36Z

Jittat เมื่อ 21:30, 11 พฤษภาคม 2564

2021-05-11T21:30:09Z

Jittat: สร้างหน้าด้วย "ด้านล่างเป็นรายการงานวิจัยสำหรับเขียนสรุปส่ง * Omer Reingold, ''..."

2021-05-11T21:20:38Z

สร้างหน้าด้วย "ด้านล่างเป็นรายการงานวิจัยสำหรับเขียนสรุปส่ง * Omer Reingold, ''..."

หน้าใหม่

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

* 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

@@ แถว 17: / แถว 17: @@
 ** 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
+** Johan Håstad: Some optimal inapproximability results, STOC'97, J.ACM'01

@@ แถว 16: / แถว 16: @@
 * PCP & Property Test
 ** Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. STOC 1990: 73-83
-** Jaikumar Radhakrishnan, Madhu Sudan: On Dinur’s Proof of the PCP Theorem. APPROX 2021
+** Venkatesan Guruswami, Jakub Opršal, Sai Sandeep: Revisiting Alphabet Reduction in Dinur’s PCP. APPROX 2020
 ** Johan Håstad: Some optimal inapproximability results

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 03:35, 14 พฤษภาคม 2564
แถว 14:		แถว 14:
	** 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]		** 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]		** 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
		+	** Jaikumar Radhakrishnan, Madhu Sudan: On Dinur’s Proof of the PCP Theorem. APPROX 2021
		+	** Johan Håstad: Some optimal inapproximability results

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 21:51, 11 พฤษภาคม 2564
แถว 11:		แถว 11:
	* Derandomization		* Derandomization
	** Nisan & Wigderson, Hardness vs randomness, JCSS, 1994. [https://www.sciencedirect.com/science/article/pii/S0022000005800431]		** 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]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 21:42, 11 พฤษภาคม 2564
แถว 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]

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 21:30, 11 พฤษภาคม 2564
แถว 3:		แถว 3:
	* Omer Reingold, ''Undirected connectivity in log-space'', JACM 2008. [https://dl.acm.org/doi/10.1145/1391289.1391291]		* 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		** 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]