ผลต่างระหว่างรุ่นของ "Grad talks"
| แถว 15: | แถว 15: | ||
|- | |- | ||
| 2 || 16กค. || จิตร์ทัศน์ | | 2 || 16กค. || จิตร์ทัศน์ | ||
| − | | Zero knowledge proof | + | | Zero knowledge proof [http://dx.doi.org/10.1145/116825.116852] |
| + | |||
| + | ปัญหาในกลุ่ม NP สามารถนิยามได้ผ่านทางการปฏิสัมพันธ์ (interaction) ระหว่างผู้พิสูจน์ (prover) และผู้ตรวจสอบ (verifier) ที่มีการติดต่อกันเพียงรอบเดียว แนวคิดดังกล่าว ถ้าเราไม่จำกัดจำนวนรอบของการปฏิสัมพันธ์ เราจะได้กลุ่มของปัญหาที่มีระบบพิสูจน์แบบปฏิสัมพันธ์ (Interactive Proof System) | ||
| + | |||
| + | คำถามที่น่าสนใจ และเกี่ยวข้องกับเนื้อหาจากการพูดคุยครั้งก่อน ก็คือเป็นไปได้หรือไม่ที่ระหว่างที่ผู้พิสูจน์ดำเนินการพิสูจน์ประโยคบางอย่างต่อผู้ตรวจสอบ ผู้พิสูจน์จะไม่เปิดเผย "ข้อมูล" อื่น ๆ ให้กับผู้ตรวจสอบ? | ||
| + | |||
| + | เปเปอร์ข้างต้นนำเสนอระบบพิสูจน์ที่รับประกันว่าระหว่างการพิสูจน์ ผู้พิสูจน์จะไม่เปิดเผยข้อมูลอื่น ๆ แก่ผู้ตรวจสอบแม้แต่น้อย (ระบบพิสูจน์ดังกล่าวเรียกว่า Zero-Knowledge Proof) สำหรับปัญหา graph isomorphism และ graph non-isomorphism นอกจากนี้ ภายใต้เงื่อนไขทางการเข้ารหัสบางอย่าง เปเปอร์ข้างต้นเสนอระบบ zero-knowledge system สำหรับปัญหา 3-COLOR ที่ต้องการตัดสินว่ากราฟที่ได้รับสามารถระบายสีด้วยสีสามสีโดยที่ไม่มีโหนดคู่ใดที่มีเส้นเชื่อมติดกันมีสีเดียวกัน | ||
| + | |||
| + | ผมจะนำเสนอแนวคิดดังกล่าว และอธิบายไอเดียหลักของบทพิสูจน์ในเปเปอร์ด้านบน (เท่าที่อ่านทันนะครับ) | ||
|- | |- | ||
| 3 || 30กค. || ธนาวินทร์ | | 3 || 30กค. || ธนาวินทร์ | ||
| − | | Game with a purpose | + | | Game with a purpose [http://www.cs.cmu.edu/~biglou/ieee-gwap.pdf] |
| + | |||
| + | อังคารหน้านี้ ผมจะคุยเกี่ยวกับแนวคิดแบบเก๋ไก๋ที่พยายามหลอกใช้พลังความคิดของมนุษย์แทน AI ชั้นต่ำครับ ^___^ (คือมนุษย์เก่งกว่ามากน่ะครับ) | ||
| + | ซึ่งงานที่จะพูดถึงนี้เป็นของคุณ Luis von Ahn ครับ งานของเค้ามีหลากหลายมากครับ โดยอังคารนี้ผมจะเน้นที่งานนี้เป็นหลักครับ | ||
| + | Game with a purpose (http://www.cs.cmu.edu/~biglou/ieee-gwap.pdf) และ | ||
| + | Designing game with a purpose (http://dl.acm.org/citation.cfm?id=1378719) | ||
|} | |} | ||
รุ่นแก้ไขเมื่อ 07:46, 30 กรกฎาคม 2556
หน้านี้สำหรับรวบรวมหัวข้อและกำหนดการของการพูดคุย Graduate Talks
เวลา: อังคาร 12:00 - 13:00
สถานที่: ห้อง 404
| ครั้งที่ | วันที่ | ผู้นำการพูดคุย | หัวข้อ/abstract |
|---|---|---|---|
| 1 | 2กค. | ภารุจ | Reflections on trusting trust [1]
ในปี 1984 Ken Thompson ได้รับรางวัลที่มีเกียรติ์สูงสุดในวงการคอมพิวเตอร์คือ ACM Turing Award ในฐานะที่เป็นผู้สร้างระบบปฏิบัติการ UNIX แต่ Ken เลือกที่จะกล่าวคำปราศรัยในตอนรับรางวัลในเรื่องที่ไม่เกี่ยวกับ UNIX โดยตรง โดยเขาเลือกที่จะพูดถึงเรื่องคอมไพเลอร์ภาษาซีและกระบวนการสร้างโปรแกรมที่สร้างโปรแกรมเดิมออกมา ผลกระทบจากคำปราศรัยและบทความที่เกี่ยวเนื่องทำให้วงการความปลอดภัียทางระบบคอมพิวเตอร์สั่นคลอน สิ่งที่เขาพูดในปีนั้นได้หลอกหลอนนักวิจัยในวงการนี้มาจนทุกวันนี้ และยังไม่มีใครที่จะมาหักล้างเขาได้ Ken บอกว่ากระบวนการในการผลิตและใช้งานโปรแกรมที่เรากระทำกันอยู่ทุกวันนี้ ไม่มีทางที่จะตรวจสอบหรือว่าเชื่อถือกับสิ่งใดๆได้ 100% เลย ในการบรรยายนี้เราจะมาทำความเข้าใจกับสิ่งที่ Ken ได้ฝากไว้ และอาจจะมีการอภิปรายกันถึงเรื่องปรัชญาที่เกี่ยวเนื่องอีกด้วย |
| 2 | 16กค. | จิตร์ทัศน์ | Zero knowledge proof [2]
ปัญหาในกลุ่ม NP สามารถนิยามได้ผ่านทางการปฏิสัมพันธ์ (interaction) ระหว่างผู้พิสูจน์ (prover) และผู้ตรวจสอบ (verifier) ที่มีการติดต่อกันเพียงรอบเดียว แนวคิดดังกล่าว ถ้าเราไม่จำกัดจำนวนรอบของการปฏิสัมพันธ์ เราจะได้กลุ่มของปัญหาที่มีระบบพิสูจน์แบบปฏิสัมพันธ์ (Interactive Proof System) คำถามที่น่าสนใจ และเกี่ยวข้องกับเนื้อหาจากการพูดคุยครั้งก่อน ก็คือเป็นไปได้หรือไม่ที่ระหว่างที่ผู้พิสูจน์ดำเนินการพิสูจน์ประโยคบางอย่างต่อผู้ตรวจสอบ ผู้พิสูจน์จะไม่เปิดเผย "ข้อมูล" อื่น ๆ ให้กับผู้ตรวจสอบ? เปเปอร์ข้างต้นนำเสนอระบบพิสูจน์ที่รับประกันว่าระหว่างการพิสูจน์ ผู้พิสูจน์จะไม่เปิดเผยข้อมูลอื่น ๆ แก่ผู้ตรวจสอบแม้แต่น้อย (ระบบพิสูจน์ดังกล่าวเรียกว่า Zero-Knowledge Proof) สำหรับปัญหา graph isomorphism และ graph non-isomorphism นอกจากนี้ ภายใต้เงื่อนไขทางการเข้ารหัสบางอย่าง เปเปอร์ข้างต้นเสนอระบบ zero-knowledge system สำหรับปัญหา 3-COLOR ที่ต้องการตัดสินว่ากราฟที่ได้รับสามารถระบายสีด้วยสีสามสีโดยที่ไม่มีโหนดคู่ใดที่มีเส้นเชื่อมติดกันมีสีเดียวกัน ผมจะนำเสนอแนวคิดดังกล่าว และอธิบายไอเดียหลักของบทพิสูจน์ในเปเปอร์ด้านบน (เท่าที่อ่านทันนะครับ) |
| 3 | 30กค. | ธนาวินทร์ | Game with a purpose [3]
อังคารหน้านี้ ผมจะคุยเกี่ยวกับแนวคิดแบบเก๋ไก๋ที่พยายามหลอกใช้พลังความคิดของมนุษย์แทน AI ชั้นต่ำครับ ^___^ (คือมนุษย์เก่งกว่ามากน่ะครับ) ซึ่งงานที่จะพูดถึงนี้เป็นของคุณ Luis von Ahn ครับ งานของเค้ามีหลากหลายมากครับ โดยอังคารนี้ผมจะเน้นที่งานนี้เป็นหลักครับ Game with a purpose (http://www.cs.cmu.edu/~biglou/ieee-gwap.pdf) และ Designing game with a purpose (http://dl.acm.org/citation.cfm?id=1378719) |
