MONDAY APRIL 19 next Program DAY TWO

SESSION C - LONG TALKS 9:00 - 10:30
9:00 Improved Randomized Algorithms for 3-SAT Kazuo Iwama, Tadashi Takai and Suguru Tamaki.
9:30 Bounded-Curvature Shortest Paths through a Sequence of Points Xavier Goaoc, Hyo-Sil Kim and Sylvain Lazard.
10:00 A New Ranking Scheme of the GSP Mechanism with Markovian Users Xiaotie Deng and Jiajin Yu.


Coffee break

SESSION 5A - COMPLEXITY 10:50 - 11:50
10:50 SAT CNF Encoding with Multi-modeling Tomohiro Sonobe and Mary Inaba.
11:10 The Size and Width of Boolean Circuits Hiroki Morizumi.
11:30 Point-Set Embeddings of Plane 3-Trees Rahnuma Islam Nishat, Debajyoti Mondal and Md. Saidur Rahman.

SESSION 5B - GAME THEORY 10:50 - 11:50
10:50 An algorithmic analysis of the Honey-Bee game Rudolf Fleischer and Gerhard J. Woeginger.
11:10 On the locker problem with empty lockers David Avis, Luc Devroye and Kazuo Iwama.
11:30 Quantum Counterfeit Coin Problems Kazuo Iwama, Harumichi Nishimura, Rudy Raymond and Junichi Teruyama.


Short break

11:55 Keeping jigsaws connected Johan Oppen.
12:15 The perimeter of fat objects Prosenjit Bose, Otfried Cheong and Vida Dujmovic.
12:35 Skyline Queries in Metric Space Wanbin Son and Hee-Kap Ahn.

SESSION 6B - (RANDOM) WALKS 11:55 - 12:55
11:55 The Cover Time of Random Walks on Trees can be an Arbitrary Order Yoshiaki Nonaka, Hirotaka Ono and Masafumi Yamashita.
12:15 A Linear Cover Time of Multiplex Random Walks Yusuke Hosaka, Hirotaka Ono and Masafumi Yamashita.
12:35 Hide-and-Seek: A Linear Time Algorithm for Polygon Walk Problems Atlas F. Cook IV, Chenglin Fan and Jun Luo.