ผลต่างระหว่างรุ่นของ "Grad talks"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 305: แถว 305:
 
|-
 
|-
 
| 34 || 21 เมย. 58 || คุณสุชา<br/>(แขกรับเชิญพิเศษ)
 
| 34 || 21 เมย. 58 || คุณสุชา<br/>(แขกรับเชิญพิเศษ)
−
| '''Achieving Utility-Delay-Reliability Tradeoff in Stochastic Network Optimization with Finite Buffers
+
| '''Achieving Utility-Delay-Reliability Tradeoff in Stochastic Network Optimization with Finite Buffers''' [http://www-scf.usc.edu/~supittay/conference/Sucha_finite_buffer_INFOCOM.pdf] [http://arxiv.org/abs/1501.03457]
−
'''[http://www-scf.usc.edu/~supittay/conference/Sucha_finite_buffer_INFOCOM.pdf] [http://arxiv.org/abs/1501.03457]
+
 
 
This talk has two parts. The first part introduces a state of the art technique called ``stochastic network optimization.''<br/>
 
This talk has two parts. The first part introduces a state of the art technique called ``stochastic network optimization.''<br/>
 
The technique is used to stabilize queuing systems, including but not limited to communication networks,<br/>
 
The technique is used to stabilize queuing systems, including but not limited to communication networks,<br/>
แถว 324: แถว 324:
 
and low complexity nature of the drift-plus-penalty algorithm.
 
and low complexity nature of the drift-plus-penalty algorithm.
 
|-
 
|-
−
| 35 || 5 พค. 58 || อดิศักดิ์
+
| 35 || 12 พค. 58 || อดิศักดิ์
 
| '''online learning problem / sequential decision problem''' [http://homes.di.unimi.it/~cesabian/Pubblicazioni/J18.pdf] [http://www.cs.cmu.edu/~avrim/Papers/onlineauction.pdf]
 
| '''online learning problem / sequential decision problem''' [http://homes.di.unimi.it/~cesabian/Pubblicazioni/J18.pdf] [http://www.cs.cmu.edu/~avrim/Papers/onlineauction.pdf]
 
เป็นปัญหาที่เราต้องตัดสินใจเลือกกระทำการ(action)อย่างใดอย่างหนึ่งเป็นรอบๆ โดยหลังจากที่เราตัดสินใจในแต่ละรอบจะมี feedback<br/>
 
เป็นปัญหาที่เราต้องตัดสินใจเลือกกระทำการ(action)อย่างใดอย่างหนึ่งเป็นรอบๆ โดยหลังจากที่เราตัดสินใจในแต่ละรอบจะมี feedback<br/>
แถว 339: แถว 339:
 
ผมจะขอรวบยอดพูดถึงทั้ง2รูปแบบข้างต้นผ่านทางปัญหา "online pricing" หรือ "การตั้งราคาแบบออนไลน์"<br/>
 
ผมจะขอรวบยอดพูดถึงทั้ง2รูปแบบข้างต้นผ่านทางปัญหา "online pricing" หรือ "การตั้งราคาแบบออนไลน์"<br/>
 
โดยผมจะอธิบายรวมถึงพิสูจน์ประสิทธิภาพของอัลกอริทึมพื้นฐานสำหรับทั้ง2รูปแบบของปัญหาดังกล่าว
 
โดยผมจะอธิบายรวมถึงพิสูจน์ประสิทธิภาพของอัลกอริทึมพื้นฐานสำหรับทั้ง2รูปแบบของปัญหาดังกล่าว
 +
|-
 +
| 36 || 9 มิย. 58 || อรรถกร
 +
| '''Single-source unsplittable flow''' [http://link.springer.com/article/10.1007/s004930050043] [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=548465&url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber%3D548465] [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=646131&url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber%3D646131]
 +
Single-source unsplittable flow สำหรับกราฟมีทิศทางที่มี edge capacity เป็นจำนวนจริงบวก ซึ่งระบุโหนดต้นทาง(โหนดเดียว)<br/>
 +
และปลายทางที่มีปริมาณการร้องขอจำนวน  สำหรับแต่ละปลายทางเราต้องการหา path จากต้นทางไปปลายทางเพื่อรองรับปริมาณการร้องขอ<br/>
 +
โดยทุก edge ปฏิบัติตาม capacity constraint<br/>
 +
 +
ในปี 1996 Jon Kleinberg [1] ได้นำเสนอปัญหาเกี่ยวกับ single-source unsplittable flow<br/>
 +
และได้แสดง constant-factor approximation algorithm แรก ซึ่งต่อมา Stavros Kolliopoulos และ Clifford Stein<br/>
 +
ได้พัฒนา algorithm ที่ให้ bound ที่ดีขึ้น [2]  ก่อนที่ Yefim Dinitz, Naveen Garg และ Michel X. Goemans<br/>
 +
จะตีพิมพ์ On the Single-Source Unsplittable Flow Problem ซึ่งให้ bound ที่ดีที่สุดจนถึงปัจุบัน และจะเป็นเนื้อหาหลักสำหรับการพูดครั้งนี้ครับ
 +
|-
 +
| 37 || 23 มิย. 58 || ศุภณัฐ
 +
| '''Pairing-based cryptography and its application in identity-based encryption''' [http://crypto.stanford.edu/~dabo/pubs/abstracts/bfibe.html] [http://crypto.stanford.edu/~dabo/pubs/abstracts/bbibe.html]
 +
pairing เป็นเครื่องมือที่สำคัญในการออกแบบ cryptographic protocol ในสมัยใหม่ โดยอาศัยคุณสมบัติที่สำคัญของ pairing<br/>
 +
identity-based encryption(IBE) เป็นตัวอย่างหนึ่งที่สามารถสร้างมาจาก pairing โดยเป็น encryption ที่ใช้ public/private key <br/>
 +
แต่มีคุณลักษณะพิเศษคือ public key จะเป็นอะไรก็ได้ตามที่เราเลือกเช่น ชื่อจริง หรือ อีเมล แทนที่จะใช้ public key ที่เป็น bit string ยาวๆ <br/>
 +
ผมจะพูดถึงการสร้าง IBE จาก pairing ทั้งหมดสองวิธี วิธีแรกเป็นของ Boneh-Frankin[1] อีกวิธีเป็นของ Boneh-Boyen[2]<br/>
 +
ต่อจากนั้นจะพูดถึง Anonymous IBE ซึ่งเป็นการใช้ IBE โดยที่ข้อความที่ถูก encrypt นั้นเราจะไม่รู้ว่าปลายทางของข้อความนั้นไปที่ไหน <br/>
 +
และนอกจาก Anonymous IBE ก็จะพูดคร่าวๆเกี่ยวกับ HIBE,ABE
 
|}
 
|}

รุ่นแก้ไขปัจจุบันเมื่อ 06:27, 6 กรกฎาคม 2558

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

เวลา: อังคาร 12:05 13:15

สถานที่: ห้อง 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

19 26 สค. 57 ธานี Balloon Popping With Applications to Ascending Auctions [19]

เป็นหัวข้อที่ว่าด้วยการตั้งราคา(หรือประมูล)ขายสินค้าดิจิตอลอย่างไร เพื่อให้ผู้ขายได้รับผลประโยชน์สูงสุด
โดยในเปเปอร์นี้ได้พิสูจน์ว่ากลไกการตั้งราคาที่ดีที่สุด ก็ไม่ได้ผลประโยชน์มากไปกว่าการตั้งราคากลางสักเท่าใดนัก
คือมากกว่าเป็นแค่ค่าคงที่ไม่เกินประมาณ 5 เท่าครับ

โดยการอธิบายนั้น ใช้วิธีการสร้างโมเดลของการประมูลนี้ให้เป็นปัญหาการเป่าลูกโป่ง เพื่อให้ได้อากาศรวมเยอะที่สุดแทนครับ
ผมคิดว่าจะอธิบายโมเดล และยกตัวอย่างให้เห็นภาพรวมถึงอธิบายในส่วนการพิสูจน์ได้บ้างครับ

20 8 กย. 57 กฤษฎิ์ scan algorithm and its application (Radix sort) [20]

จะพูดเรื่อง parallel computing บน GPU เป็น technical report

21 23 กย. 57 ธรรมรักษ์ On mobile sensor assisted field coverage [21]

คราวนี้จะยังคงอยู่ที่เรื่อง Coverage ใน wireless sensor networks อยู่
แต่ว่าเป็นงานค่อนข้างใหม่ ออกมาในปี 2013 นี่เองค่ะ หวังว่าจะยังไม่เบื่อกันเสียก่อนนะคะ :D
โดยในงานนี้จะสนใจว่าจะเคลื่อนที่ mobile sensors ไปที่ไหนดีเพื่อที่จะให้ static sensors ทำงานน้อยๆ
จะได้ประหยัดพลังงานของ static sensors อันจะส่งผลให้ network lifetime สูงขึ้นโดยที่ยังคงรักษา coverage ไว้ได้ด้วยค่ะ

22 7 ตค. 57 วิศรุต Parallel Firewall Designs for High-Speed Networks [22]

งานที่จะพูดเป็นเรื่องเกียวกับการออกแบบ parallel firewall สำหรับ high speed network
ซึ่งมีเป้าหมายให้ delay ที่เกิดขึ้นจากการทำงานของ firewall น้อยที่สุด
(เริ่ม 12.05)

23 21 ตค. 57 อ.จิตร์ทัศน์ Quantum Algorithm []

ผมจะมาเล่าเกี่ยว quantum algorithm ครับ ถ้าเป็นไปได้ จะพยายามไปให้ถึง quantum fft ครับ (คงไม่ถึง factorization)
ขึ้นกับว่าผมสามารถทบทวนความเข้าใจทันไม่ทันนะครับ 555

รบกวนขอเจอกัน 12:05 นะครับ

24 4 พย. 57 ภัทร Approximation algorithms for NP-complete problems on planar graphs [23]

ผมจะหยิบงานของ Brenda S. Baker
ชื่อ Approximation algorithms for NP-complete problems on planar graphs มาพูดครับ
งานนี่นำเสนอ เทคนิคที่สามารถใช้ ประมาณคำตอบปัญหา NP-complete หลาย ๆ ปัญหาบน Planar Graphs ได้
โดยมีความแม่นยำ และเวลาในการทำงานแปรตามค่า k ซึ่งกำหนดได้ครับ

25 18 พย. 57 สรทัศน์ Internet of Things(IoT): A vision, architectural elements, and future directions [24]

grad talks ครั้งต่อไปวันที่ 18 พ.ย. เวลา 12.05น. ครับ
ผมจะพูดเรื่อง Internet of Things(IoT): A vision, architectural elements, and future directions
ของ Jayavardhana Gubbi, Rajkumar Buyya, Slaven Marusic เเละ Marimuthu Palaniswami
ขอบคุณครับ

26 2 ธค. 57 ชยธร Energy-Aware Design For Wireless Mesh Networks [25]

อังคารนี้จะผมขอพูดเรื่อง Energy-Aware Design For Wireless Mesh Networks
เกี่ยวกับการบริหารการใช้พลังงานใน WMN ครับ ขอบคุณครับ

27 13 มค. 58 ณัฐวุฒิ Automatically mining software-based, semantically-similar words from comment-code mappings [26]

ผมจะมาพูดเรื่อง Automatically mining software-based, semantically-similar words from comment-code mappings
โดย Matthew J. Howard, Samir Gupta, Lori Pollock และ K. Vijay-Shanker
ซึ่ง paper นี้ ถูกเลือกเป็น distinguished papers ในปี 2013 ของงานสัมมนา Mining Software Repositories ครับ

งานดังกล่าวนำเสนอการจับคู่ keyword ที่พ้องความหมายกันใน context ที่เค้าสนใจ (รหัสต้นฉบับโปรแกรม)
ซึ่งจะเห็นประโยชน์ได้อย่างชัดเจน เมื่อนำไปประยุกต์ใช้กับการค้นหา keyword เหล่านี้ครับ

28 27 มค. 58 กฤตา Vulnerability Analysis and Attacks on NFC-enabled Mobile Phones [27]

โดยงานนี้จะเสนอเรื่องการวิเคราะห์ช่องโหว่และการโจมตีสมาร์ทโฟนผ่านทางอินเตอร์เฟส NFC อาทิเช่น NFC-based worm, Denial-of-Service ค่ะ
หวังว่าจะเป็นประโยชน์ต่อทุกท่านนะคะ

29 10 กพ. 58 ภาสกร No wire / No plug / No battery [28][29]

จะกล่าวถึง การทำงานของอุปกรณ์ไฟฟ้า อย่าง Switch ไฟบ้าน ที่ได้รับเอา Energy harvesting technology เข้าไป
เพื่อให้ Switch ดังกล่าว สามารถทำงานได้โดยอาศัยพลังงานจากแรงกดเท่านั้น
ด้วย Constraints ที่เกิดขึ้นนี้ (พลังงานที่จำกัด / ระยะเวลาที่ทำงานได้) ทำให้กระบวนการทำงานของ
Protocol จะเป็นอย่างไร และ จะมีประสิทธิภาพมากแค่ไหน เป็นเรื่องที่ต้องติดตามต่อไปครับ

30 24 กพ. 58 อ.จิตร์ทัศน์ approximate distance oracles []

approximate distance oracles เป็น data structures ที่ใช้ตอบคำถามว่าระยะทางสั้นที่สุดจาก u ไปยัง v มีค่าเป็นเท่าใด
ในงานที่สำคัญในปี 2001 ของ Thorup และ Zwick พวกเขาได้นำเสนออัลกอริทึมที่สร้าง data structures ที่มีขนาด O(kn^{1+1/k})
ที่สามารถตอบระยะทางจากคู่ของโหนดใด ๆ ได้โดยมีค่ามากกว่าความจริงไม่เกิน 2k-1 เท่า อัลกอริทึมสำหรับสร้างทำงานในเวลา O(kmn^{1/k}).
อัลกอริทึมนี้มีจุดเด่นที่ความง่าย ผมจะนำเสนออัลกอริทึมและ data structures ดังกล่าว พร้อมทั้งพิสูจน์คุณสมบัติตามที่ระบุข้างต้น
นอกจากนี้จะยัง review งานอื่น ๆ ที่พัฒนาต่อมาจากงานนี้ด้วย

31 10 มีค. 58 อ.ภารุจ หาดทรายสีดำ [30]

หลังจากที่ไมโครโปรเซสเซอร์มีสมรรถนะเพิ่มขึ้นอย่างต่อเนื่องแบบทวีคูณมาเป็นเวลากว่า 50 ปี ได้เกิดจุดเปลี่ยนอย่างกระทันหันในราวปี 2005
ที่สมรรถนะต่อตัวโปรเซสเซอร์ไม่สามารถเพิ่มขึ้นได้อีก สิ่งที่เราได้กลับมาหลังจากนั้นเป็นโปรเซสเซอร์ที่มีโปรเซสเซอร์ย่อยหลายตัวรวมอยู่ด้วยกัน (multi-core CPU)
และแนวโน้มในอนาคตบ่งว่าเราจะยิ่งมีโปรเซสเซอร์ย่อยเหล่านี้เพิ่มเป็นทวีคูณ (many-core CPU) แต่อนาคตที่เป็นไปในทิศทางนี้เริ่มไม่สดใสเสียแล้ว
เพราะเรากำลังเผชิญกับปัญหา "หาดทรายสีดำ" (Dark Silicon)

Grad-Talk ในวันนี้จะพูดถึงปัญหานี้และแนวทางในการแก้ไขโดยใช้ฮาร์ดแวร์แบบอนุรักษ์ (conservation cores)

32 24 มีค. 58 อ.ธนาวินท์ Time Series Motif [31][32][33]

ผมจะมาพูดเรื่องนี้ Time Series Motif ซึ่งเป็นส่วนที่เหมือนกันใน Time Series ครับ
โดยจะนำมาจาก Tutorial ของคุณ A. Mueen และ E. Keogh ครับ
เรามีเวลาประมาณครึ่งชม. ถึง 40 นาที ผมคงไม่ได้ลงในรายละเอียดอะไรครับ (เพราะผมก็ไม่ได้รู้มากนักครับ ^____^)

เพื่อเรียกน้ำย่อยครับ [34]

33 7 เมย. 58 อ.ชัยพร cooperative communication และ cooperative routing [35]

เป็นที่ทราบดีกว่าการสื่อสารข้อมูลโดยช่องสัญญาณร่วมกันนั้นจำเป็นต้องมีกลไกควบคุมการเข้าใช้สื่อให้มีผู้ส่งสัญญาณไม่เกิน 1 คนในช่วงเวลาหนึ่ง ๆ
ไม่เช่นนั้นแล้วจะเกิดการ "ปะทะ" กันของสัญญาณขึ้น ส่งผลทำให้การสื่อสารไม่สัมฤทธิ์ผล อย่างไรก็ตามหากผู้ส่งร่วมมือกันเพื่อปล่อยสัญญาณ
ในรูปแบบที่"ปรองดอง"กัน (cooperative communication) จะให้ผลในทางตรงกันข้าม สถานีที่เคยจัดว่าอยู่ไกลเกินเอื้อมสามารถสื่อสารข้อมูลกับที่เหลือได้
ส่วนที่เคยเอื้อมถึงอยู่แล้วก็สามารถรับข้อมูลได้ด้วยพลังงานส่งรวมที่ต่ำลง โมเดลการสื่อสารข้อมูลระดับล่างที่เปลี่ยนไปนี้นำมาซึ่งความท้าทายในการออกแบบอัลกอริทึมระดับบน
เช่นการหาเส้นทาง (cooperative routing) ซึ่งไม่สามารถหาคำตอบได้ด้วยอัลกอริทึม shortest-path ง่าย ๆ ได้อีกต่อไป

34 21 เมย. 58 คุณสุชา
(แขกรับเชิญพิเศษ) 		Achieving Utility-Delay-Reliability Tradeoff in Stochastic Network Optimization with Finite Buffers [36] [37]

This talk has two parts. The first part introduces a state of the art technique called ``stochastic network optimization.
 The technique is used to stabilize queuing systems, including but not limited to communication networks,
task scheduling problems, and smart grids. A particular queuing system is formulated with an objective function
and queue stability constraints. A ``drift-plus-penalty algorithm (including MaxWeight and Backpressure algorithms)
 is applied to solve the problem. Depending on the problem structure, the algorithm can be implemented distributively.
The drift-plus-penalty algorithm is proven to achieve [O(1/V), O(V)] utility and delay trade-off,
where V is the algorithm parameter.

The second part considers recent results to be presented at IEEE INFOCOM 2015. A ``floating-queue algorithm
 is proposed as a technique that allows the stochastic network optimization to be implemented with finite buffers
at the cost of packet drops. Further, the buffer size requirement is significantly smaller than previous works in this area.
With a finite buffer size of B packets, the proposed algorithm achieves within of the optimal utility
while maintaining average per-hop delay of O(B) and an average per-hop drop rate of .
From an implementation perspective, the floating-queue algorithm requires little modification of
the drift-plus-penalty algorithm. As a result, the floating-queue algorithm inherits the distributed
and low complexity nature of the drift-plus-penalty algorithm.

35 12 พค. 58 อดิศักดิ์ online learning problem / sequential decision problem [38] [39]

เป็นปัญหาที่เราต้องตัดสินใจเลือกกระทำการ(action)อย่างใดอย่างหนึ่งเป็นรอบๆ โดยหลังจากที่เราตัดสินใจในแต่ละรอบจะมี feedback
กลับมาว่าบอกว่า action ที่เลือกไปในรอบนั้นๆดีหรือไม่ดีอย่างไร ยกตัวอย่างเช่น ในแต่ละวันนายAจะต้องเลือกเส้นทาง(action) เพื่อเดินทางจากบ้านไปยังที่ทำงาน
หลังเดินทางถึงที่ทำงาน A จะรู้เวลาในการเดินทาง(feedback)ของเส้นทางที่ใช้ในวันนั้นๆ
สำหรับปัญหานี้เราต้องการหาวิธีการเลือกที่รับประกันได้ว่าท้ายที่สุดแล้วสิ่งที่เราเลือกไปนั้นดี

เราสามารถโมเดลปัญหานี้ตามรูปแบบของ feedback ได้ 2 แบบดังนี้
1) full information feedback สมมติให้ในแต่ละรอบจะมีfeedbackของทุกๆactionกลับมา และ
2) partial information feedback ในแต่ละรอบเราจะได้รับเพียงfeedback ของactionที่เราเลือกเท่านั้น

ปัญหาในรูปแบบนี้เราเรียกว่า multi-armed bandit problem

ผมจะขอรวบยอดพูดถึงทั้ง2รูปแบบข้างต้นผ่านทางปัญหา "online pricing" หรือ "การตั้งราคาแบบออนไลน์"
โดยผมจะอธิบายรวมถึงพิสูจน์ประสิทธิภาพของอัลกอริทึมพื้นฐานสำหรับทั้ง2รูปแบบของปัญหาดังกล่าว

36 9 มิย. 58 อรรถกร Single-source unsplittable flow [40] [41] [42]

Single-source unsplittable flow สำหรับกราฟมีทิศทางที่มี edge capacity เป็นจำนวนจริงบวก ซึ่งระบุโหนดต้นทาง(โหนดเดียว)
และปลายทางที่มีปริมาณการร้องขอจำนวน สำหรับแต่ละปลายทางเราต้องการหา path จากต้นทางไปปลายทางเพื่อรองรับปริมาณการร้องขอ
โดยทุก edge ปฏิบัติตาม capacity constraint

ในปี 1996 Jon Kleinberg [1] ได้นำเสนอปัญหาเกี่ยวกับ single-source unsplittable flow
และได้แสดง constant-factor approximation algorithm แรก ซึ่งต่อมา Stavros Kolliopoulos และ Clifford Stein
ได้พัฒนา algorithm ที่ให้ bound ที่ดีขึ้น [2] ก่อนที่ Yefim Dinitz, Naveen Garg และ Michel X. Goemans
จะตีพิมพ์ On the Single-Source Unsplittable Flow Problem ซึ่งให้ bound ที่ดีที่สุดจนถึงปัจุบัน และจะเป็นเนื้อหาหลักสำหรับการพูดครั้งนี้ครับ

37 23 มิย. 58 ศุภณัฐ Pairing-based cryptography and its application in identity-based encryption [43] [44]

pairing เป็นเครื่องมือที่สำคัญในการออกแบบ cryptographic protocol ในสมัยใหม่ โดยอาศัยคุณสมบัติที่สำคัญของ pairing
identity-based encryption(IBE) เป็นตัวอย่างหนึ่งที่สามารถสร้างมาจาก pairing โดยเป็น encryption ที่ใช้ public/private key
แต่มีคุณลักษณะพิเศษคือ public key จะเป็นอะไรก็ได้ตามที่เราเลือกเช่น ชื่อจริง หรือ อีเมล แทนที่จะใช้ public key ที่เป็น bit string ยาวๆ
ผมจะพูดถึงการสร้าง IBE จาก pairing ทั้งหมดสองวิธี วิธีแรกเป็นของ Boneh-Frankin[1] อีกวิธีเป็นของ Boneh-Boyen[2]
ต่อจากนั้นจะพูดถึง Anonymous IBE ซึ่งเป็นการใช้ IBE โดยที่ข้อความที่ถูก encrypt นั้นเราจะไม่รู้ว่าปลายทางของข้อความนั้นไปที่ไหน
และนอกจาก Anonymous IBE ก็จะพูดคร่าวๆเกี่ยวกับ HIBE,ABE

ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=Grad_talks&oldid=55472"