Grad talks

หน้านี้สำหรับรวบรวมหัวข้อและกำหนดการของการพูดคุย Graduate Talks

เวลา: อังคาร 12:30 - 13:30

สถานที่: ห้อง 404

ครั้งที่	วันที่	ผู้นำการพูดคุย	หัวข้อ/abstract
1	2 กค. 56	อ.ภารุจ	Reflections on trusting trust [1] ในปี 1984 Ken Thompson ได้รับรางวัลที่มีเกียรติ์สูงสุดในวงการคอมพิวเตอร์คือ ACM Turing Award ในฐานะที่เป็นผู้สร้างระบบปฏิบัติการ UNIX แต่ Ken เลือกที่จะกล่าวคำปราศรัยในตอนรับรางวัลในเรื่องที่ไม่เกี่ยวกับ UNIX โดยตรง โดยเขาเลือกที่จะพูดถึงเรื่องคอมไพเลอร์ภาษาซี และกระบวนการสร้างโปรแกรมที่สร้างโปรแกรมเดิมออกมา ผลกระทบจากคำปราศรัยและบทความที่เกี่ยวเนื่องทำให้วงการความปลอดภัย ทางระบบคอมพิวเตอร์สั่นคลอน สิ่งที่เขาพูดในปีนั้นได้หลอกหลอนนักวิจัยในวงการนี้มาจนทุกวันนี้ และยังไม่มีใครที่จะมาหักล้างเขาได้ Ken บอกว่ากระบวนการในการผลิตและใช้งานโปรแกรมที่เรากระทำกันอยู่ทุกวันนี้ ไม่มีทางที่จะตรวจสอบหรือว่าเชื่อถือกับสิ่งใดๆได้ 100% เลย ในการบรรยายนี้เราจะมาทำความเข้าใจกับสิ่งที่ Ken ได้ฝากไว้ และอาจจะมีการอภิปรายกันถึงเรื่องปรัชญาที่เกี่ยวเนื่องอีกด้วย
2	16 กค. 56	อ.จิตร์ทัศน์	Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems [2] ปัญหาในกลุ่ม NP สามารถนิยามได้ผ่านทางการปฏิสัมพันธ์ (interaction) ระหว่างผู้พิสูจน์ (prover) และผู้ตรวจสอบ (verifier) ที่มีการติดต่อกันเพียงรอบเดียว แนวคิดดังกล่าว ถ้าเราไม่จำกัดจำนวนรอบของการปฏิสัมพันธ์ เราจะได้กลุ่มของปัญหาที่มีระบบพิสูจน์แบบปฏิสัมพันธ์ (Interactive Proof System) คำถามที่น่าสนใจ และเกี่ยวข้องกับเนื้อหาจากการพูดคุยครั้งก่อน ก็คือเป็นไปได้หรือไม่ที่ระหว่างที่ผู้พิสูจน์ดำเนินการพิสูจน์ประโยคบางอย่างต่อผู้ตรวจสอบ ผู้พิสูจน์จะไม่เปิดเผย "ข้อมูล" อื่น ๆ ให้กับผู้ตรวจสอบ? เปเปอร์ข้างต้นนำเสนอระบบพิสูจน์ที่รับประกันว่าระหว่างการพิสูจน์ ผู้พิสูจน์จะไม่เปิดเผยข้อมูลอื่น ๆ แก่ผู้ตรวจสอบแม้แต่น้อย (ระบบพิสูจน์ดังกล่าวเรียกว่า Zero-Knowledge Proof) สำหรับปัญหา graph isomorphism และ graph non-isomorphism นอกจากนี้ ภายใต้เงื่อนไขทางการเข้ารหัสบางอย่าง เปเปอร์ข้างต้นเสนอระบบ zero-knowledge system สำหรับปัญหา 3-COLOR ที่ต้องการตัดสินว่ากราฟที่ได้รับสามารถระบายสีด้วยสีสามสีโดยที่ไม่มีโหนดคู่ใดที่มีเส้นเชื่อมติดกันมีสีเดียวกัน ผมจะนำเสนอแนวคิดดังกล่าว และอธิบายไอเดียหลักของบทพิสูจน์ในเปเปอร์ด้านบน (เท่าที่อ่านทันนะครับ)
3	30 กค. 56	อ.ธนาวินท์	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)
4	13 สค. 56	อ.ชัยพร	Protothread [4] ผมจะขอพูดถึงเรื่อง Protothread ซึ่งเป็นความพยายามในการสร้าง abstraction เพื่อให้การพัฒนาแอพลิเคชันแบบมัลติทาสค์ บนแพลทฟอร์มที่มีหน่วยความจำกัด (ในที่นี้ คือระดับไม่กี่กิโลไบท์) เป็นเรื่องสะดวกขึ้นโดยการใช้ท่าพิสดารผ่านมาโครของภาษาซี กลไกนี้ทำให้ เราสามารถเขียนโค้ดให้กับแต่ละส่วนของแอพลิเคชันในรูปโครูทีนที่เสมือนว่ามีทำงานไปพร้อม ๆ กัน ซึ่งมีลำดับขั้นตอนที่ง่ายต่อการเข้าใจมากกว่ารูปแบบเครื่องจักรสถานะแบบเดิมที่ใช้กันในคอมพิวเตอร์ ฝังตัวทั่วไป
5	27 สค. 56	อ.ภารุจ	Checkpointed Early Load Retirement [5] Checkpointed Early Load Retirement เป็นความพยายามที่จะเพิ่มสมรรถนะของการประมวลผลของ "CPU แบบ superscalar ที่ใช้ ROB เพื่อรองรับ precise exception โดยการใช้ value prediction ทำนายค่าของคำสั่ง load ที่ตำแหน่งหัวของ ROB ที่ miss ใน L2 cache" อย่าเพิ่งตกใจกับคำศัพท์นะครับ เราจะใช้เวลา 20 นาที่แรกในการเรียนรู้พื้นฐานทางสถาปัตยกรรมคอมพิวเตอร์ทั้งหมดที่สั่งสมมากว่า 20 ปี และจะทำความเข้าใจบทความนี้ด้วยกัน ;) เกร็ดเล็กน้อยเกี่ยวกับบทความนี้ : คนเขียนบทความนี้เป็นฝาแฝดผู้หญิงที่น่าจะเป็นคู่แรกของโลกในวงการสถาปัตยกรรมคอมพิวเตอร์ และเป็นบทความแรกของเธอทั้งคู่ในชีวิตการเป็นนักศึกษาปริญญาเอกครับ
6	10 กย. 56	อ.จิตร์ทัศน์	Differential Privacy [6] ผมจะมาเล่าเรื่องเกี่ยวกับ differential privacy ซึ่งเป็นเครื่องมือในการวิเคราะห์ความเป็นส่วนตัวของข้อมูลของปัจเจกเมื่อถูกนำไปประมวลผลกับข้อมูลก้อนใหญ่ (เช่นการนำข้อมูลทางการแพทย์ไปหาสถิติภาพรวม หรือพวกการทำ data mining) เพิ่มเติม : http://research.microsoft.com/apps/pubs/default.aspx?id=74339
7	1 ตค. 56	อ.ธนาวินท์	Parameter-free (time series) data mining [7] ผมจะมายกตัวอย่างให้ดูสองสามแบบครับว่าทางแลปที่ผมอยู่เนี่ยเค้าสนใจเรื่องการลด parameter ด้วยครับ
8	5 พย. 56	อ.ชัยพร	Compressive Sensing บน Sensor Network [8] หลัก ๆ จะอิงตามเปเปอร์สองฉบับนี้ครับ http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5461926 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1614066
9	26 พย. 56	ธานี	Dynamic graph algorithm [9] ปัญหาบนกราฟทุกคนคงรู้จักดี เช่น Minimum Spanning Tree ทีนี้เราจะแก้ปัญหานั้นๆ บนกราฟที่มีการเปลี่ยนแปลงตลอดเวลา ซึ่งการเปลี่ยนแปลงที่ว่าก็คือ การเพิ่มหรือลด edge ครับ ในการแก้ปัญหานี้ก็จะมี Data Structure ที่น่าสนใจที่นำมาใช้ได้ครับ โดยในเปเปอร์ด้านบน พูดถึงปัญหาหลายปัญหาครับ ซึ่งผมน่าจะพูดแค่ Connectivity และ บางส่วนของ MST (ถ้าทัน)
10	17 ธค. 56	ธรรมรักษ์	Path coverage in wireless sensor networks [10] จะสนใจในเรื่องของการหาเส้นทางของ target ที่เคลื่อนที่เข้ามาใน wireless sensor networks อย่างมีเงื่อนไขค่ะ เงื่อนไขแรกคือต้องการให้ target เสี่ยงต่อการถูกตรวจจับได้จาก sensor น้อยที่สุด ส่วนอีกเงื่อนไขหนึ่งกลับกัน คือต้องการให้ target ถูกตรวจจับได้มากๆ ซึ่งจะมีรายละเอียดของปัญหาอยู่ค่ะ เปเปอร์เพิ่มเติม http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=1204831&queryText%3DCoverage+in+Wireless+Ad+Hoc+Sensor+Networks+X-Y+Li
11	21 มค. 57	วิศรุต	Internet load balancing ใน High-speed Network [11] สวัสดีครับ ในวันอังคารที่ 21 ม.ค.นี้ผมจะพูดเรื่อง Internet load balancing ใน High-speed Network นะครับ โดยจะสนใจในเรื่องของการทำ balancing ใน network ขนาดใหญ่โดยใช้ hash function เป็นหลักนะครับ
12	11 กพ. 57	กฤษฎิ์	Object recognition in 3D scenes with occlusions and clutter by Hough voting [12] เป็นเรื่องเกี่ยวกับ object recognition โดยใช้ข้อมูล 3D ที่ได้จาก kinect ครับ
13	11 มี.ค. 57	อ.ภารุจ	Threads cannot be implemented as a library [13] เราอยู่ในยุคของมัลติคอร์และการโปรแกรมแบบขนาน และเมื่อนึกถึงการโปรแกรมแบบขนาน โปรแกรมเมอร์ก็มักจะใช้เลือกใช้ thread library เพื่อแตก thread ย่อยและทำการสื่อสารระหว่าง thread แต่การใช้ thread library ในโปรแกรมแบบขนานที่เขียนด้วยภาษาอย่าง C/C++ มีปัญหาในเบื้องลึกที่จะต้องเยียวยากันให้ถูกต้องทีเดียว ใน grad talk คราวนี้เราจะมาทำความเข้าใจเรื่องราวที่มันเกิดเป็นประเด็นขึ้นมา จนกระทั่งการนำไปสู่ความพยายามในการสร้าง ข้อกำหนดเกี่ยวกับหน่วยความจำที่มีความแข็งแกร่งและชัดเจนกว่าก่อนหน้านี้ี้
14	25 มี.ค. 57	อ.จิตร์ทัศน์	A fast solver for a class of linear systems. [14] ผมจะพูดเกี่ยวกับ development ของ algorithm ที่แก้สมการเชิงเส้นที่มีเงื่อนไขเป็นเมตริกซ์ที่มาจากกราฟ (laplacian matrices of graphs) ในไม่กี่ปีที่ผ่านมา มีการพัฒนาอัลกอริทึมที่ทำงานเร็วขึ้นเพื่อประมาณค่า max flow บนกราฟที่ไม่มีทิศทางอย่างต่อเนื่อง หรือล่าสุดได้มีการค้นพบอัลกอริทึมที่หา bipartite matching ที่เร็วขึ้น (bipartite matching ถ้าพิจารณาเป็นปัญหา max flow จะเป็น max flow บน directed graph) ปัญหาเหล่านี้ไม่มีพัฒนาการใด ๆ มาหลายสิบปี เครื่องมือหลักพื้นฐานก็คืออัลกอริทึมที่สามารถแก้สมการเชิงเส้นรูปแบบพิเศษนี้ได้ในเวลาใกล้กับ linear time การพัฒนาอัลกอริทึมดังกล่าวของ Daniel A. Spielman และ Shang-Hua Teng นับเป็นงานสำคัญมาก ๆ และได้มีการพัฒนาเครื่องมีหลายชิ้นเพื่อจะให้ถึงเป้าหมายดังกล่าวนอกจากนี้ยังเป็นการนำเครื่องมือเชิง algebraic เข้ามาในพื้นที่ที่เคยมีแต่อัลกอริทึมแบบ combinatorial ด้วย ผมจะพยายามเล่าที่มาที่ไปและแสดงให้เห็นถึงบางองค์ประกอบที่น่าสนใจของพัฒนาการนี้ หน้าเว็บที่เกี่ยวข้อง: http://www.cs.yale.edu/homes/spielman/precon/precon.html
15	3 มิ.ย. 57	อ.ธนาวินท์	How to do good research, get it published in SIGKDD and get it cited! [15] ผมหมดมุขแล้วครับ เลยจะพูดกว้างๆ เรื่องการทำวิจัยครับ ในหัวข้อ "How to do good research, get it published in SIGKDD and get it cited!" ของคุณ Eamonn Keogh ครับ คงจะพูดๆ ข้ามๆ ครับ เพราะว่างานนี้เป็น talk ยาว 3 ชม. ครับ
16	24 มิ.ย. 57	อ.ชัยพร	Networking Named Contents [16] หัวข้อที่จะขอนำมาเล่าให้ฟังคือ Content-Centric Networks (CCN) หรืออีกชื่อหนึ่งคือ Named Data Networks (NDN) ซึ่งเป็นความพยายามที่จะทำให้เครือข่ายอินเตอร์เน็ตรองรับการขนส่งข้อมูลแบบเจาะจงเนื้อหาแทนที่จะเป็นแบบเจาะจงโฮสท์ เพื่อให้สอดรับกับลักษณะการใช้งานอินเตอร์เน็ตของผู้ใช้ส่วนใหญ่ในปัจจุบันที่สนใจว่าข้อมูลมีเนื้อหาอะไรมากกว่าอยู่ที่เครื่องไหน จริง ๆ แล้วแนวคิดนี้เคยถูกนำเสนอมาแล้วบ่อยครั้งในหลายสิบปีที่ผ่านมา แต่งวดนี้หนึ่งในตัวตั้งตัวตีคือคุณ Van Jacobson เจ้าพ่อ TCP/IP ผู้พัฒนา flow/congestion control algorithm ที่เราคุ้นเคย อีกทั้งยังได้รับทุนสนับสนุนจากมูลนิธิวิทยาศาสตร์แห่งชาติสหรัฐอเมริกา (NSF) เพื่อวิจัยและพัฒนาสถาปัตยกรรมเครือข่ายอินเตอร์เน็ตแห่งอนาคต จึงน่าลุ้นว่าแนวคิดนี้จะประสบความสำเร็จเพียงใดต่อไป และถ้ามีเวลาอาจจะโฉบมาคุยเรื่องการหาเส้นทางและการประยุกต์ใช้ NDN ในเครือข่ายระหว่างยานพาหนะ (VANET) อีกสองเปเปอร์ดังนี้ครับ NLSR: Named-data Link State Routing Protocol http://dl.acm.org/citation.cfm?id=2491231 VANET via Named Data Networking http://named-data.net/publications/vanet_via_ndn_infocom_nom/
17	8 ก.ค. 57	อ.ภารุจ	Anti-kobpae [17] GradTalk ในวันพรุ่งนี้ ผมขอปาดหน้า อ. จิตรทัศน์ เนื่องจากอยากจะนำงานที่กำลังดำเนินการอยู่มาให้ทางทีมได้ช่วยกันวิจารณ์ครับ โดยในการพูดคุยคราวนี้ ผมจะนำแนวคิดและแนวทางปฏิบัติในการปรับปรุงสมรรถนะระบบตรวจสอบการคัดลอก anti-kobpae มานำเสนอครับ โดยจะพูดถึงการปรับปรุงทั้งในมุมของอัลกอริทึมและสถาปัตยกรรมการคำนวณ โดยในมุมแรกนั้น จะพูดถึงเทคนิคการใช้ locality sensitive hashing เป็นตัวกรองในชั้นแรก ก่อนที่จะตรวจสอบความคล้ายคลึงในระดับหน่วยย่อยโดยใช้ edit distance ในขั้นต่อมา ในแง่มุมที่สอง จะพูดถึงการกระจายไฟล์ข้อมูลที่เป็นฐานในการตรวจสอบ เพื่อใช้การคำนวณแบบขนานในการเพิ่มสมรรถนะ โดยจะเทียบเคียงการประมวลผลโดยใช้ MapReduce กับ parallel RDBMS ลิงค์ไปหารายละเอียดและบทความที่เกี่ยวข้องครับ http://web.mit.edu/andoni/www/LSH/index.html http://research.google.com/archive/mapreduce.html http://research.google.com/pubs/pub38125.html
18	22 ก.ค. 57	อ.จิตร์ทัศน์	Small-World Phenomenon [18] ผมจะมาพูดเกี่ยวกับเรื่อง Small-World Phenomenon นะครับ โดยจะเริ่มจากข้อสังเกตและการทดลองต่าง ๆ เกี่ยวกับปรากฏการณ์ที่เรียกรวม ๆ กันว่า small-world ที่หลาย ๆ คนเคยได้ยิน (เช่นเรื่องพวก six-degree of separation) และจะแสดงให้เห็นว่า model พื้นฐานของ random graph สองแบบที่มีใช้อยู่ก่อนหน้ามีการศึกษาเรื่องนี้ ไม่เหมาะสมกับการศึกษาปรากฏการณ์นี้ จากนั้นผมจะอธิบายโมเดลที่นำเสนอโดย Kleinberg ที่ปรับมาจากโมเดลของ Watts และ Strogatz เพื่อที่จะศึกษาปรากฏการณ์ดังกล่าวในมุมมองของอัลกอริทึม เปเปอร์ที่อ้างอิงคืออันนี้นะครับ J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. อ่านแบบ html: http://www.cs.cornell.edu/home/kleinber/swn.d/swn.html pdf: http://www.cs.cornell.edu/home/kleinber/swn.pdf