みなさま，

１月３０日のメール（このメールの最後にあるもの）でお伝えしました スケジュールの最新版をみなさまの参考のためお伝えします。

主な変更点は、TBAとなっていたいくつかの講演タイトルが 決定したことです。

参加ご検討くださるようお願いします。

垂井 -------------------------------- Mar13(Wed) Satellite Mini-Workshop, Shinagawa

venue: Kyoto Univ Shinagawa Office, Shinagawa (in: Intercity Shinagawa Building A, 27th floor) http://www.kyoto-u.ac.jp/ja/tokyo-office http://goo.gl/aCgSE registration not necessary; no participation fee; everybody is welcome organizers: Yoshio Okamoto (UEC), Suguru Tamaki (Kyoto U), Jun Tarui (UEC)

each talk will have a 15-min break in the middle 10:30--12:15 David Zuckerman: Randomness Extraction: A Survey 12:15--13:40 lunch (on your own) 13:40--15:25 Ran Raz: Parallel Repetition of Two Prover Games: A Survey 15:25--15:45 break 15:45--17:30 Noam Nisan: Algorithmic Mechanism Design: Multi-unit Auctions 18:00-- impromptu dinner party at Shinagawa -------------------------------

Tokyo Complexity Workshop (Main Workshop): venue: Shinagawa Prince Hotel, Main Tower 8th floor, Room: "Turquoise 8" http://www.al.ics.saitama-u.ac.jp/elc/ws/ http://goo.gl/aCgSE fee for reception/banquet; no fee otherwise; please register in all cases

Mar14(Thu) 13:20--13:30 opening 13:30--14:20 Umesh Varirani: Quantum Hamiltonian Complexity: through the computational lens 14:20--14:35 break 14:35--15:25 Rahul Jain: TBA 15:25--15:40 break 15:40--16:30 Pavel Pudlak: Polynomial Hierarchy and Bounded Arithmetic Hierarchy. 16:30--16:45 break 16:45--17:35 Ryan O'Donnell: Approximability and Proof Complexity 18:00--20:00 reception

Mar15(Fri) 09:00--09:50 Noam Nisan: Selling Two Objects (in Three Models) 09:50--10:15 break 10:15--11:05 Ketan Mulmuley: The GCT Chasm 11:05--11:30 break 11:30--12:20 Joshua Grochow: Geometric Complexity Theory unifies and generalizes many known lower bounds (an introduction to GCT) 12:20--14:00 lunch (on your own) 14:00--14:50 Shachar Lovett: The probabilistic method - new frontiers 14:50--15:15 break 15:15--16:05 Zeev Dvir: Locally Decodable Codes: recent progress and open problems 16:05--16:30 break 16:30--17:20 Luca Trevisan: Spectral Graph Theory

Mar16(Sat) 09:00--09:50 Raghu Meka: Recent Progress in Unconditional Derandomization 09:50--10:15 break 10:15--11:05 David Zuckerman: Pseudorandomness from Shrinkage 11:05--11:30 break 11:30--12:20 Irit Dinur: TBA 12:20--14:00 lunch (lunch on your own) 14:00--14:50 Rocco Servedio: TBA 14:50--15:15 break 15:15--16:05 Pinyan Lu: Complexity Dichotomies of Counting Problems 16:05--16:30 break 16:30--17:20 Ran Raz: Interactive Channel Capacity 18:00--20:00 banquet

Mar17(Sun) 09:00--09:50 Valentine Kabanets: Yin and Yang of computing: From circuit lower bounds to compression and SAT algorithms, and back 09:50--10:05 break 10:05--10:55 Eric Allender: Strengthening the Link between Complexity Classes and Kolmogorov Complexity 10:55--11:10 break 11:10--12:00 Yuichi Yoshida: Robust approximation of CSPs: Universal algebra meets optimization --------------------------------

Mar17(Sun) Satellite Mini-Workshop on Geometric Complexity Theory(GCT)

venue: 2nd floor meeting room, Campus Innovation Center, Tamachi http://www.cictokyo.jp/access.html http://goo.gl/aCgSE registration not necessary; no participation fee; everybody is welcome organizers: Takeshi Tokuyama (Tohoku U), Susumu Ariki (Osaka U), Jun Tarui (UEC)

speakers: Ketan Mulmuley and Joshua Grochow

14:00--18:15 (with 3 breaks) 18:30-- impromptu dinner party at Tamachi -------------------------------

Mar19(Tue) Satellite Mini-Workshp, Kyoto venue: Room 111, RIMS, Kyoto Univ, Kyoto http://www.kurims.kyoto-u.ac.jp/en/access-01.html http://goo.gl/aCgSE registration not necessary; no participation fee; everybody is welcome organizers: Shin-ichi Tanigawa (RIMS), Suguru Tamaki (Kyoto U), Jun Tarui (UEC)

