2012年 | |
1/8 - 10
| ITCS 2012 |
| 投稿〆切 : 2011/8/7 |
| Place : Cambridge, MA |
| (previously known as ICS)
|
1/16
| ALENEX-ANALCO 2012 |
| 投稿〆切 : 2011/10/3 |
| Place : The Westin Miyako, Kyoto, Japan |
| ALENEX
http://www.siam.org/meetings/analco12/
ANALCO
http://www.siam.org/meetings/analco12/
|
1/17 - 19
| SODA 2012 |
| 投稿〆切 : 2011/7/12 |
| Place : The Westin Miyako, Kyoto (京都), Japan |
| Short Abstract Submission and Paper Registration Deadline:
July 5, 2011, 4:59 PM EDT
|
1/30 - 2/1
| 冬のLAシンポジウム |
| Place : 京都大学数理解析研究所420号室 |
1/30 - 2/2
| CATS 2012 -- Computing: The Australasian Theory Symposium |
| 投稿〆切 : 2011/8/29 |
| Place : Melbourne, Australia |
| 投稿〆切が延長されました。8/15 -> 8/29。
|
2/15 - 17
| WALCOM 2012 (Workshop on Algorithms and Computation 2012) |
| 投稿〆切 : 2011/9/17 |
| Place : Dhaka, Bangladesh |
| 投稿〆切が延期されました。(9/10->9/17)
|
2/29 - 3/3
| STACS 2012 |
| 投稿〆切 : 2011/9/23 |
| Place : Paris, France |
| Invited Speakers:
- Martin Dietzfelbinger, Ilmenau
- Thomas Colcombet, Paris
- Shafi Goldwasser, MIT
|
3/4
| 日本OR学会 シンポジウム |
| Place : 政策研究大学院大学 |
3/5 - 6
| 2012 JAIST杯 ゲームアルゴリズム大会 |
| Place : JAIST 東京キャンパス(品川駅徒歩数分) |
3/6 - 8
| 情報処理学会 第74回全国大会 |
| 投稿〆切 : 2011/11/18 |
| Place : 名古屋工業大学 |
| 講演申込登録締切:2011年11月18日(金)19:00
原稿投稿締切 :2012年 1月13日(金)19:00
|
3/8
| 組合せゲーム・パズル ミニ研究集会 |
| 投稿〆切 : 2012/2/13 |
| Place : 大阪商業大学 |
| アミューズメント産業研究所の所蔵資料
http://ouc.daishodai.ac.jp/facilities/ams_labo/about.html
の見学も行います。
|
3/13
| 藤重悟教授 最終講義『劣モジュラ構造と離散最適化』 |
| Place : 京都大学数理解析研究所 420号室 |
| 16:00--17:30: 最終講義
終了後(18:00〜) 記念祝賀パーティが行われます。(要事前申込)
|
3/13 - 14
| 第4回 錯覚ワークショップ |
| Place : 明治大学駿河台キャンパス アカデミーコモン9階 講義室309A |
3/18
| 電子情報通信学会コンピュテーション研究会 |
| Place : 岐阜大 |
3/18 - 21
| TCC 2012 |
| 投稿〆切 : 2011/9/15 |
| Place : Taormina, Italy |
3/19 - 21
| EuroCG 2012 |
| 投稿〆切 : 2012/1/9 |
| Place : Assisi, Italy |
3/19 - 22
| 電子情報通信学会総合大会 |
| Place : 岐阜大 |
3/20 - 23
| 電子情報通信学会 総合大会 |
| Place : 岡山大学 津島キャンパス |
3/24
| 小島政和先生退官記念シンポジウム「数理最適化の 40 年と今後の展開」 |
| Place : 東京工業大学 大岡山キャンパス |
3/26
| 日本オペレーションズ・リサーチ学会 シンポジウム「災害対処の施策とOR」 |
| Place : 防衛大学校 |
3/26 - 30
| Logical Approaches to Barriers in Complexity II |
| Place : Cambridge, UK |
3/27 - 28
| 日本オペレーションズ・リサーチ学会 春期研究発表会 |
| Place : 防衛大学校 |
4/16 - 20
| LATIN 2012 |
| 投稿〆切 : 2011/9/23 |
| Place : Arequipa, Peru |
4/17 - 21
| ISCO 2012 (2nd International Symposium on Combinatorial Optimization) |
| 投稿〆切 : 2011/12/8 |
| Place : Athens, Greece |
| 投稿〆切が延長されました。新しい〆切は12/08です。
INVITED SPEAKERS
- Giorgio Ausiello, Universit� di Roma "La Sapienza"
- Christos Papadimitriou, UC Berkeley
- George Nemhauser, Georgia Tech
- Paolo Toth, Universit� di Bologna
Click to Continue ...
April 17-18: Spring School "Mathematical Programming and Design of Approximation Algorithms"
April 19-21: ISCO 2012
|
4/21 - 22
| AAAC 2012 (The 5th Annual Meeting of the Asian Association for Algorithms and Computation) |
| 投稿〆切 : 2012/2/1 |
| Place : Fudan University, Shanghai |
4/27
| COMP研 |
| Place : 大阪府立大学 |
5/10 - 12
| TURING CENTENNIAL CELEBRATION at PRINCETON |
| Place : PRINCETON, NJ, USA |
5/14
| COMP研 |
| 投稿〆切 : 2012/3/9 |
| Place : 愛媛大学 |
| アルゴリズム研究会と共同開催
|
5/16 - 21
| TAMC 2012 |
| 投稿〆切 : 2012/1/10 |
| Place : Beijing, China |
| Invited Speakers:
S Barry Cooper, Leeds
John Hopcroft, Cornell
Richard M. Karp, Berkeley
Jon Kleinberg, Cornell
Butler W. Lampson, Microsoft
Wei Li, BUAA
Click to Continue ...Andrew Chi-Chih Yao, Tsinghua
|
5/19 - 22
| STOC 2012 |
| 投稿〆切 : 2011/11/2 |
| Place : New York, USA |
6/4 - 6
| FUN 2012 (Sixth International Conference on FUN WITH ALGORITHMS) |
| 投稿〆切 : 2012/1/15 |
| Place : San Servolo Island, Venice, Italy |
6/12 - 13
| Workshop for Quasi-Monte Carlo and Pseudo Random Number Generation |
| Place : 東大駒場キャンパス数理科学棟 |
| url : https://sites.google.com/a/craft.titech.ac.jp/workshop-on-qmc-and-prng-2012-utms/ |
6/12 - 14
| COLT 2013 |
| 投稿〆切 : 2012/2/8 |
| Place : Princeton, NJ |
6/15 - 16
| The ACM Turing Centenary Celebration |
| Place : San Francisco, USA |
6/16 - 20
| SoCG 2012 (The 28th Symposium on Computational Geometry) |
| 投稿〆切 : 2011/11/22 |
| Place : University of North Carolina at Chapel Hill, NC, USA |
6/17 - 21
| SAT 2012 |
| 投稿〆切 : 2012/2/12 |
| Place : Trento, Italy |
| Abstract Submission: 05/02/2012
Invited Speakers:
- Aaron Bradley, Boulder
- Donald Knuth, Stanford
|
6/18 - 23
| TURING CENTENARY CONFERENCE: CiE 2012 - How the World Computes |
| 投稿〆切 : 2012/1/20 |
| Place : University of Cambridge |
| Submission Deadline for LNCS: Jan. 20, 2012
Submission Deadline for Informal Presentations: May 11, 2012
|
6/21
| COMP研 |
| 投稿〆切 : 2012/4/6 |
| Place : 北大 |
| ERATO湊離散構造処理系 初夏のワークショップ(6/22,23)と連続開催
|
6/21 - 23
| COCOON 2013 |
| 投稿〆切 : 2013/1/6 |
| Place : Hangzhou, China |
6/22 - 23
| ERATO湊離散構造処理系プロジェクト「2012年度 初夏のワークショップ」 |
| Place : 北大 |
| COMP研(6/21)と連続開催
|
6/23
| 離散数学1日研究集会(秋山仁先生 東京理科大学着任記念) |
| 投稿〆切 : 2012/5/25 |
| Place : 東京理科大学 8号館 832室 |
6/24 - 27
| INFORMS 2012 |
| 投稿〆切 : 2012/2/13 |
| Place : 北京(中国) |
| 投稿はアブストラクト(最大500文字)
|
6/25 - 27
| COLT 2012 |
| 投稿〆切 : 2012/2/14 |
| Place : Edinburgh, Scotland |
6/25 - 28
| LICS 2012 |
| 投稿〆切 : 2012/1/6 |
| Place : Dubrovnik, Croatia |
6/26 - 28
| CCC 2012 |
| 投稿〆切 : 2011/12/8 |
| Place : Porto, Portugal |
7/3 - 7
| CSR 2012 |
| 投稿〆切 : 2011/12/11 |
| Place : Nizhny Novgorod |
7/4 - 6
| SWAT 2012 |
| 投稿〆切 : 2012/2/24 |
| Place : Helsinki, Finland |
7/8 - 11
| EURO XXV (25TH EUROPEAN CONFERENCE ON OPERATIONAL RESEARCH) |
| 投稿〆切 : 2012/2/29 |
| Place : Vilnius, Lithuania |
7/9
| [elc] ELC 発足準備会 |
| Place : 東京工業大学 |
| 詳細は、ELC ウェブサイトをご覧ください
|
7/9 - 13
| ICALP 2012 |
| 投稿〆切 : 2012/2/21 |
| Place : University of Warwick, UK |
| Invited Speakers:
- Gilles Dowek, INRIA Paris
- Kohei Honda, Queen Mary London
- Stefano Leonardi, Sapienza University of Rome
- Daniel A. Spielman, Yale
- Berthold Voecking, RWTH Aachen
Click to Continue ...
|
7/10 - 11
| WAAC 2012 |
| 投稿〆切 : 2012/5/16 |
| Place : 国立情報学研究所 |
7/17 - 19
| LA シンポジウム |
| Place : 天橋立 |
7/19 - 20
| MATCH-UP 2012 (the Second International Workshop on Matching Under Preferences) |
| 投稿〆切 : 2012/3/19 |
| Place : Budapest, Hungary |
7/22 - 26
| AAAI-12 |
| Place : Toronto, Ontario, Canada |
7/28 - 30
| APORS2012 (9TH TRIENNIAL CONFERENCE OF ASSOCIATION OF ASIA-PACIFIC OPERATIONAL RESEARCH SOCIETIES) |
| 投稿〆切 : 2012/4/30 |
| Place : 西安(中国) |
7/30 - 31
| 第25回 回路とシステムワークショップ |
| 投稿〆切 : 2012/4/13 |
| Place : 淡路夢舞台国際会議場 |
8/8 - 10
| CCCG 2012 (24th Canadian Conference on Computational Geometry) |
| 投稿〆切 : 2012/5/7 |
| Place : Charlottetown, Prince Edward Island, Canada |
8/9 - 11
| 離散数学とその応用研究集会2012 |
| 投稿〆切 : 2012/7/23 |
| Place : 茨城大学日立キャンパスE5棟8階イノベーションルーム |
8/15 - 17
| APPROX 2012 + RANDOM 2012 |
| 投稿〆切 : 2012/4/20 |
| Place : MIT, Boston, USA |
8/19 - 24
| ISMP 2012 (The 21st International Symposium on Mathematical Programming) |
| 投稿〆切 : 2012/4/15 |
| Place : ベルリン |
8/20 - 22
| COCOON 2012 |
| 投稿〆切 : 2012/2/18 |
| Place : Sydney, Australia |
8/25
| 離散構造処理系とその未来 ― JST ERATO 湊離散構造処理系プロジェクト 2012 公開シンポジウム |
| Place : 日本科学未来館 7F みらいCANホール |
| - 公開シンポジウム
- 参加ご希望の方は、湊離散構造処理系プロジェクト宛てに「御氏名」「御所属」「懇親会参加有無」を記載のうえ、
メールにてお申し込みください。(メールアドレスはシンポジウムのページに記載されております。)
|
8/27 - 31
| MFCS 2012 |
| 投稿〆切 : 2012/4/20 |
| Place : Bratislava, Slovakia |
9/3
| COMP研 |
| 投稿〆切 : 2012/6/29 |
| Place : 法政大学小金井キャンパス |
| FITの前日に同じキャンパスで開催します。
|
9/3
| [elc] 電子情報通信学会 コンピュテーション研究会 ELC招待講演 |
| Place : 法政大学 |
9/4
| e-サイエンス:超大規模実問題に挑戦するアルゴリズムと計算技術(FIT2012イベント企画) |
| Place : 第2イベント会場 (法政大学 小金井キャンパス 西館B1F 工学部マルチメディアホール) |
9/4 - 6
| FIT2012 |
| Place : 法政大学 小金井キャンパス |
9/5 - 7
| [elc] ELC Mini-Workshop (B01) |
| Place : 京都大学 |
9/5 - 8
| ICGI 2012 (11th International Conference on Grammatical Inference) |
| 投稿〆切 : 2012/6/8 |
| Place : Washington, DC, USA |
| 2012.6.8はshort paperの〆切(延長されています)
|
9/10 - 12
| ESA 2012 |
| 投稿〆切 : 2012/4/22 |
| Place : Ljubljana, Slovenia |
9/11
| 日本OR学会 シンポジウム |
| Place : 南山大学名古屋キャンパス |
9/12 - 13
| 日本OR学会秋季研究発表会 |
| 投稿〆切 : 2012/6/29 |
| Place : Winc Aichi (名古屋駅前) |
9/12 - 14
| IPEC 2012 |
| 投稿〆切 : 2012/6/19 |
| Place : Ljubljana, Slovenia |
9/18 - 19
| 第5回錯覚ワークショップ |
| Place : 明治大学駿河台キャンパス リバティタワー |
9/19 - 21
| GD 2012 (20th International Symposium on Graph Drawing) |
| 投稿〆切 : 2012/6/8 |
| Place : Redmond, Washington, USA |
9/19 - 21
| 列挙合宿 |
| Place : 群馬大学伊香保研修所 |
9/24 - 26
| [elc] 計算量理論の秋学校 |
| Place : かんぽの宿 熱海 |
9/24 - 27
| [elc] 暗号理論秋学校 |
| Place : 河口湖セントビレッヂ |
9/27 - 28
| RAMPシンポジウム |
| Place : 東北大学 |
10/2
| [elc] ELC Seminar (Lance Fortnow) |
| Lance Fortnow 氏の短期間来日の機会に,氏の講演を中心に何人かの方に発表して頂くWSを企画しました.ぜひ,おいでください.
場所:東工大大岡山キャンパス 西8号館W棟10Fコラボレーションルーム
※道順は渡辺研のウェブのアクセスから
http://www.is.titech.ac.jp/~watanabe/lab/pukiwiki4lab/index.php?howtoget-jp
日時:10月2日(火)13時30分~18時頃
※終了後懇親会も予定しています.こちらは予約もあるので参加希望者は連絡して下さい
Click to Continue ...
ホスト:河内亮周 kawachi(at)is.titech.ac.jp
|
10/8 - 12
| CP 2012 |
| 投稿〆切 : 2012/4/23 |
| Place : Quebec City |
10/20 - 23
| FOCS 2012 |
| 投稿〆切 : 2012/4/4 |
| Place : New Brunswick, USA |
10/28 - 29
| [elc] ELC Mini-Workshop (B02, B03) |
| Place : 秋保温泉 |
| 場所: 秋保温泉 ホテル瑞鳳
予定:
10月28日 13時~17時 話題提供セッション(9時から自由形式のDiscussion)
10月29日 9時~11時半 問題解決セッション
交通:
Click to Continue ...仙台駅からバスがあります。
ホテルの無料送迎バスはありますが、9時と15時(予約制)です。
宮城交通バス(仙台駅から55分、780円)をつかうか、
希望者多数の場合は(割り勘で)送迎バスを有料で出してもらいます。
参加希望の方は、下記情報を徳山豪まで9月10日までにご連絡ください。
氏名
所属
学生の場合は学年
到着予定時間
有料送迎バス(12時仙台駅発予定)を使いたいかどうか。
話題提供があれば、そのテーマ。 特になくてもOK
(話題は計算理論に関係すれば、COMPLEXITYに限定しませんが、
成果発表ではなく、問題提起が望ましいです。)
|
10/29 - 31
| ALT 2012 |
| 投稿〆切 : 2012/5/17 |
| Place : Lyon, France |
10/31
| 電子情報通信学会コンピュテーション研究会 |
| 投稿〆切 : 2012/8/6 |
| Place : 東北大 |
11/2
| [elc] ELC Seminar (Laszlo Egri, Yuichi Yoshida) 11/9 との連続開催 |
| Place : 東京工業大学大岡山キャンパス西8号館E棟E1011 |
| Time: 1:30pm -, November 2
Place: Room E1011, W8 building, Tokyo Institute of Technology
Speaker: Laszlo Egri (McGill Univ.)
Title: The Complexity of the List Homomorphism Problem for Graphs
Abstract:
We completely classify the computational complexity of the list
Click to Continue ...H-colouring problem for graphs (with possible loops) in combinatorial
and algebraic terms: for every graph H, the problem is either
NP-complete, NL-complete, L-complete or is first-order definable;
descriptive complexity equivalents are given as well via Datalog and
its fragments. Our algebraic characterisations match important
conjectures in the study of constraint satisfaction problems.
Speaker: Yuichi Yoshida (NII & PFI)
Title: An Algebraic Characterization of Testable Boolean CSPs
Abstract:
Given an instance I of a CSP, a tester for I distinguishes assignments satisfying I
from those which are far from any assignment satisfying I.
The efficiency of a tester is measured by its query complexity,
the number of variable assignments queried by the algorithm.
In this paper, we characterize the hardness of testing Boolean CSPs
in terms of the algebra generated by the relations used to form constraints.
In terms of computational complexity, we show that if a non-trivial Boolean CSP
is sublinear-query testable (resp., not sublinear-query testable), then the CSP is in NL
(resp., P-complete, ⊕L-complete or NP-complete) and that if a sublinear-query testable
Boolean CSP is constant-query testable (resp., not constant-query testable),
then counting the number of so- lutions of the CSP is in P (resp., #P-complete).
Also, we conjecture that a CSP instance is testable in sublinear time
if its Gaifman graph has bounded treewidth.
We confirm the conjecture when a near-unanimity operation is a polymorphism of the CSP.
Contact: Akinori Kawachi (Tokyo Institute of Technology)
|
11/9
| [elc] ELC Seminar (Kazuhisa Seto) 11/2との連続開催 |
| Place : 東京工業大学大岡山キャンパス西8号館E棟E1011 |
| Speaker: Kazuhisa Seto (The University of Electro-Communications)
Title: An Introduction to Circuit Complexity and Satisfiability Algorithms on Formulas
Time: 1:30pm -, November 9
Place: Room E1011, W8 building, Tokyo Institute of Technology
Abstract:
In this talk, we give a basic introduction to circuit complexity and
satisfiability algorithms on formulas. At first, we show Subbotovskaya's
Click to Continue ...technique for proving the lower bound of parity function on formulas.
Next, we introduce Santhanam's satisfiability algorithm for de morgan
formulas by using Subbotovskaya's technique. Finally, we give our
satisifiablity algorithm for formulas over the full binary basis by
extension of Santhanam's algorithm.
|
11/12 - 13
| [elc] ELC Mini-Workshop (C02) |
| Place : 名古屋大学 |
| C02班による年次集会です.
日時: 11月12日~11月13日
場所: 名古屋大学
連絡先: 河内 亮周(http://www.is.titech.ac.jp/~kawachi/index-j.html)
Click to Continue ... |
11/15
| 続・娯楽のOR(OR学会関西支部講演会) |
| Place : 大阪府立大学 中百舌鳥キャンパス A12棟 サイエンスホール |
11/21
| 芸術支援数学の挑戦 |
| Place : 明治大学駿河台キャンパスリバティタワー1166教室 |
11/22
| [elc] Center for ELC opening |
| Place : Center for ELC (Tamachi) |
| We are planning to have a small opening event for
the Center for ELC (Tamachi office) as follows. If you are
interested in join us, please give a message to Ms. Kishimoto
(CELC staff) via email by the end of Oct.
Opening Event:
Nov. 22nd, 16:30 -
Click to Continue ... * some small seminar (very informal)
* maybe going out somewhere for dinner
Place: Tokyo Tech CIC 5F, 502
http://www.cictokyo.jp/access.html
Contact: kimiko(at)is.titech.ac.jp
|
11/30
| [elc] ERATO河原林巨大グラフプロジェクト & ELC合同講演会 (Arnab Bhattacharyya & Mikkel Thorup) |
| Place : キャンパスイノベーションセンター東京(東工大田町キャンパス) |
| ERATO河原林巨大グラフプロジェクトとELCの合同講演会を以下の要領で開催いたします.奮ってご参加下さい.
日時: 11/30(金) 15:30-17:30
場所: キャンパスイノベーションセンター東京 2階多目的室4
15:30-16:30
Speaker: Arnab Bhattacharyya (DIMACS/Rutgers)
Click to Continue ...Title: Every locally characterized affine-invariant property is testable
Abstract:
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a
property of functions on F^n that is closed under taking affine
transformations of the domain. We prove that all affine-invariant property
having local characterizations are testable. In fact, we show a
proximity-oblivious test for any such property P, meaning that there is a
test that, given an input function f, makes a constant number of queries to
f, always accepts if f satisfies P, and rejects with positive probability
if the distance between f and P is nonzero. More generally, we show that
any affine-invariant property that is closed under taking restrictions to
subspaces and has bounded complexity is testable.
We also prove that any property that can be described as the property of
decomposing into a known structure of low-degree polynomials is locally
characterized and is, hence, testable. For example, whether a function is a
product of two degree-d polynomials, whether a function splits into a
product of d linear polynomials, and whether a function has low rank are
all examples of degree-structural properties and are therefore locally
characterized.
Our results depend on a new Gowers inverse theorem by Tao and Ziegler for
low characteristic fields that decomposes any polynomial with large Gowers
norm into a function of low-degree non-classical polynomials. We establish
a new equidistribution result for high rank non-classical polynomials that
drives the proofs of both the testability results and the local
characterization of degree-structural properties.
Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar
Lovett.
16:30-17:30
Speaker: Mikkel Thorup (AT&T Labs Research)
Title: The Power of Tabulation Hashing
Abstract:
Randomized algorithms are often enjoyed for their simplicity, but the hash functions
used to yield the desired theoretical guarantees are often neither simple nor practical.
Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees.
The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting
of c characters. We initialize c tables T1,…,Tc mapping characters to random hash codes.
A key x=(x1,…,xc) is hashed to T1[x1]⊕⋯⊕Tc[xc], where ⊕ denotes xor. While this scheme is not
even 4-independent, we show that it provides many of the guarantees that are normally obtained
via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating
set intersection, and cuckoo hashing. We shall also discuss a twist to simple tabulation
that leads to extremely robust performance for linear probing with small buffers.
|
12/5 - 7
| ICNC'12 (The Third International Conference on Networking and Computing) |
| 投稿〆切 : 2012/7/23 |
| Place : 沖縄県男女共同参画センター てぃるる (沖縄県那覇市西3-11-1) |
| 渡邉敏正先生の定年退職記念ワークショップ (Workshop on Computational Complexity Analysis
and Algorithm Design for Combinatorial Optimization Problems) が開催される予定です。
|
12/6
| [elc] ELC Mini-Workshop (暗号理論) |
| Place : Center for ELC |
| Program
1:30-2:00
Speaker: Hirotoshi Takebe (Tokyo Inst. Tech.)
Title: Symmetric-Key Encryption Scheme with Multi-Ciphertext Non-malleability
Abstract:
A standard notion of non-malleability
Click to Continue ...is that an adversary cannot forge a ciphertext $c'$
from a single valid ciphertext $c$ for which
a plaintext $m'$ of $c'$ is meaningfully
related to a plaintext $m$ of $c$.
The {\em multi-ciphertext non-malleability} is a
stronger notion; an adversary is allowed to
obtain multiple ciphertexts $c_1,c_2,...$
in order to forge $c'$.
We provide an efficient symmetric-key encryption scheme with
an information-theoretic version of
the multi-ciphertext non-malleability
in this paper by using $\ell$-wise almost independent
permutations of Kaplan, Naor, and Reingold.
2:00-2:30
Speaker: Vorapong Suppakitpaisarn (U. Tokyo)
Title: Generalized Analysis Methods for Efficiency of Representations for Elliptic Curve Scalar Multiplication
Abstract:
In this talk, we introduce the algorithmic analysis approach for
elliptic curve scalar multiplication implemented using various kinds
of number representations. Scalar multiplication is the bottleneck
operation of elliptic curve cryptography, and there are many works
proposed to speed-up the operation including the improvement on how we
represent the scalar. Many number representations, which are designed
to optimize the computation time in a specific type of elliptic curve
implementation, are too complicated to be analyzed using mathematical
approach. We devise the method based on dynamic programming scheme,
automatically-generated Markov chain, and the generic property of most
representations. Our focus in this presentation is the r-radix
representation for r > 2, which is practically used in pairing-based
cryptography. We found an interesting relationship between the memory
usage and the average speed of optimal scalar multiplication.
2:30-2:50
Break
2:50-3:50
Speaker: Takeshi Koshiba (Saitama Univ.)
Title: On Unidirectional Public Discussion in Secure Message Transmission
Abstract:
We consider the possibility and the limitation of secure message
transmission (SMT) in the "unidirectional" public discussion (PD)
model. Let epsilon be the privacy parameter and delta be the
reliability parameter, where smaller values are better.
[K-Sawada 2010] has shown that the privacy and the reliability
are not compatible in the SMT-PD model when only backward public
channel is avaiable.
Roughly speaking, epsilon + delta must be close to 1.
Also, we have shown that delta must be larger than approximately 1/2
when only foreward public channel is avaiable, while we provide an
upper-bound protocol achieving approximately delta < t/n, where
n is the number of channels and t |
12/6 - 8
| TJJCCGG 2012 (Thailand-Japan Joint Conference on Computational Geometry and Graphs) |
| Place : Bangkok, Thailand |
| JCDCGシリーズの一つです。
|
12/7
| [elc] ELC Seminar (Manabu Hagiwara) |
| Place : Center for ELC |
| 産業技術総合研究所の萩原学氏をお招きして講演会を開催いたします.
線形計画法と符号理論の関係についてお話いただけるということですので
特に関係の深いチームの方々はご参加を検討いただけると幸いです.
よろしくお願いいたします.
日時:12月7日(金)16:00-17:00
※終了後に懇親会を予定しております.
Click to Continue ...場所:計算限界研究センターセミナー室
講演者:萩原学(産業技術総合研究所)
講演タイトル:
コンパクトグラフと線形計画法による置換符号
Compact Graph and Linear Programming for Permutation Codes
講演概要:
置換符号は符号理論の話題の一つである.
これまでこの符号は,電力線搬送通信向きとして研究されてきた.
この符号の特別なケースである,ランク変調と呼ばれる方式は,
近年,フラッシュメモリの誤り訂正に応用できる可能性が指摘され,
注目が高まっている.
本講演では,置換符号やランク変調のコンセプトについて解説する.
また,それらの誤り訂正アルゴリズムとして線形計画法を適用する為の,
置換符号とランク変調の構成法について議論したい.
Permutation codes are error-correcting codes and have been investigated
mainly for study of power line communication.
Rank modulation, which is a class of permutation codes, has recently
attracted since the modulation might be applicable to an
error-correction method for flash memories.
In this talk, basic notion and idea will be introduced and some previous
results on construction of the codes and the modulations suitable for
linear programming method as decoding algorithm will be discussed.
|
12/10
| 電子情報通信学会コンピュテーション研究会 |
| 投稿〆切 : 2012/9/28 |
| Place : 九州大学伊都キャンパス |
12/10
| [elc] 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 九州大学 |
12/15 - 17
| FSTTCS 2012 |
| 投稿〆切 : 2012/7/13 |
| Place : IIIT Hyderabad, India |
12/17
| [elc] ELC Mini-Workshop (A02) |
| Place : CELC(計算限界研究センター, 田町) |
| 13:00〜17:00(終了時間は予定)
講演者(題目と講演順は仮)
- Skip Jordan(北大) 「Experimental Model Theory and Testing: Recent Directions」
- 吉田悠一(NII) 題目未定
- 脊戸和寿(電通大)「回路計算量と通信複雑さ」
- 玉置卓(京大) 「計算限界証明における障壁と性質検査アルゴリズム」
Click to Continue ...質問・ディスカッション重視で行います。
状況によってはセミナーの途中、あるいは最後にディスカッションを設定するかもしれません。
問合せは伊藤大雄(電通大)まで
|
12/17 - 18
| [elc] ELC Mini-Workshop (C03) |
| Place : JR博多シティ9F第2,3会議室 |
| 会場:
JR博多シティ9F第3会議室(12/17),第2会議室(12/18)
アクセス:
http://www.jrhakatacity-eventspace.jp/access/index.html
また,17日19時より博多駅付近で懇親会を企画しています
Click to Continue ...(参加費4000-5000円程度).
参加希望の方は12月13日(木)までに畑埜
http://www.i.kyushu-u.ac.jp/~hatano/
までご連絡下さい.
※なお発表者の方は特に連絡のないかぎり参加を想定していますので,ご連絡は不要です.ご都合の悪い方はお知らせください.
スケジュール:
Dec 17 (mon) JR Hakata City 9F, Meeting Room 3
10:00 - 10:20
Eiji Takimoto (Kyushu University)
Opening address and some remarks on the mission of Group C03.
10:30 - 12:00 [Tutorial Talk]
Kei Uchizawa (Yamagata University)
Learning Algorithm and Circuit Lower Bounds
14:00 - 15:30
Kohei Hatano (Kyushu University)
Combinatorial Online Prediction using Offline Approximation Algorithms
Marco Cuturi (Kyoto University)
Transportation Distances and their Application in Machine Learning:
New Problems
15:45 - 17:15
Ayumi Shinohara (Tohoku University)
Revisiting minimum consistency problem for DFA, and on the maximum number
of runs in a string.
Ryo Yoshinaka (Kyoto University)
Distributional Learning of Context-Free Grammars
17:30 -
Kei Uchizawa (Yamagata University)
Output Patterns of Logic Circuits
19:00 - drinking session
Dec 18 (tue) JR Hakata City 9F, Meeting Room 2
10:00 - 11:30
Takayoshi Shoudai (Kyushu University)
Learning Unordered Tree Contraction Patterns in Polynomial Time
Koji Tsuda (Aist)
Loss Minimization of Power Distribution Networks with Binary Decision
Diagrams
11:30 - 12:00 (free discussion)
[Tutorial]
Speaker: Kei Uchizawa (Yamagata University)
Title: Learning Algorithm and Circuit Lower Bounds
Abstract:
In this talk, we mainly survey the following two papers concerning a
relationship between learning algorithms and circuit lower bounds:
(1) Efficient Learning Algorithms Yield Circuit Lower Bounds,
Journal of Computer and System Sciences, 75, 27-36, 2009.
(2) Learning DNFs and Circuits using Teaching Assistants,
In Proceedings of COCOON 2004, 188-197, 2004.
We then discuss future work and open problems along a line of research
given by the paper (2).
(1h30min)
Speaker: Kei Uchizawa (Yamagata University)
Title: Output Patterns of Logic Circuits
Abstract:
Consider any combinatorial circuit C of logic gates. We define
an output pattern of C for a circuit input x as a vector of the outputs
of the gates in C for x, and say that C has a number p of output patterns
if different p output patterns arise in C for the circuit inputs.
In this talk, we observe that the number of output patterns are strongly
related to another major complexity measure, size
(i.e., the number of gates), and then present some lower bounds on
the number of output patterns. We also give some dichotomy result on
a problem of counting output patterns of a simple logic circuit.
(45min)
Speaker: Ryo Yoshinaka (Kyoto University)
Title: Distributional Learning of Context-Free Grammars
Abstract:
In Grammatical Inference, intensive research on the learning of
regular languages has achieved a plenty of positive results so far.
It had been thought to be quite a hard task to learn a considerably
rich class of languages that handle context-free structures.
In these years, a new line of research on the learning of context-free
languages, called "distributional learning", has been proposed and has
produced several fruitful results.
Distributional learning algorithms model and exploit the distribution of
substrings in grammatical sentences.
This talk summarizes different approaches of distributional learning
and presents some open problems on the efficiency of the learning
algorithms.
(45min)
Speaker: Takayoshi Shoudai (Kyushu University)
Title: Learning Unordered Tree Contraction Patterns
in Polynomial Time
Abstract:
We present a concept of edge contraction-based tree-structured
patterns as a graph pattern suited to represent tree-structured data.
A tree contraction pattern (TC-pattern) is an unordered tree-structured
pattern common to a given tree-structured data, which is obtained by
merging every uncommon connected substructure into one vertex by
edge contraction. In this talk, in order to establish an algorithmic
foundation for the discovery of knowledge from tree-structured data,
we show that TC patterns are learnable in polynomial time.
(45min)
Speaker: Ayumi Shinohara (Tohoku University)
Title: Revisiting minimum consistency problem for DFA,
and on the maximum number of runs in a string.
Abstract:
We discuss two topics. The first one is motivated by a simple puzzle game
which we own created, and we are interested in the computational
complexity
to solve it. It is NP-hard in general, since it contains the minimum
consistency
problem for deterministic finite automata (MinCons(DFA)) as a special
case.
MinCons(DFA) is well-known to be NP-hard and hard to approximate.
We are trying to analyze the complexity for a special case, which
is also related to the problem of inferring graphs from walks.
The second topic is concerning with the combinatorial properties of
maximal repetitions (runs) in strings. We show a new lower bound of
maximal sum of exponents of runs in a string.
(45min)
Speaker: Kohei Hatano (Kyushu University)
Title: Combinatorial Online Prediction using Offline Approximation
Algorithms
Abstract:
We consider online prediction problems of combinatorial concepts.
Examples of such concepts include shortest pathes, permutations,
assignments, covers, and so on.
The goal of the online prediction algorithm is to compete with the best
fixed combinatorial concept in hindsight.
A generic approach to this problem is to design an "offline-online
converter", i.e.,
an online prediction algorithm using the corresponding offline
(approximation) algorithm as an oracle.
The current state-of-the art converter, however, is not efficient enough.
In this talk, we will discuss approaches to construct more efficient
offline-online converters.
(45min)
Speaker: Marco Cuturi (Kyoto University)
Title: Transportation Distances and their Application in Machine
Learning: New Problems
Abstract:
I will present in this talk two new research topics related to the
optimal transportation distance (also known as Earth Mover's or
Wasserstein) and its application in machine learning to compare
histograms of features.
I discuss first the ground metric learning problem, which is the
problem of tuning automatically the parameters of transportation
distances using labeled histogram data.
After providing some reminders on optimal transportation,
I will argue that learning transportation distances is akin
to learning an L1 distance on the simplex, namely a distance with
polyhedral level sets, and I will draw some parallels with Mahalanobis
distances, the L2 distance and elliptic level sets. I will then introduce
our algorithm (arXiv:1110.2306) and more recent extensions.
In the second part of my talk, I address the fact that transportation
distances are not Hilbertian by showing that they can be cast as
positive definite kernels through the "generating function trick".
We prove that the trick, which uses the generating function of the
transportation polytope to define a similarity - rather than focusing
exclusively on the optimal transport to define a distance - leads to
a positive definite kernel between histograms
(arXiv:1209.2655).
(45min)
Speaker: Koji Tsuda (Aist)
Title: Loss Minimization of Power Distribution Networks with
Binary Decision Diagrams
Abstract:
Determining loss minimum configuration in a distribution network is a
hard discrete optimization problem involving many variables.
Since more and more dispersed generators are installed on the demand side
of power systems and they are reconfigured frequently, developing
automatic approaches is indispensable for effectively managing a
large-scale distribution network. Existing fast methods employ local
updates that gradually improve the loss to solve such an optimization
problem. However, they finally get stuck at local minima, resulting in
arbitrarily poor results. In contrast, this paper presents a novel
optimization method that provides an error bound on the solution quality.
Thus, the obtained solution quality can be evaluated in comparison to
the global optimal solution. Instead of using local updates,
we construct a highly compressed search space using a binary decision
diagram and reduce the optimization problem to a shortest path-finding
problem.
Our method was shown to be not only accurate but also remarkably efficient;
Optimization of a large-scale model network with 468 switches was solved
in three hours with 1.56% relative error bound.
(45min)
|
12/19 - 21
| ISAAC 2012 |
| 投稿〆切 : 2012/6/22 |
| Place : Taipei, Taiwan |
12/28
| [elc] ELC Seminar (河内亮周) |
| Place : CELC |
| タイトル: ACC^0回路のNEXPでの超多項式下界の解説
講師: 河内 亮周 (東工大)
場所: 計算限界研究センターセミナー室
http://www.al.ics.saitama-u.ac.jp/elc/?celc
関連論文:
[Wil13] Ryan Williams: Natural Proofs versus Derandomization, manuscript (available at R. Williams' website).
[Wil11] Ryan Williams: Non-uniform ACC Circuit Lower Bounds. IEEE Conference on Computational Complexity 2011: 115-125
Click to Continue ...[Wil10] Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. STOC 2010.
[IKW02] Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. 65(4): 672-694 (2002)
|