2014年 | |
1/5 - 7
| SODA 2014 |
| 投稿〆切 : 2013/7/8 |
| Place : Portland, Oregon, USA |
| July 3, 2013, 4:59 PM EDT - Deadline - Short Abstract Submission and Paper Registration Deadline
|
1/11 - 12
| CREST特定課題調査「ビッグデーター時代に向けた革新的アルゴリズム基盤」シンポジウム |
| Place : 京都リサーチパーク 東地区1号館4階AV会議室 |
| 懇親会参加登録〆切:1月6日
|
1/12 - 14
| ITCS 2014 |
| 投稿〆切 : 2013/8/22 |
| Place : Princeton, New Jersey |
1/13 - 5/16
| Quantum Hamiltonian Complexity |
| Place : Simons Institute, Berkeley |
1/13 - 5/16
| Evolutionary Biology and the Theory of Computing |
| Place : Simons Institute, Berkeley |
1/25 - 26
| [elc] ELC Workshop on Inapproximability |
| Place : University of Electro-Communications, Japan |
| Tentative Program
January 25 (Sat)
12:00-13:00 Registration
13:05-13:15 Opening Address
13:15-14:00 Nisheete Vishnoi (Microsoft Research India)
14:15-15:00 Samuel Fiorini (Universite libre de Bruxelles)
Click to Continue ...15:15-16:00 Danupon Nanongkai (Nanyang Technological University)
16:15-17:00 Kenya Ueno (Kyoto University)
January 26 (Sun)
9:30-10:15 Michael Lampis (Kyoto University)
10:30-11:15 Sevag Gharibian (University of California, Berkeley)
11:30-12:15 Kiyohito Nagano (Future University Hakodate)
12:15 Closing
Afternoon: Possible excursion to Jindaiji
and further discussion
Organizers
Satoru Iwata (University of Tokyo)
Naoyuki Kamiyama (Kyushu University)
Naoki Katoh (Kyoto University)
Shuji Kijima (Kyushu University)
Yoshio Okamoto (University of Electro-Communications)
|
1/28 - 30
| 冬のLAシンポジウム |
| Place : 京都大学 数理解析研究所 |
2/3 - 6
| ICNC2014 (International Conference on Computing, Networking and Communications) |
| 投稿〆切 : 2013/7/5 |
| Place : Honolulu, Hawaii, USA |
2/3 - 7
| QIP 2014 |
| Place : Barcelona |
2/10
| [elc] SODA 2014 参加報告会 |
| Place : 東京工業大学キャンパス・イノベーションセンター 2階 多目的ルーム |
| 日時 2月10日 9:40~18:00
場所 〒108-0023 東京都港区芝浦3-3-6
東京工業大学キャンパス・イノベーションセンター
2階 多目的ルーム
(http://www.cictokyo.jp/index.html)
9:40-10:40:大舘 陽太 (JAIST)
Click to Continue ...担当論文:Large induced subgraphs via triangulations and CMSO
F. Fomin, I. Todinca, Y. Villanger
11:00-12:00:安藤 映 (崇城大学)
担当論文:Smoothed Analysis of Local Search for the Maximum-Cut
Problem
M. Etscheid, H. Roglin
13:00-14:00: 小長谷 松雄 (JAIST)
担当論文: Selection and Sorting in the "Resotre" Model
T. M. Chan, J. I. Munro, V. Raman
14:20-15:20:澄田 範奈 (東京大学)
担当論文: Dantzig's pivoting rule for shortest paths, deterministic MDPs,
and minimum cost to time ratio cycles
T. D. Hansen, H. Kaplan, U. Zwick
15:40-16:40: 木村 慧 (東京大学)
担当論文: Space complexity of list H-coloring: a dichotomy
L. Egri, P. Hell, B. Larose, A. Rafiey
17:00-18:00: 桂 敬史 (東北大学)
担当論文: Bicriteria data compression
A. Farruggia, P. Ferragina, A. Frangioni, R. Venturini
|
2/17 - 20
| CTFM 2014 |
| 投稿〆切 : 2014/1/15 |
| Place : 東京 |
2/24 - 26
| TCC 2014 |
| Place : San Diego, CA, USA |
2/28
| 第9回 組合せゲーム・パズル ミニ研究集会 |
| 投稿〆切 : 2013/2/7 |
| Place : 北陸先端科学技術大学院大学 I3-I4講義室 |
| ・特別企画 JAISTギャラリーパズルコレクション見学会があります。
・講演申込締め切りは2月7日 17:00
|
3/3 - 5
| EuroCG 2014 |
| Place : 死海, イスラエル |
3/5 - 7
| 日本OR学会春季研究発表会・シンポジウム |
| 投稿〆切 : 2013/12/31 |
| Place : 大阪大学 豊中キャンパス |
| 5日(午後):シンポジウム
6・7日:研究発表会
|
3/5 - 8
| STACS 2014 |
| 投稿〆切 : 2013/9/20 |
| Place : Lyon, France |
3/8
| 離散数学1日セミナー |
| 投稿〆切 : 2014/2/20 |
| 加納幹雄教授(茨木大)退職記念行事:
- 最終講義:3月7日(金)14時30分~16時
- 祝賀会: 3月7日(金)17時~19時30分(予定)
詳細は
http://gorogoro.cis.ibaraki.ac.jp/web/kano2014/index.html
|
3/10
| 電子情報通信学会コンピュテーション研究会 |
| 投稿〆切 : 2013/12/24 |
| Place : 明治大 |
3/11 - 12
| 第7回 錯覚ワークショップ |
| Place : 明治大学 中野キャンパス 6階セミナー室3 |
| 3/11 12:55--17:20
3/12 09:30--17:20
|
3/14
| [elc] 新学術領域「計算限界解明」シンポジウム |
| Place : 東京工業大学 田町キャンパス |
3/15
| [elc] ELC Mini-Workshop (B01) |
| Place : 東大本郷キャンパス工学部6号館2階235号室 |
| プログラム:
10:00 -- 11:00 : The matching polytope has exponential extension complexity の解説(神山)
11:00 -- 12:00 : Garph procduct の解説(来嶋)
13:00 -- 15:00 : 議論
15:30 -- 17:00 : 議論
|
3/16 - 18
| EuroCG 2015 |
| 投稿〆切 : 2015/1/7 |
| Place : Ljubljana(リュブリャナ), Slovenia |
3/18 - 21
| 電子情報通信学会 総合大会 |
| 投稿〆切 : 2014/1/7 |
| Place : 新潟大学 |
| 締切は1月8日(水)午後5時
・一般セッションD-1「コンピュテーション」
・シンポジウムDS-1「COMP-ELC学生シンポジウム」
|
3/19
| [elc] COMP-ELC 学生シンポジウム |
| Place : 新潟大学 |
| 電子情報通信学会 総合大会 (3/18-21) での企画です
|
3/24 - 28
| WACT 2014 |
| Place : Saarbruecken, Germany |
3/26
| [elc] ELC Seminar (Akimasa Miyake) |
| Place : CELC |
| Speaker: Prof. Akimasa Miyake (Univ. of New Mexico)
Time & Date: 3:00pm, March 26
Place: CELC seminar room (404, 4F)
Title: Quantum computation and simulation, and classical simulation thereof
Abstract: Potential quantum advantage in computation and simulation is of great
interest to scientists, while for now its evidences are rather
Click to Continue ...scattered as quantum algorithms solving specific problems. In this
talk, I would like to advocate such an approach that quantum
entanglement is indeed a way to characterize generally the complexity
of quantum computation and simulation, despite some (old and new)
misconceptions about its roles. I highlight a restricted set of
quantum logical gate operations related to non-interacting fermionic
time evolutions, called quantum matchgates, in order to observe a
subtle difference between quantum computation and classical simulation
thereof in this setting. It is demonstrated that the computational
complexity of quantum matchgate circuits is evaluated by
"concentrating necessary entanglement and compressing optimally the
width of quantum circuits."
Contact: Akinori Kawachi
|
3/31 - 4/4
| LATIN 2014 |
| 投稿〆切 : 2013/9/22 |
| Place : Montevideo, Uruguay |
4/5 - 6
| DICE 2014 |
| 投稿〆切 : 2014/1/5 |
| Place : グルノーブル(仏) |
4/11 - 13
| TAMC 2014 (11th Annual Conference on Theory and Applications of Models of Computation) |
| 投稿〆切 : 2013/11/15 |
| Place : Vivekananda Auditorium, Anna University, Chennai, India |
4/24
| 電子情報通信学会コンピュテーション研究会 |
| Place : 東北大学 |
| 専門委員会を開催
懇親会あり。申込みは
https://www.al.ics.saitama-u.ac.jp/horiyama/party/2014_0424_comp/
|
5/8
| [elc] ELC Seminar (Dr. Brendan Juba) |
| Place : CELC |
| Speaker: Dr. Brendan Juba(Harvard Univ.)
Time and date: 4:00pm - 5:30pm, May 8
Place: CELC seminar room (404, 4F)
Title: Knowledge Farming
Abstract: A variety of problems can be cast as "data mining with a
goal." I propose a framework for solving such problems by
Click to Continue ...integrating machine learning into logical reasoning problems.
In machine learning, we may obtain a new formula satisfied by data.
In logical reasoning, we seek a proof that derives a query proposition
from background knowledge, given as additional input propositions. In
the combined approach, we seek a proof that derives a query from the
background knowledge and any propositions that can be learned from
the input data. The crucial advantage of this integrated approach is
that the query and background knowledge serve as context for
learning. This context guides an algorithm to identify the relevant
propositions satisfied by the data. I will show how these algorithms
can possess desirable properties, such as tolerance to adversarial
noise. Moreover, for some applications, such integrated algorithms
provide the first algorithms known to be efficient.
|
5/11 - 15
| EUROCRYPT 2014 |
| Place : Copenhagen, Denmark |
5/17 - 19
| AAAC2014 (7th Annual Meeting of Asian Association for Algorithms and Computation) |
| 投稿〆切 : 2014/2/5 |
| 投稿はアブストラクト(1ページ)
|
5/17 - 24
| Japan Conference on Graph Theory and Combinatorics |
| 投稿〆切 : 2014/3/15 |
| Place : 日本大学文理学部 |
| Plenary Speakers:
Noga Alon (Tel Aviv University, Israel)
Maria Axenovich (Karlsruhe Institute of Technology, Germany)
Jack Koolen (University of Science and Technology of China, China)
Hiroshi Nozaki (Aichi University of Education, Japan)
Patrice Ossona de Mendez (Ecole des Hautes Etudes en Sciences Sociales, France)
Dieter Rautenbach (Universitat Ulm, Germany)
Click to Continue ...Paul Seymour (Princeton University, U.S.A.)
Paul Terwilliger (University of Wisconsin, U.S.A.)
Xingxing Yu (Georgia Institute of Technology, U.S.A.)
Xuding Zhu (National Sun Yat-sen University, Taiwan)
|
5/21 - 23
| TQC 2014 |
| 投稿〆切 : 2014/2/15 |
| Place : Singapole |
5/23 - 24
| [elc] 平成26年度 第1回領域会議 |
| Place : CELC |
| 2014年度第一回領域会議
場所: 東京工業大学キャンパスイノベーションセンター
http://www.cictokyo.jp/access.html
日時: 5月23日,24日 領域会議: 1階 国際会議室
総括班会議: 4階 404号室
ポスターセッション: 1階 国際会議室
Click to Continue ...
5月23日
13:00-13:10 事務局連絡
13:10-13:40 公募班1
13:40-14:10 公募班2
14:10-14:30 休憩
14:30-15:00 公募班3
15:00-15:30 公募班4
15:30-15:50 休憩
15:50-16:30 本年度の計画について
16:30-18:00 ポスターセッション
5月24日
9:30-11:00 ポスターセッション
11:00-11:30 公募班5
11:30-12:00 公募班6
12:00-13:30 お昼休み 総括班会議
13:30-14:00 公募班7
14:00-14:30 公募班8
14:30-15:00 公募班9
15:00-15:20 休憩
15:20-16:20 中間評価に向けて
16:20-16:30 事務局連絡
公募班1: 形式論理のプロパティー検査と発見による計算限界の解析
Skip Jordan (北海道大学)
公募班2: 離散最適化に対する固定パラメータアルゴリズム設計によるパラメータ化計算複雑さ解明
宇野 裕之 (大阪府立大学)
公募班3: 計算構造制限下での暗号技術の限界解明
安永 憲司 (金沢大学)
公募班4: 分散計算複雑性の理論:最悪時評価を超えて
泉 泰介 (名古屋工業大学)
公募班5: 離散凸解析に基づく劣モジュラ最適化問題の計算限界の解明
塩浦 昭義 (東北大学)
公募班6: 線形相補性問題の計算限界への挑戦
森山 園子 (東北大学)
公募班7: 列挙的なアプローチによる計算限界解明
山中 克久 (岩手大学)
公募班8: 解空間の直径に基づく計算限界解析アプローチの構築
伊藤 健洋 (東北大学)
公募班9: 統計力学的アプローチによる機械学習の計算限界解明アルゴリズム開発
永田 賢二 (東京大学)
|
5/29
| [elc] ELC Seminar ( Dr. Periklis Papakonstantinou) |
| Place : CELC |
| Speaker: Periklis A. Papakonstantinou (IIIS Tsinghua University)
Time & date: 4:00pm, May 29
Place: CELC seminar room (404, 4F)
Title: Cryptography with Streaming Algorithms
Abstract: We put forth the question of whether cryptography is feasible using streaming devices. We
give constructions and prove lower bounds. In streaming cryptography (not to be confused
Click to Continue ...with stream-ciphers) everything|the keys, the messages, and the seeds|are huge compared
to the internal memory of the device. These streaming algorithms have small internal memory
size and make a constant number of passes over big data maintained in a constant number of
read/write external tapes. Typically, the internal memory size is O(log n) and we use 2 external
tapes; whereas 1 tape is provably insucient. In this setting we cannot compute instances of
popular intractability assumptions. Nevertheless, we base cryptography on these assumptions
by employing non-black-box techniques, and study its limitations.
We introduce new techniques to obtain unconditional lower bounds showing that no super-
linear stretch pseudorandom generator exists, and no Public Key Encryption (PKE) exists with
private-keys of size sub-linear in the plaintext length.
For possibility results, assuming the existence of one-way functions computable in NC1|e.g.
factoring, lattice assumptions|we obtain streaming algorithms computing one-way functions
and pseudorandom generators. Given the Learning With Errors (LWE) assumption we construct
PKE where both the encryption and decryption are streaming algorithms. The starting point
of our work is the groundbreaking work of Applebaum-Ishai-Kushilevitz on Cryptography in
NC0. In the end, our developments are technically orthogonal to their work; e.g. there is a PKE
where the decryption is a streaming algorithm, whereas no PKE decryption can be in NC0.
|
5/31 - 6/3
| STOC 2014 |
| 投稿〆切 : 2013/11/11 |
| Place : New York, USA |
6/4 - 6
| [elc] Japanese-Swiss Workshop on Combinatorics and Computational Geometry |
| Place : 東京 |
6/5
| [elc] ELC Seminar on Theoretical Computer Science in UEC |
| Place : Room 302 (3F), West-9 BLDG, The University of Electro-Communications(電気通信大学, 西9号館, 3F 302) |
| ELC Seminar on Theoretical Computer Science in UEC
We are going to have a seminar on Theoretical Computer Science,
which consists of a talk by a distinguished researcher
Professor Mike Paterson (Univ. Warwick, UK).
We hope you all participate.
Click to Continue ...--
Time and Date: 14:000--15:00, June 5 (Thur), 2014.
Place: Room 302, 3F, West-9 BLDG, The University of Electro-Communications
http://www.uec.ac.jp/eng/about/access/
Speaker: Mike Paterson (DIMAP and Computer Science, Univ. Warwick, UK)
Title: Geometric dissection problems
Abstract:
I shall introduce several dissection problems, which involve cutting and
rearranging simple geometric shapes. In particular I will concentrate on
recent results which involve packing sectors of a circular disc inside a
smaller circle, and explain in detail some of the constructions and
techniques needed. Some very open problems remain!
Contact to: ITO Hiro (UEC, Japan)
http://www.alg.cei.uec.ac.jp/itohiro/
|
6/6 - 12
| CSR 2014 |
| 投稿〆切 : 2013/12/9 |
| Place : Moscow, Russia |
6/8 - 11
| SoCG 2014 |
| 投稿〆切 : 2013/11/22 |
| Place : Centennial Memorial Hall, Clock Tower Centennial Hall, Kyoto University, Kyoto, Japan |
6/9
| [elc] Workshop on Extension Complexity: An Update and Future Directions |
| Place : 京都大学百周年記念館 |
| SoCG 2014(http://www.dais.is.tohoku.ac.jp/~socg2014/#home)
のWorkshopとして開催します.
奮ってご参加ください.
Organizers: David Avis and Naoki Katoh
Invited Speakers:
Click to Continue ...Hans Tiwary (Charles University)
Extended formulations: Introduction to lower bounding techniques
Kanstantsin Pashkovich (Université libre de Bruxelles)
Extended formulations: Lower bounds and matching polytope
Yoshio Okamoto (University of Electro-Communications)
Extended formulations for sparsity matroids
David Avis (Kyoto and McGill)
Polynomial size matching polytopes
文責 加藤直樹(京都大学)
|
6/11 - 14
| CCC 2014 |
| 投稿〆切 : 2013/11/27 |
| Place : Vancouver, British Columbia, Canada |
6/13 - 14
| 電子情報通信学会コンピュテーション研究会 |
| 投稿〆切 : 2014/4/7 |
| Place : 道後温泉(愛媛県松山市) |
| 情報処理学会アルゴリズム研究会と連催
|
6/13 - 15
| COLT 2014 |
| 投稿〆切 : 2014/2/7 |
| Place : Barcelona, Spain |
6/21 - 26
| ICML 2014 |
| Place : Beijing |
6/22 - 27
| SIGMOD/PODS 2014 |
| Place : Snowbird, Utah, USA |
6/23 - 25
| IPCO XVII (17th Conference on Integer Programming and Combinatorial Optimization) |
| 投稿〆切 : 2013/11/15 |
| Place : Bonn, Germany |
6/23 - 27
| CiE 2014 |
| 投稿〆切 : 2014/1/10 |
| Place : ブダペシュト(洪) |
6/25 - 27
| WG 2014 (40th International Workshop on Graph-Theoretic Concepts in Computer Science) |
| 投稿〆切 : 2014/3/1 |
| Place : Domaine de Chals near Orlans, France |
6/28 - 30
| FAW 2014 (The 8th International Frontiers of Algorithms Workshop) |
| 投稿〆切 : 2014/2/20 |
| Place : 張家界, 中国 (Zhangjiajie, Hunan, China) |
6/29 - 7/1
| SEA 2014 (13th International Symposium on Experimental Algorithms) |
| 投稿〆切 : 2014/2/7 |
| Place : Copenhagen, Denmark |
| SWAT2014, ICALP2014を続けて開催
|
7/1 - 3
| FUN 2014 (7th International Conference on FUN WITH ALGORITHMS) |
| Place : Lipari Island, Sicily, Italy |
7/2 - 4
| SWAT 2014 |
| 投稿〆切 : 2013/2/28 |
| Place : IT University in Copenhagen |
| SEA2014に続けて開催
ICALP2014を続けて開催
|
7/7 - 11
| ICALP 2014 |
| 投稿〆切 : 2014/2/14 |
| Place : IT University in Copenhagen |
| SEA 2014, SWAT2014に続けて開催
|
7/9 - 24
| Vienna Summer of Logic |
| Place : Vienna, Austria |
7/10 - 11
| 6th Conference on Reversible Computation (RC 2014) |
| 投稿〆切 : 2014/2/9 |
| Place : 京都 |
| Abstract Submission: February 9th, 2014
Submission Deadline: February 16th, 2014
|
7/11
| FMES(経営工学関連学会協議会)シンポジウム 「ビッグデータ利活用と価値創造」 |
| Place : 日科技連 千駄ヶ谷本部ビル 1号館3階講堂 |
7/13 - 15
| WAAC 2014 |
| 投稿〆切 : 2014/5/25 |
| Place : 沖縄コンベンションセンター |
7/13 - 18
| IFORS 2014 (20th Conference of the International Federation of Operational Research Societies) |
| 投稿〆切 : 2014/1/31 |
| Place : BARCELONA, SPAIN |
| 投稿は1ページのアブストラクト
|
7/16
| [elc] ELC Seminar on Theoretical Computer Science in UEC |
| Place : Room 302 (3F), West-9 BLDG, The University of Electro-Communications(電気通信大学, 西9号館, 3F 302) |
| ELC Seminar on Theoretical Computer Science in UEC
We are going to have a seminar on Theoretical Computer Science,
which consists of a talk by
Professor Wolfgang Bein (University of Nevada, Las Vegas).
We hope you all participate.
Click to Continue ...--
Time and Date: 14:000--15:30, July 16 (Wed), 2014.
Place: Room 302, 3F, West-9 BLDG, The University of Electro-Communications
http://www.uec.ac.jp/eng/about/access/
Speaker: Wolfgang Bein (University of Nevada, Las Vegas)
Title: Knowledge States: A Tool in Randomized Online Algorithms
Abstract:
We introduce the concept of knowledge states; many well-known algorithms can
be viewed as knowledge state algorithms. The knowledge state approach can
be used to to construct competitive randomized online algorithms and study
the tradeoff between competitiveness and memory.
We give new results for the two server problem and the paging problem.
We present a knowledge state algorithm for the two server problem over
Cross Polytope Spaces with a competitive ratio of 19/12, and show that
it is optimal against the oblivious adversary.
Regarding the paging problem, Borodin and El-Yaniv had listed as an
open question whether there exists an H_k-competitive randomized
algorithm which requires O(k) memory for k-paging. We have answered
this question in the affirmative using knowledge state techniques.
Contact to: ITO Hiro (UEC, Japan)
http://www.alg.cei.uec.ac.jp/itohiro/
|
7/17 - 19
| LA シンポジウム |
| Place : 半月庵 (山口県岩国市) |
7/21 - 24
| CCA (Eleventh International Conference on Computability and Complexity in Analysis) |
| 投稿〆切 : 2014/4/7 |
| Place : 独ダルムシュタット |
7/23 - 25
| SIROCCO 2014 (21st International Colloquium on Structural Information and Communication Complexity) |
| 投稿〆切 : 2014/4/25 |
| Place : 高山グリーンホテル, 岐阜県高山市 |
| url : https://sites.google.com/site/sirocco2014japan/home |
7/26 - 27
| [elc] ELC Mini-Workshop (B01, C03) |
| Place : 九州大学伊都キャンパス数理学研究教育棟中セミナー室7 |
| 7/26
13:00 -- 14:00
畑埜晃平:順序にまつわるエトセトラ
14:15 -- 15:15
篠原歩:文字列に含まれる連の最大数と指数和について(仮)
15:30 -- 16:30
加藤直樹:minimax regret sink location problems in dynamic networks
Click to Continue ...16:30 -- 17:00
議論
7/27
10:00 -- 11:00
正代隆義:文脈決定文脈自由グラフ言語の質問学習
11:15 -- 12:15
内澤啓:拡散競争ゲームについて
13:30 -- 14:30
神山直之:計算量理論的視点から生じるマッチングに関する問題
14:30 -- 15:00
議論
多班の方で参加を希望されるかたは神山までメールをお送りください.
|
7/27 - 31
| AAAI-14 |
| Place : Quebec City, Quebec, Canada |
7/30 - 8/1
| 第11回組合せ最適化セミナー |
| Place : 京都大学 数理解析研究所 |
8/4 - 6
| COCOON 2014 |
| 投稿〆切 : 2014/2/15 |
| Place : Atlanta, Georgia, USA, |
8/6
| [elc] ELC Seminar (Dr. Boaz Barak) |
| Place : Center for ELC @ CIC Tamachi |
| Speaker: Dr. Boaz Barak(Microsoft Research)
Time & date: 4:00pm - 5:30pm, Aug 6th
Place: CELC seminar room (404, 4F)
TITLE: Sum of Squares Proofs and the Quest towards Optimal Algorithms
ABSTRACT:
I will survey recent results and questions regarding the Sum-of-quares (SOS) method for
Click to Continue ...solving polynomial equations. This method, which is related to classical mathematical questions,
has been studied in several scientific disciplines, including real algebraic geometry,
proof complexity, control theory, and mathematical programming, and has found applications
in fields as diverse as quantum information theory, formal erification, game theory and many others.
We discuss some new perspectives on the SOS method, giving different interpretations
and applications of it, and raising the question whether it could yield a generic *optimal* algorithm
for broad domains of computational problems.
We will also discuss the fascinating relation between the SOS method and
Khot's Unique Games Conjecture, which is a tantalizing conjecture in computational complexity
that has the potential to shed light on the complexity of a great many problems.
The talk will assume no background on the SOS method or the unique games conjecture.
It is partially based on joint works with Jonathan Kelner and David Steurer.
|
8/10 - 13
| 6OSME (The Sixth International Conference on Origami in Science, Mathematics, and Education) |
| 投稿〆切 : 2013/11/1 |
| Place : 東京大学 |
8/11 - 13
| CCCG (26th Canadian Conference on Computational Geometry) |
| 投稿〆切 : 2014/5/9 |
| Place : ハリファクス |
| url : https://www.cs.dal.ca/cccg2014/ |
8/17 - 21
| CRYPTO 2014 |
| 投稿〆切 : 2014/2/10 |
| Place : Santa Barbara |
8/18
| [elc] ELC Workshop on Quantum Complexity Theory |
| Place : The University of Tokyo |
| This satellite workshop of AQIS 2014 will be held at the University of Tokyo,
in the center of Tokyo, on August 18, 2014. The AQIS conference itself,
held in Kyoto, will start two days later (tutorials on August 20, main
conference from August 21), leaving plenty of time for participants
to move from Tokyo to Kyoto after the end of the workshop.
This one-day workshop will be devoted to quantum complexity theory,
Click to Continue ...with a scientific program consisting of invited talks and one "rump session"
(one session for very short, and possibly informal, contributed talks).
Invited speakers:
Andr CHAILLOUX (INRIA)
Richard CLEVE (Waterloo University / IQC)
Tomoyuki MORIMAE (Gunma University)
Harumichi NISHIMURA (Nagoya University)
Yasuhiro TAKAHASHI (NTT)
Thomas VIDICK (Caltech)
|
8/21 - 12/19
| Algorithmic Spectral Graph Theory |
| Place : Simons Institute, Berkeley |
8/21 - 12/19
| Algorithms and Complexity in Algebraic Geometry |
| Place : Simons Institute, Berkeley |
8/24 - 27
| KDD 2014 |
| Place : New York |
8/25 - 27
| ISVD2014 (11th International Symposium on Voronoi Diagrams in Science and Engineering) |
| 投稿〆切 : 2014/4/10 |
| Place : ソウル(韓国) |
8/25 - 29
| MFCS 2014 |
| 投稿〆切 : 2014/4/18 |
| Place : Budapest |
8/27 - 29
| OR学会秋期研究発表会・シンポジウム |
| 投稿〆切 : 2014/6/22 |
| Place : 北海道大学 |
| 8/27 シンポジウム: テーマ「メタヒューリスティクスの新たなる挑戦」
8/28-29 研究発表会
|
8/28 - 30
| ISORA 2014は延期(多分来年のISORA2015)になりました。 |
| ISORA 2014は延期になりました。多分来年に、すなわちISORA2015になるとの情報です。
|
9/1 - 3
| TCS2014 (8th IFIP International Conference on Theoretical Computer Science) |
| 投稿〆切 : 2014/4/27 |
| Place : Rome, Italy |
9/1 - 5
| VLDB 2014 |
| Place : Hangzhou, China |
9/3 - 5
| FIT 2014 |
| 投稿〆切 : 2014/4/16 |
| Place : 筑波大学 筑波キャンパス |
| 査読付き論文申込締切:4月16日(水)15:00
|
9/4 - 6
| RANDOM-APPROX 2014 |
| 投稿〆切 : 2014/4/17 |
| Place : Barcelona |
9/8 - 9
| 第8回錯覚ワークショップ |
| Place : 明治大学 中野キャンパス 6階603セミナー室 |
9/8 - 10
| ESA 2014 |
| 投稿〆切 : 2013/4/18 |
| Place : Wrocław, Poland |
| ALGO2014 (Sept. 8-12)の中で行われます。
|
9/8 - 12
| ALGO 2014 |
| Place : Wroclaw, Poland |
9/9 - 12
| [elc] ELC暗号理論秋学校 |
| Place : 河口湖クラブセントヴィレッヂ |
| 2014年度ELC暗号理論秋学校
日程: 2014年9月9日(火) 13:00 から 12日(金) 12:00 まで
場所: 河口湖クラブセントビレッヂ (http://www.stvillage.com/)
講師: 松田 隆宏 (産総研),矢内 直人 (阪大),安永 憲司 (金沢大),河内 亮周 (東工大) (敬称略)
<講義内容>
Click to Continue ...講師: 松田隆宏
テーマ: 公開鍵暗号
1. 公開鍵暗号の構成に関するクラシックな結果の紹介 (Naor-Yung、Fujisaki-Okamoto、ハイブリッド暗号、その他もっと最近の成果など)
2. 公開鍵暗号の安全性定義の間の関係 (A安全であればB安全かどうか、その反例を示すにはどうするか、など)
講師: 矢内直人
テーマ: 電子署名
1. 署名に関する代表的な結果(RSA、DSA、BLS 署名、Boneh-Boyen, Waters、Naor 変換)
2. 署名の安全性証明手法(ランダムオラクルのみ、Coron のテクニック、Katz-Wang など)
3. 署名を利用したプロトコル仕様に対する安全性証明(S-BGP、TLS handshake など)
講師: 安永 憲司
テーマ: ゲーム理論と現代暗号
1. ゲーム理論の考え方(ゲーム的状況、戦略型ゲーム、展開型ゲーム、Nash均衡、相関均衡、部
分ゲーム完全均衡など)
2. ゲーム理論と暗号のつながり(秘密分散、安全性とNash均衡の関係)
講師: 河内 亮周
テーマ: 誤り訂正符号と暗号理論の基礎
1. 誤り訂正符号と暗号プリミティブの関係
2. 具体的な符号の暗号理論への応用
連絡先: 河内 亮周(東工大)
|
9/15 - 16
| JCDCG^2 2014 |
| 投稿〆切 : 2014/8/8 |
| Place : 東京理科大学(神楽坂キャンパス) |
9/16
| [elc] ELC Workshop on Learning Theory and Complexity (C03) |
| Place : 京都大学 |
9/17
| [elc] ELC Seminar (David Witmer) |
| Place : ELC Center Seminar Room |
| Date and Time: Sept. 17, 4pm-5pm
Place: Center for ELC (Seminar Room, 4th floor)
Speaker: David Witmer (CMU, Doctoral student)
Title: Goldreich's PRG: Evidence for near-optimal polynomial stretch
Abstract:
Goldreich proposed a simple, highly parallelizable pseudorandom generator
Click to Continue ...(PRG) construction whose security is related to the hardness of constraint
satisfaction problems. We give two types of evidence that a particular
instantiation of this generator that stretches n bits to n^1.499 bits is
secure. Specifically, we show that this PRG is secure against linear tests
and attacks based on the Lasserre hierarchy. This amount of stretch is
nearly optimal, as there is an algorithm that distinguishes the output from
random if the stretch is O(n^1.5 log(n)). Previous work had only shown
that Goldreich's generator with stretch up to n^1.249 was secure against
linear tests.
Joint work with Ryan O'Donnell
Host: Osamu Watanabe (watanabe(at)is.titech.ac.jp)
|
9/19
| [elc] ELC Mini-Workshop (C01) |
| Place : CELC |
| Date & time: September 19, 15:10 - 17:30
Place: Center for ELC Seminar Room (4F, 404)
Spearers: Dr. T. Kawamoto (Tokyo Inst. of Tech.)
Dr. M. Vehekapera (Aalto Univ., Finland)
15:10 - opening
Click to Continue ...
15:15 - 16:15
Speaker: Dr. Tatsuro Kawamoto
(Tokyo Institute of Technology, JSPS Research Fellow)
Title: Detectability limit of a spectral clustering method
Abstract:
A method of spectral clustering is one of the traditional tools for
extracting community structure out of graphs, which makes use of
eigenvectors which correspond to small eigenvalues of a graph
Laplacian. In general, estimating the validity of a community
detection method is an important problem for practical use and has
been gathering significant attention. In order to estimate the
situation where a method of spectral clustering is valid, we consider
a pair of loosely connected random graphs and solve its second
smallest eigenvalue/eigenvector problem using the replica method;
it gives the limit of the coupling strength between clusters,
below which the method correctly detects the clusters.
16:30 - 17:30
Speaker: Dr. Mikko Vehekapera (Aalto University, Finland)
Title: Signal recovery and denoising for sparse linear systems
Abstract:
Several problems in engineering can be thought as an instance of
signal recovery in linear observation systems. The current
state-of-the-art scheme for inference given a sparse source is
so-called approximate message passing (AMP) that can approach the
Bayesian optimal performance with polynomial complexity under certain
conditions. Recently it has been shown, however, that the basic AMP
algorithm is not able to provide optimal performance if the coupling
matrix is not constructed from independent entries. In this talk we
review some of the recent results regarding iterative signal recovery
methods for sparse linear systems - including the case when the
measurement matrix has specific row-orthogonal structure.
END
|
9/22
| [elc] ELC Seminar (Nir Ailon) |
| Place : 九州大学伊都キャンパスウエスト2号館10階1019号室 |
| 日時:9月22日(月)15:00-16:00
Nir Ailon (Technion)
Lower Bound for Fourier Transform in the Well-Conditioned Linear Model
(Or: If You Want a Faster Fourier Transform You'd Need to Sacrifice Accuracy)
Click to Continue ...
The Fourier Transform is one of the most important linear transformations
used in science and technology. Cooley and Tukey's Fast Fourier Transform
(FFT) from 1964 is a method for computing this transformation in time
O(n log n). In spite of its importance, no nontrivial (super-linear)
lower bounds were known without making very strong assumptions.
Morgenstern's result from 1974 provides an Ω(n log n) lower bound for
the *unnormalized* Fourier Transform (of determinant n^{n/2}),
assuming only numbers with bounded constant modulus are used.
[Ailon 2013] shows an Ω(n log n) bound for the *normalized* Fourier
Transform (of determinant 1) assuming only unitary operations on two
coordinates are allowed. In this work we show that, as long as the
computation is well conditioned, *any scaling* of the Fourier transform
requires Ω((n log n)/R) operations, where R is the condition number.
This means that, on a given machine, a faster Fourier transform is less
accurate. The main new technique is definition of a matrix entropy
function, using "quasi-probabilities" (which can be negative or >1).
I will discuss the result and present some open questions.
問合せ先:瀧本(C03)
|
9/22 - 26
| DNA20 (the 20th International Conference on DNA Computing and Molecular Programming) |
| 投稿〆切 : 2014/4/15 |
| Place : 京都大学 芝蘭会館 |
9/24 - 26
| [elc] ELC 計算量理論の秋学校 |
| Place : 鬼怒川温泉ホテル |
| 日時: 9/24(水)14時~9/26(金)12時頃
(初日受付は 13:30~を予定)
場所:鬼怒川温泉ホテル
http://www.kinugawaonsenhotel.com/
Click to Continue ...プログラム:
9月24日(水) 14:00~ 9月26日(金) 12:00頃
(1時間程度x2コマ)x4人+自由討論
プログラム詳細:
http://www.al.ics.saitama-u.ac.jp/elc/blog/20140924_0926/
講演者(順不同):
・伊藤大雄先生(電通大)
「定数時間アルゴリズム」
・岡本吉央先生(電通大)
「数理計画法に基づくアルゴリズム設計方法論の限界」
・吉田悠一先生(NII)
「劣モジュラ性と線形時間FPTアルゴリズム」
・本多淳也先生(東大)
「多腕バンディット問題と決定的・確率的アルゴリズム」
※なお,自由討論で話題提供できる方を募集しています.
「ご自身または他人の面白い結果」や「未解決問題や研究課題」
などがございましたら,ご一報いただけますと幸いです.
宿泊代等の費用:
宿泊(24日夜,25日夜)と食事(24日夜,25日朝夜,26日朝)の実費
で 25000~30000円程度です.詳細は部屋に応じて異なるので
別途個別にご案内します.
問い合わせ:
畑埜 晃平(九大)
hatano (a)inf.kyushu-u.ac.jp ((a)を@に変えて下さい)
|
10/8 - 10
| ALT 2014 |
| 投稿〆切 : 2014/5/9 |
| Place : Bled, Slovenia |
10/16 - 17
| RAMP(数理計画研究部会)シンポジウム |
| Place : 法政大学市ヶ谷キャンパス |
10/18 - 21
| FOCS 2014 |
| 投稿〆切 : 2014/4/2 |
| Place : Philadelphia, Pennsylvania |
11/6 - 10
| [elc] ELC Mini-Workshop on Boolean Functions |
| Place : Center for ELC, Tokyo Institute of Technology (Tamachi), Tokyo |
| [Schedule]
11/6 (Thu) Room #501 A-B (5F)
14:00-15:00 Kenya Ueno (B02, Kyoto U.), Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
15:30-17:00 open problems & free discussion
11/7 (Fri) Room #501 A-B (5F)
10:00-11:00 Jun Tarui (A03, U. Electro-Communications), Depth-First Search using O(n) bits
Click to Continue ...11:15-12:15 Suguru Tamaki (A02, Kyoto U.), On the complexity of randomness extractors
14:00-15:00 Kazuhisa Makino (A01, Kyoto U.), Posimodular function optimization
15:30-17:00 open problems & free discussion
11/8 (Sat) International Conference Room (1F)
10:00-11:00 Ramamohan Paturi (invited, UC San Diego), Fine-grained Complexity and Satisfiability
11:15-11:55 Kazuyuki Amano (B02, Gunma U.), Graph Partition and Communication Complexity
14:00-15:00 Osamu Watanabe (PI, Tokyo Institute of Technology), A Short Implicant of a CNF Formula with Many Satisfying Assignments
15:30-17:00 open problems & free discussion
18:00- dinner
11/9 (Sun) International Conference Room (1F)
10:00-11:00 Stefan Schneider (invited, UC San Diego), A Satisfiability Algorithm for Depth Two Threshold Circuits and 0-1 Integer Linear Programming
11:15-11:45 Kei Uchizawa (C03, Yamagata U.), Lower Bounds for Linear Decision Trees with Bounded Weights
14:00-15:00 Oliver Kullmann (invited, Swansea U.), Good SAT translations: approaches via resolution and monotone circuit bounds
15:30-17:00 open problems & free discussion
11/10 (Mon) Room #501 A-B (5F)
10:00-12:00 open problems & free discussion
[Talk Slides and Abstracts]
- Kenya Ueno, Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/ueno.pdf
In this talk, we will present O(1.415^n)-time and O(1.190^n)-space
exact algorithms for 0-1 integer programs where constraints are linear
equalities and coefficients are arbitrary real numbers. Our manuscript
on these results (arXiv:1405.6851) will be renewed before the
workshop. We will also discuss ongoing work on computational
experiments by using random 0-1 integer programs.
- Jun Tarui, Depth-First Search using O(n) bits
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/tarui.pdf
- Suguru Tamaki, On the complexity of randomness extractors
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/tamaki.pdf
Randomness extractors for structured sources such as bit-fixing and
affine sources are useful in proving circuit lower bounds. One reason
is that they inherit the property of being extractors after
restriction. In this talk I will survey known results on the
complexity of such extractors, especially focusing on lower bounds
obtained by restriction method. Also, I will present some open
questions related to this topic.
- Ramamohan Paturi, Fine-grained Complexity and Satisfiability
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/paturi.pdf
- Stefan Schneider, A Satisfiability Algorithm for Depth Two Threshold Circuits and 0-1 Integer Linear Programming
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/schneider.pdf
- Kei Uchizawa, Lower Bounds for Linear Decision Trees with Bounded Weights
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/uchizawa.pdf
We consider a linear decision tree $T$ such that the sum of the
absolute values of the integer weights of a linear threshold function
at each internal node is at most $w$, and prove that if $T$ has size
(i.e., the number of leave) $s$, rank $r$, and computes a Boolean
function $f$, then there exists a depth-2 threshold circuit that
computes $f$ and has $s(2w+1)^{r}$ threshold gates with weight at most
$(2w+1)^{r+1}$ in the bottom level. Combining a known lower bound on
size of depth-2 threshold circuits, we can obtain a $2^{\Omega (n/\logw)}$
lower bound on the size of linear decision trees computing
Inner-Product function modulo 2, which improves on the previous bound
$2^{\sqrt{n}}$ if $w=2^{o(\sqrt{n})}$.
- Oliver Kullmann, Good SAT translations: approaches via resolution and monotone circuit bounds
I wish to give an overview on our work regarding aspects of a theory of
good SAT translations ("encodings"). The main tools are various "hardness
measures" for conjunctive normal forms, based on certain stable forms of
resolution complexity, extended to satisfiable CNFs via a worst-case
approach. The basic dimensions are:
1. tree-resolution versus full-resolution
2. absolute versus relative hardness (taking auxiliary variables into
account or not).
Relative hardness is closely related to monotone circuit complexity,
while the stronger approach, absolute hardness, needs new tools.
In my talk I will discuss the basic definitions, and give an overview
on our results.
[Organizers]
Kazuhisa Makino (A01, Kyoto U.)
Kazuhisa Seto (A02, Seikei U.)
Suguru Tamaki (A02, Kyoto U.)
|
11/8 - 9
| Discrete and Computational Geometry The Goodman-Pollack Fest/Feast |
| Place : Courant Institute of Mathematical Sciences 251 Mercer Street, New York, NY 10012 |
11/21
| [elc] ELC 勉強会(Spectral Boot Camp. 報告 #1) |
| Place : ELC Seminar room |
| Date & Time: Nov. 21 (Fri), 15:45 -- 18:00
Simons Institute での Spectral Boot Camp に参加した山口君(東工大,
博士課程)に,その一部を以下のように報告してもらいます.勉強会ですので
お気軽にご参加ください.ポリコム参加の歓迎です.
ホスト:渡辺治
Click to Continue ...
====
タイトル:
A nearly linear time solver for linear equations in Laplacian matrices
Preconditioning via spectral graph sparsification
内容:
Laplacian行列で記述される線型方程式系を、非零要素数のほぼ線型時間
で近似的に解くアルゴリズムを説明する。解法は前処理付き共役勾配法を用い、
前処理行列を対応するグラフの疎化を用いて構成する。
以上
|
11/28 - 29
| [elc] 平成26年度 第2回領域会議 |
| 場所:九州大学伊都キャンパス 稲盛財団記念館 1F 稲盛ホール(会議室A,B)
http://inamori-center.kyushu-u.ac.jp/access/index.html
日時:11月28日12時40分~11時29日12時
Click to Continue ...11月28日
12:40-13:00 事務局連絡
13:00ー13:50 講演 「P vs. NP問題解決へのアプローチを整理しよう」
玉置 卓 (京都大学)
13:50ー14:00 *休憩*
14:00ー14:15 講演 「順序制約下でのオンラインジョブスケジューリングと未解決問題」
畑埜 晃平 (九州大学)
14:15-14:30 講演 「三角形発見問題の量子質問計算量」
Le Gall Francois (東京大学)
14:30ー14:45 講演 「置換上の関数に対する2者間通信複雑性」
泉 泰介 (名古屋工業大学)
14:45ー15:00 講演 「ホログラフィック変換,量子計算,統計力学」
森 立平 (東京工業大学)
15:00-15:10 *休憩* (ポスターセッション準備)
15:10-17:30 ポスターセッション
(16:30-17:30 別室で総括班会議)
19:00- 懇親会
11月29日
9:30-11:50 ポスターセッション
11:50-12:00 事務局連絡
下記から参加申し込みをお願いいたします.締め切りは11/21です.
https://www.al.ics.saitama-u.ac.jp/elc/reg/2014_1128_elc/
懇親会の申し込みは、会場の予約の関係で、定員60名に達しましたら〆切らせていただきます。
|
11/29
| [elc] ELC Mini-Workshop (B01) |
| Place : 九州大学伊都キャンパス ウェスト2号館7階720 |
| 13:00 - 15:00
岡本吉央:The 5th Cargese Workshop on Combinatorial Optimization の報告
15:30 - 18:00
議論
|
12/4
| [elc] ELC Seminar (Prof. Hubie Chen) |
| Place : CELC |
| Date: Dec. 4th (Thu), 2014
Time: 10:00 - 12:00
Place: CELC seminar room (CIC 4F)
Speaker: Hubie Chen
(Univ. del Pai's Vasco & IKERBASQUE, Basque Foundation for Science)
Click to Continue ...Title:
The Fine Classification of Conjunctive Queries
and Parameterized Logarithmic Space Complexity
Abstract:
Conjunctive queries are the most basic and heavily studied database
queries. The complexity of evaluating a conjunctive query on a
relational database has been, since the landmark work of Chandra and
Merlin (1977), a research subject of persistent and enduring interest.
This evaluation problem is equivalent to a number of well-known
problems, including conjunctive query containment, the homomorphism
problem on relational structures, and the constraint satisfaction
problem. Correspondingly, studies of this problem have come from a wide
variety of perspectives and motivations.
In this work, we perform a fundamental investigation of the complexity
of conjunctive query evaluation from the perspective of parameterized
complexity. We classify sets of conjunctive queries according to the
complexity of this problem. Previous work showed that a set of
conjunctive queries is fixed-parameter tractable precisely when the set
is equivalent to a set of queries having bounded treewidth. We present a
fine classification of query sets up to parameterized logarithmic space
reduction. We show that, in the bounded treewidth regime, there are
three complexity degrees and that the properties that determine the
degree of a query set are bounded pathwidth and bounded tree depth.
After presenting this classification theorem, we engage in a study of
the two higher degrees via logarithmic space machine characterizations
and complete problems. Our work yields a significantly richer
perspective on the complexity of conjunctive queries and, at the same
time, suggests new avenues of research in parameterized complexity.
We will end by discussing recent work that obtains a broad, unifying
perspective on and generalization of the discussed classifications. This
work makes use of a novel variant of the well-known notion of tree
decomposition which we call graph deconstruction. Interestingly, while
the notion of tree decomposition is typically useful for giving positive
algorithmic results, here we use the notion of graph deconstruction,
in a crucial way, to obtain complexity hardness results.
This talk is based on PODS '13 and LICS '14 articles with Moritz Muller.
|
12/4
| [elc] ELC Seminar (Toshio Suzuki) |
| Place : CELC seminar room |
| Date & Time: December 4th (Thu) 14:00- 15:00
Place: CELC 4F Seminar room
Toshio Suzuki
Tokyo Metropolitan University
*Title:
Equilibrium Points of an AND-OR Tree: under Constraints on Probability
Click to Continue ...
*Abstract:
We study a probability distribution $d$ on the truth assignments to a
uniform binary AND-OR tree. Liu and Tanaka [2007, Inform. Process.
Lett.] showed the following: If $d$ achieves the equilibrium among
independent distributions (ID) then $d$ is an independent identical
distribution (IID).
We show a stronger form of the above result. Given a real number $r$
such that $0 < r < 1$, we consider a constraint that the probability
of the root node having the value 0 is $r$. Our main result is the
following: When we restrict ourselves to IDs satisfying this
constraint, the above result of Liu and Tanaka still holds.
Keys to the solution are two fundamental relationships between
expected cost and probability in an IID on an OR-AND tree.
(1) The ratio of the cost to the probability (of the root having the
value 0) is a decreasing function of the probability $x$ of the leaf.
(2) The ratio of derivative of the cost to the derivative of the
probability is decreasing function of $x$, too.
This work is a collaboration with Yoshinao Niida. Our research is
partially supported by KAKENHI (C) 22540146 and (B) 23340020.
Preprint arXiv:1401.8175
END OF TALK INFO.
|
12/8 - 13
| NIPS 2014 |
| Place : Montreal, Quebec, Canada |
| url : https://nips.cc/FutureConferences/ |
12/9 - 11
| Real Analysis Reunion Workshop |
| Place : Simons Institute, UC Berkeley |
12/12
| [elc] ELC Seminar (Suguru Tamaki) |
| Place : CELC seminar room (CIC 4F) |
| Date: Dec. 12 (Fri), 2014
Time: 11:00 - 13:00
Place: CELC seminar room (CIC 4F)
Speaker: Suguru Tamaki(A02, Kyoto Univ.)
Title: SAT Algorithms and Average Sensitivity
Abstract:
Click to Continue ...In this talk, I will discuss a connection between satisfiability
algorithm and average sensitivity. For some circuit class C such as
CNF, AC0 and De Morgan formula, there exists a satisfiability
algorithm whose running time is of the form 2^{(1-1/as(C))n}, where
as(C) denotes the average sensitivity of C. Is this connection
coincidence? Does it hold for other circuit classes? I will explain
why we have such connections for CNF, AC0 and De Morgan formula and
would like to encourage people to seek more such connections.
|
12/14 - 17
| WINE 2014 (Conference on Web and Internet Economics) |
| 投稿〆切 : 2014/7/25 |
| Place : 中国 北京 |
12/15 - 17
| ISAAC 2014 |
| 投稿〆切 : 2014/6/16 |
| Place : Hanok village, Jeonju, Korea |
| Invited Speakers
Ulrik Brandes (University of Konstanz)
Giuseppe F. Italiano (Universita di Roma "Tor Vergata" )
|
12/15 - 18
| Big Data Reunion Workshop |
| Place : Simons Institute, UC Berkeley |