13:15--14:15 Raghu Meka: Beating the Union Bound via Gaussian Geometry 14:15--14:30 break 14:30--15:30 Zeev Dvir: Locally Decodable Codes: recent progress and open problems 15:30--15:45 break 15:45--17:15 Ketan Mulmuley: talk on geometric complexity theory 18:00-- impropmtu dinner party around Sanjo/Shijo-Kawara-machi --------------------------------

Speakers:

Eric Allender (Rutgers) www.cs.rutgers.edu/~allender/ Irit Dinur (Weizmann) www.wisdom.weizmann.ac.il/~dinuri/ Zeev Dvir (Princeton) www.cs.princeton.edu/~zdvir/ Josh Grochow (U Toronto) www.cs.toronto.edu/~jgrochow/ Rahul Jain (Nat Univ Singapore) www.comp.nus.edu.sg/~rahul/ Valentine Kabanets (Simon Fraser) www.cs.sfu.ca/~kabanets/ Shachar Lovett (UCSD) https://sites.google.com/site/shacharlovetthomepage/ Pinyan Lu (Microsoft Research Asia and Shanghai Jiao Tong Univ) http://research.microsoft.com/en-us/people/pinyanl/ Raghu Meka (Princeton, IAS) www.math.ias.edu/~raghu/ Ketan Mulmuley (Chicago) www.cs.uchicago.edu/people/mulmuley Noam Nisan (Hebrew U) www.cs.huji.ac.il/~noam/ Ryan O'Donnell (CMU) www.cs.cmu.edu/~odonnell/ Pavel Pudlak (Math Institute of Czech Republic) www.math.cas.cz/~pudlak/ Ran Raz (Weizmann) www.wisdom.weizmann.ac.il/~ranraz/ Rocco Servedio (Columbia) www.cs.columbia.edu/~rocco/ Luca Trevisan (Stanford) http://theory.stanford.edu/~trevisan/ Umesh Vazirani (UC Berkeley) http://www.cs.berkeley.edu/~vazirani/ Yuichi Yoshida (National Institute of Informatics, Tokyo) http://research.nii.ac.jp/~yyoshida/ David Zuckerman (U Texas, Austin) www.cs.utexas.edu/~diz/

At 10:08 13/01/30, Jun Tarui wrote:

みなさま，

電通大の垂井です．

計算限界解明プロジェクト http://www.al.ics.saitama-u.ac.jp/elc/ のキックオフメイン集会とサテライト集会に関して プログラム作成と企画の主担当をしています．

まだ調整中の部分もあるのですが，みなさまの参考のために 現時点での予定をお伝えします．ぜひ参加ご検討ください．

サテライト集会： 参加費なしで登録不要です． 当日夕方に参加希望を現地で尋ねる形の懇親食事会を予定しています．

メイン集会： 参加費はなしですが，一部講演のみ聴講の場合でも 登録をお願いしています．登録締め切りは２月２８日です．

よろしくお願いします．

垂井淳

Exploring the Limits of Computation (ELC) Tokyo Complexity Workshop and Satellite Mini-Workshops: http://www.al.ics.saitama-u.ac.jp/elc/ws/

Mar13(Wed) Satellite Mini-Workshop, Shinagawa

venue: Kyoto Univ Shinagawa Office, Shinagawa http://www.kyoto-u.ac.jp/ja/tokyo-office http://goo.gl/aCgSE registration not necessary; no participation fee; everybody is welcome organizers: Yoshio Okamoto(UEC), Suguru Tamaki(Kyoto U), Jun Tarui(UEC)

each talk will have a 15-min break in the middle 10:30--12:15 TBA 12:15--13:40 lunch (on your own) 13:40--15:25 Ran Raz: Parallel Repetition of Two Prover Games: A Survey 15:25--15:45 break 15:45--17:30 Noam Nisan: Algorithmic Mechanism Design: Multi-unit Auctions 18:00-- impromptu dinner party at Shinagawa

Mar17(Sun) Satellite Mini-Workshop on Geometric Complexity Theory(GCT)

venue: 2nd floor meeting room, Campus Innovation Center, Tamachi http://www.cictokyo.jp/access.html http://goo.gl/aCgSE registration not necessary; no participation fee; everybody is welcome organizers: Takeshi Tokuyama(Tohoku U), Susume Ariki(Osaka U), Jun Tarui(UEC)

speakers: Ketan Mulmuley and Joshua Grochow

14:00--18:15 (with 3 breaks) 18:30-- impromptu dinner party at Tamachi

Mar19(Tue) Satellite Mini-Workshp, Kyoto venue: Room 111, RIMS, Kyoto Univ, Kyoto http://www.kurims.kyoto-u.ac.jp/en/access-01.html http://goo.gl/aCgSE registration not necessary; no participation fee; everybody is welcome organizers: Shin-ichi Tanigawa(RIMS), Suguru Tamaki(Kyoto U), Jun Tarui(UEC)

13:15--14:15 Raghu Meka: Beating the Union Bound via Gaussian Geometry 14:15--14:30 break 14:30--15:30 Zeev Dvir: Locally Decodable Codes: recent progress and open problems 15:30--15:45 break 15:45--17:15 Ketan Mulmuley: talk on geometric complexity theory 18:00-- impropmtu dinner party around Sanjo/Shijo-Kawara-machi

Tokyo Complexity Workshop (Main Workshop): tentative schedule as of Jan 30th venue: Shinagawa Prince Hotel, Main Tower 8th floor, Room: "Turquoise 8" http://www.al.ics.saitama-u.ac.jp/elc/ws/ http://goo.gl/aCgSE fee for reception/banquet; no fee otherwise; please register in all cases

Mar14(Thu) 13:20--13:30 opening 13:30--14:20 Umesh Varirani: Quantum Hamiltonian Complexity: through the computational lens 14:20--14:35 break 14:35--15:25 Rahul Jain: TBA 15:25--15:40 break 15:40--16:30 Pavel Pudlak: Polynomial Hierarchy and Bounded Arithmetic Hierarchy. 16:30--16:45 break 16:45--17:35 Ryan O'Donnell: Approximability and Proof Complexity 18:00--20:00 reception

Mar15(Fri) 09:00--09:50 Noam Nisan: Selling Two Objects (in Three Models) 09:50--10:15 break 10:15--11:05 Ketan Mulmuley: The GCT Chasm 11:05--11:30 break 11:30--12:20 Joshua Grochow: Geometric Complexity Theory unifies and generalizes many known lower bounds (an introduction to GCT) 12:20--14:00 lunch 14:00--14:50 Shachar Lovett: The probabilistic method - new frontiers 14:50--15:15 break 15:15--16:05 Zeev Dvir: Locally Decodable Codes: recent progress and open problems 16:05--16:30 break 16:30--17:20 Luca Trevisan: TBA

Mar16(Sat) 09:00--09:50 Raghu Meka: Recent Progress in Unconditional Derandomization 09:50--10:15 break 10:15--11:05 David Zuckerman: Pseudorandomness from Shrinkage 11:05--11:30 break 11:30--12:20 Irit Dinur: TBA 12:20--14:00 lunch 14:00--14:50 Rocco Servedio: TBA 14:50--15:15 break 15:15--16:05 Pinyan Lu: TBA 16:05--16:30 break 16:30--17:20 Ran Raz: Interactive Channel Capacity 18:00--20:00 banquet

Mar17(Sun) 09:00--09:50 Valentine Kabanets: Yin and Yang of computing: From circuit lower bounds to compression and SAT algorithms, and back 09:50--10:05 break 10:05--10:55 Eric Allender: Strengthening the Link between Complexity Classes and Kolmogorov Complexity 10:55--11:10 break 11:10--12:00 Yuichi Yoshida: Robust approximation of CSPs: Universal algebra meets optimization

Speakers:

Eric Allender (Rutgers) www.cs.rutgers.edu/~allender/ Irit Dinur (Weizmann) www.wisdom.weizmann.ac.il/~dinuri/ Zeev Dvir (Princeton) www.cs.princeton.edu/~zdvir/ Josh Grochow (U Toronto) www.cs.toronto.edu/~jgrochow/ Rahul Jain (Nat Univ Singapore) www.comp.nus.edu.sg/~rahul/ Valentine Kabanets (Simon Fraser) www.cs.sfu.ca/~kabanets/ Shachar Lovett (Princeton, IAS) https://sites.google.com/site/shacharlovetthomepage/ Pinyan Lu (Microsoft Research Asia and Shanghai Jiao Tong Univ) http://research.microsoft.com/en-us/people/pinyanl/ Raghu Meka (Princeton, IAS) www.math.ias.edu/~raghu/ Ketan Mulmuley (Chicago) www.cs.uchicago.edu/people/mulmuley Noam Nisan (Hebrew U) www.cs.huji.ac.il/~noam/ Ryan O'Donnell (CMU) www.cs.cmu.edu/~odonnell/ Pavel Pudlak (Math Institute of Czech Republic) www.math.cas.cz/~pudlak/ Ran Raz (Weizmann) www.wisdom.weizmann.ac.il/~ranraz/ Rocco Servedio (Columbia) www.cs.columbia.edu/~rocco/ Luca Trevisan (Stanford) http://theory.stanford.edu/~trevisan/ Umesh Vazirani (UC Berkeley) http://www.cs.berkeley.edu/~vazirani/ Yuichi Yoshida (National Institute of Informatics, Tokyo) http://research.nii.ac.jp/~yyoshida/ David Zuckerman (U Texas, Austin) www.cs.utexas.edu/~diz/