2013年 | |
1/6 - 8
| SODA 2013 |
| Place : New Orleans, USA |
1/10 - 12
| ITCS 2013 |
| 投稿〆切 : 2012/8/13 |
| Place : Berkeley, California |
1/17
| [elc] ELC Mini-Workshop (C01) |
| Place : CELC |
| Workshop on Randomness and Computation (organized by ELC C01)
This is the first workshop for the C01 project team. Two foreign
collaborators of C01 team are invited and with them we will have
a mini workshop for discussing collaborations between theoretical
computer science and statistical physics.
Click to Continue ...Date: 2013 Jan. 17th
Time: 1:30 - 5:30
Place: Center for ELC at Tokyo Tech CIC, Tamachi
Talks: (the detail schedule will be determined at the workshop)
0. Opening: Brief introduction to C01 project
by Osamu Watanabe (Tokyo Inst. of Tech.)
1. The minimum vertex cover problem in random hypergraphs:
replica-symmetric solution and a leaf removal algorithm
by Koji Hukushima (Univ. of Tokyo)
2. Searching for witness of unsatisfiability for a random
3-SAT formula
by Haijun Zhou
3. Statistical mechanics approach to the sample complexity
of dictionary learning
by Yoshiyuki Kabashima (Tokyo Inst. of Tech.)
4. Where the really hard problems really are?
by Lenka Zdeborova (CNRS and Institut de Physique Theorique, CEA)
We may go somewhere nearby for eating/drinking after the
workshop.
Host: Osamu Watanabe (watanabe@is.titech.ac.jp)
|
1/28 - 30
| LA シンポジウム |
| Place : 京都大学 数理解析研究所 420号室 |
2/14 - 16
| WALCOM |
| 投稿〆切 : 2012/9/3 |
| Place : IIT Kharagpur, India |
2/21
| [elc] ELC Seminar (A01) |
| Place : 東京大学(本郷キャンパス)理学部七号館214室 |
2/27
| [elc] ELC Seminar (Michael Lampis) |
| Place : 東京大学(本郷キャンパス)工学部六号館235室 |
| Date: Wednesday 17:30-18:30, February 27th
Improved inapproximability for TSP: the role of bounded occurrence CSPs
Michail Lampis (KTH Royal Institute of Technology)
The Traveling Salesman problem is one of the most famous problems in
combinatorial optimization and its approximability is a huge open
Click to Continue ...problem. Though there have been recent breakthroughs on the
algorithmic side, until recently the best inapproximability constant
was only 220/219, due to Papadimitriou and Vempala. In this talk we
will sketch a much simpler reduction which achieves a slightly better
inapproximability bound. The main ingredient is inapproximable
constraint satisfaction problems where each variable only appears a
bounded number of times. We will discuss the role of expanders and
amplifier graphs in the inapproximability of such problems and outline
a simple (but hard to analyze) idea which allows us to obtain better
expander graphs using the probabilistic method, improving on a 25-year
old result by Bollobas. Finally, we will discuss whether it is
realistic to hope that further work in this direction might eventually
lead to a strong inapproximability result for TSP (spoiler: probably
not!).
問合せ先:河村(A01)
|
2/27 - 3/2
| STACS 2013 |
| 投稿〆切 : 2012/9/21 |
| Place : Kiel, Germany |
3/1
| 組合せゲーム・パズル研究集会 |
| Place : 電気通信大学(調布) |
3/3 - 6
| TCC 2013 |
| 投稿〆切 : 2012/9/1 |
| Place : Tokyo, Japan |
3/4
| 日本OR学会 シンポジウム |
| Place : 政策研究大学院大学 |
3/5 - 6
| 日本OR学会春季研究発表会 |
| Place : 東京大学 (本郷キャンパス) |
3/13
| [elc] Satellite Mini-Workshop, Shinagawa |
| Place : Kyoto Univ. Shinagawa Office |
| Mar13(Wed) Satellite Mini-Workshop, Shinagawa
venue: Kyoto Univ. Shinagawa Office, Intercity Shinagawa Bldg. A 27F, 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)
Click to Continue ...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
(We plan to walk to a dinner place from the workshop
venue. Please note that dinner is not free of charge,
and you are kindly asked to come on time.)
|
3/14 - 15
| 第6回錯覚ワークショップ |
| Place : 明治大学 駿河台キャンパス |
3/14 - 17
| [elc] 平成24年度 第1回領域会議 & ELC Tokyo Complexity Workshop |
| Place : 品川プリンスホテル |
3/17
| [elc] Satellite Mini-Workshop on Geometric Complexity Theory (GCT) |
| Place : Campus Inovation Center Tokyo |
| 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), Kazuhisa Seto(UEC)
Click to Continue ...speakers: Ketan Mulmuley and Joshua Grochow
14:00--18:15 (with 3 breaks)
18:30-- impromptu dinner party at Tamachi
(We plan to walk to a dinner place from the workshop
venue. Please note that dinner is not free of charge,
and you are kindly asked to come on time.)
|
3/18
| 電子情報通信学会コンピュテーション研究会 |
| Place : 岐阜大学 |
3/18
| [elc] 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 岐阜大学 |
3/18 - 20
| IPCO 2013 |
| 投稿〆切 : 2012/10/24 |
| Place : Valparaso, Chile |
3/18 - 22
| EDBT/ICDT 2013 |
| Place : Genoa, Italy |
3/19
| [elc] Satellite Mini-Workshop, Kyoto |
| Place : RIMS, Kyoto Univ., Kyoto |
| 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
Click to Continue ...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: The GCT chasm
18:00-- impropmtu dinner party around Sanjo-Kawara-machi
(We will move to a dinner place from the workshop venue.
Please note that dinner is not free of charge,
and you are kindly asked to come on time.)
Abstracts:
Raghu Meka: Beating the Union Bound via Gaussian Geometry:
The union bound is one of the mainstays of the probabilistic method and
analysis of randomized algorithms. However, this simplistic approach does
not give the full picture for many important cases, with Lovasz local lemma
being a particularly salient example. In this talk I will discuss two recent
results that go beyond the union bound via geometric techniques:
1) Optimal size, explicit eps-nets for computing Gaussian integrals.
2) A new elementary and constructive proof of Spencer's celebrated
six standard deviations suffice theorem.
For both problems, our methods critically exploit certain geometric and
symmetry properties of the Gaussian space.
Zeev Dvir: Locally Decodable Codes: recent progress and open problems:
Locally Decodable Codes (LDCs) are error correcting codes that allow for
super efficient decoding of a single message symbol using only a small
number of queries to a corrupted codeword. These codes and their variants
have many theoretical applications and are also starting to appear in
practical scenarios. Our understanding of these codes is quite limited
and this talk will attempt to survey the state of the art both in term
of constructions and lower bounds.
Ketan Mulmuley: The GCT chasm:
It is shown that derandomization of Noether's Normalization Lemma (NNL) for explicit varieties
is essentially equivalent to black-box derandomization of Polynomial Identity Testing (PIT). This and
related results reveal that the fundamental problems in Geometry (classification
of algebraic varieties) and Complexity Theory (derandomization and lower bounds) share a common
root difficulty, namely the problem of overcoming the formidable EXPSPACE vs. P gap in the
complexity of NNL for explicit varieties. We call this gap the GCT chasm.
|
3/19 - 22
| 電子情報通信学会総合大会 |
| Place : 岐阜大学柳戸キャンパス |
4/11
| [elc] ELC Seminar (Colin Cooper) |
| Place : 九州大学伊都キャンパスウェスト2号館 3階 第5・6講義室 |
| 日時:4/11(木)10:00-11:30
Coalescing Random Walks and Voting on Graphs
Colin Cooper (Department of Informatics, King's College London)
The standard model of voting on connected graphs is as follows:
Click to Continue ...Initially each neighbour has a distinct opinion. The voting proceeds
in rounds. In each round each vertex contacts a randomly chosen
neighbour and adopts their opinion. We refer to this model as
single-sample voting. In voting, the quantities of interest are the
time for voting to complete, and the probability a particular opinion
wins.
The talk focuses on the following topics:
Single sample voting.
The relationship between single sample voting and coalescing random
walks. These processes are dual and we can use random walks to
analyze the performance of voting. Using this, we give an upper bound
for the expected time for voting to complete on general connected
graphs.
Other models of voting.
In the standard voting model, each vertex checks the opinion of one
neighbour at each step. We consider models of voting where more than
one opinion is sampled at each step. The simplest such model is
two-sample voting where each vertex randomly samples the opinions of
two neighbours at each step. For this model we discuss min-voting and
two-party voting.
Min-voting.
In min-voting, each vertex initially has a distinct numeric opinion
between 1 and n (the graph size). At each step each vertex randomly
samples the opinion of two neighbours, and adopts the minimum opinion.
This process completes in O(log n) expected time on certain classes
of expanders.
Two-party voting.
In two-party voting, each vertex initially holds one of two opinions
(e.g. 0 or 1). We are interested in the time taken for all vertices
to have the same opinion, and the probability that a given opinion
wins. We review the results for two-party voting in the standard
(single-sample) model of voting. We discuss the performance of
two-party voting when more than one opinion is sampled at each step.
We give some results for the outcome of two-party voting on r
regular expanders when we use two-sample voting. Compared to
single-sample voting, the performance of this process is more
consistent and obtained more rapidly.
問合せ先:来嶋(B01)
|
4/19 - 21
| AAAC(6th Annual Meeting of Asian Association for Algorithms and Computation) |
| 投稿〆切 : 2013/1/22 |
| Place : 松島(Hotel Daikanso, Matsushima, Miyagi) |
4/22
| [elc] ELC Seminar (Sampath Kannan) |
| Place : 九州大学伊都キャンパス ウエスト2号館3階第7講義室(W2-327) |
| 日時:4月22日(月)15:00 - 16:30
Generalized Sorting
Sampath Kannan (University of Pennsylvania)
The well-known problem of sorting still has some interesting
Click to Continue ...variations that have not been fully explored. In this talk we
consider the problem when we are given a graph that specifies which
pairs of elements we are allowed to compare.
Under the promise that making all the comparisons will reveal a total
order, we show that it is possible to design a randomized algorithm
that makes about n^{3/2} comparisons on any graph and determines the
total order.
This is joint work with Zhiyi Huang and Sanjeev Khanna.
問合せ先:瀧本(C03)
|
4/24
| 電子情報通信学会コンピュテーション研究会 |
| Place : 神戸大学 |
5/13
| [elc] ELC Seminar (Sanjeev Arora) |
| Place : CELC seminar room |
| ELC seminar
Date and Time: May 13th (Mon.) 14:00 - 15:00
Place: CELC seminar room
*1) polycom access is possible
*2) for using polycom, we decided to have a seminar at the
small seminar room. so if you are coming to the seminar
room, please send a message to Osamu Watanabe
Click to Continue ... watanabe(at)is.titech.ac.jp
Title: Is Machine Learning Tractable? --- Three Vignettes
Speaker: Sanjeev Arora (Princeton University)
Abstract:
Many tasks in machine learning (especially unsupervised learning) are
provably intractable: NP-complete or worse. Nevertheless, researchers
have developed heuristic algorithms to try to solve these tasks in
practice. In most cases, these algorithms are heuristics with no
provable guarantees on their running time or on the quality of
solutions they return. Can we change this state of affairs?
This talk will suggest that the answer is yes, and describe three of our
recent works as illustration. (a) A new algorithm for learning topic
models. (It applies to Linear Dirichlet Allocations of Blei et al. and
also to more general topic models. It provably works under some
reasonable assumptions and in practice is up to 50 times faster than
existing software like Mallet. It relies upon a new procedure for
nonnegative matrix factorization.) (b) What classifiers are worth
learning? (Can theory illuminate the contentious question of what binary
classifier to learn: SVM, Decision tree, etc.?) (c) Provable ICA with
unknown gaussian noise. (An algorithm to provably learn a "manifold"
with small number of parameters but exponentially many "interesting
regions.")
The talk will be self-contained.
(Based upon joint works with Rong Ge, Ravi Kannan, Ankur Moitra, Sushant
Sachdeva.)
|
5/14
| [elc] ELC Seminar on Quantum Query Complexity (C02) |
| Place : CELC |
| 量子質問計算量(Quantum Query Complexity)に関する以下の論文2件を報告する予定です.
Nested Quantum Walks with Quantum Data Structures
(Stacey Jeffery, Robin Kothari, Frederic Magniez
http://arxiv.org/abs/1210.1199
Quantum algorithms for search with wildcards and combinatorial group testing
Click to Continue ...(Andris Ambainis, Ashley Montanaro)
http://arxiv.org/abs/1210.1148
日時: 2013年5月14日13:00~
場所: Center for Exploring the Limits of Computation (CELC)
http://www.al.ics.saitama-u.ac.jp/elc/?celc
連絡先: 興味があって参加したいという方はC02班の山下,河内,西村の誰かにメイルいただければ幸いです.
|
5/14 - 15
| [elc] ELC Workshop on Randomness and Probability Through Computability (A01) |
| 投稿〆切 : 2013/4/19 |
| Place : 東京大学(本郷キャンパス)工学部六号館三階セミナー室AD |
| 問合せ先:河村
|
5/17 - 18
| 電子情報通信学会コンピュテーション研究会 |
| Place : 小樽 |
| アルゴリズム研究会と共同開催
|
5/20
| [elc] ELC Seminar (Bakhadyr Khoussainov) |
| Place : 計算限界解明センター(田町) |
| ELC Seminar
Monday 1 pm, May 20, 2013
Seminar room, ELC Centre, 5th floor of Tokyo Institute of Technology Tamachi office
http://www.al.ics.saitama-u.ac.jp/elc/en/?celc
Algorithmically random infinite structures
Bakhadyr Khoussainov (University of Auckland)
Click to Continue ...
The last two decades have witnessed significant advances in the
investigation of algorithmic randomness of infinite strings.
Monographs by Downey and Hirschfeldt, and by Nies account for the
recent research activities in the area. In spite of much work,
research on randomness of infinite strings has excluded the
investigation of algorithmic randomness for infinite algebraic
structures such graphs, trees, groups or more generally universal
algebras. In this talk, we provide a framework for reasoning about
algorithmic randomness for various classes of infinite structures.
問合せ先:河村(A01班)
|
5/20 - 22
| TAMC 2013 |
| 投稿〆切 : 2013/1/11 |
| Place : Hong Kong, China |
5/21
| [elc] ELC & NII Joint Seminar (Rahul Santhanam) |
| Title: Algorithmic Analysis and Complexity Lower Bounds
Speaker: Rahul Santhanam (Univeristy of Edinburgh)
Date & Time: May 21st, 2013, 15:30-16:30
Place: Tokyo Tech. CIC at Tamachi, 2F, Meeting Room #1
Abstract: I will give an overview of recent work on connections between
Click to Continue ...complexity lower bounds and algorithms for Satisfiability beating brute
force search. On the one hand, Williams established a formal connection
from non-trivial SAT algorithms to circuit lower bounds, and used this
connection to prove that NEXP not in ACC_0. On the other hand, new
algorithms for Satisfiability have been found and analyzed recently by
Impagliazzo-Mathews-Paturi, Seto-Tamaki and myself, with the analysis in
each case inspired by complexity lower bound techniques. In addition to
surveying recent work, I will give some high-level arguments why
algorithmic methods are a promising approach to circuit lower bounds,
and indicate some of the main open problems in this area.
host: Osamu Watanabe and Benjamin Rossman
watanabe@is.titech.ac.jp
|
5/21 - 23
| TQC 2013 |
| 投稿〆切 : 2013/2/5 |
| Place : Guelph, Canada |
5/23
| [elc] ELC Seminar (Xavier Dahan) |
| Place : 九州大学伊都キャンパスウェスト2号館 3階 第5・6講義室 |
| 日時:5/23(木)16:00-17:30
場所:九州大学伊都キャンパスウェスト2号館 3階 第5・6講義室
講演者:Xavier Dahan (九州大学)
題目:高girthのエキスパンダーグラフの代数的な構造
概要:
エキスパンダグラフは30年以上前から、
理論情報学において 様々なところで適用できるものである。
Click to Continue ...2000年代から著しく発展し、非常に注目される分野になった。
その上、高girthグラフの構造は難しい問題と考えられ、
現在の記録を1986のRamanujanグラフによって与えられた。
この発表では、エキスパンダーグラフの面白さや高girthグラフの大事さを説明し、
新しい構造や、構造の試行について記述する。
両者は、1986の有名なRamanujanグラフに関係があります。
|
5/25 - 26
| [elc] ELC Mini-Workshop (B01, C03) |
| Place : 東北大学大学院情報科学研究科棟 2F 大講義室 |
| 5/25(土)
10:30~12:00 Randomness in Algorithm Design(来嶋)
(昼食)
13:00~14:00 領域会議(6/13,14)に向けた準備,今後の方針について
Click to Continue ...14:15~15:15 B01+C03 班の連携の実績紹介
・瀧本,畑埜+来嶋の事例(畑埜)
・内澤+神山の事例(内澤)
15:30~17:30 話題提供トーク
5/26(日)
10:00~12:00 話題提供トーク
(昼食)
13:00~15:00 話題提供・自由討論
|
5/26 - 30
| Eurocrypt 2013 |
| 投稿〆切 : 2012/10/24 |
| Place : Athens, Greece |
5/29 - 31
| Visions of the Theory of Computing |
| Place : UC Berkeley |
6/1 - 4
| STOC 2013 |
| 投稿〆切 : 2012/11/2 |
| Place : Palo Alto |
6/2 - 6
| DAC 2013 |
| Place : Austin |
6/4 - 7
| CCC 2013 |
| 投稿〆切 : 2012/11/30 |
| Place : Palo Alto |
6/4 - 7
| 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications |
| 投稿〆切 : 2013/2/15 |
| Place : Veszprem, Hungary |
6/5 - 7
| 4th International Conference on Mathematics in Sport |
| 投稿〆切 : 2013/1/31 |
| Place : Leuven, Belgium |
6/12
| e-サイエンスに向けた革新的アルゴリズム基盤 第4回シンポジウム |
| Place : 京都大学(吉田キャンパス) |
| 講演予定者(五十音順)
- 岡田真人(東大), 河原林健一(NII), 徳山豪(東北大), 湊真一(北大), 渡辺治(東工大)
|
6/12 - 14
| COLT 2013 |
| 投稿〆切 : 2013/2/8 |
| Place : Princeton, NJ |
6/13 - 14
| [elc] 平成25年度 第1回領域会議 |
| Place : 京都大学本部キャンパス (部屋は詳細を参照してください) |
| 2013年度第1回 ELC領域会議
日時:6月13日9:00~6月14日11:20
場所 : 京都大学本部キャンパス
6月13日午前: 総合研究4号館 1階 共通2
6月13日午後: 総合研究8号館 3階 Sホール
Click to Continue ... 6月14日: 総合研究7号館 1階 情報2講義室
プログラム
6月13日 午前 (場所:総合研究4号館 1階 共通2)
9:00~9:30 領域の方向性:渡辺領域代表、事務局連絡
9:30~9:45 A01班
9:45~10:00 A02班
10:00~10:15 A03班
10:15~10:30 休憩
10:30~10:45 B01班
10:45~11:00 B02班
11:00~11:15 B03班
11:15~11:30 C01班
11:30~11:45 C02班
11:45~12:00 C03班
昼休み
6月13日 午後 (場所:総合研究8号館 3階 Sホール)
13:00~13:15 公募研究班 Skip Jordan (北海道大学)
13:15~13:30 公募研究班 宇野 裕之 (大阪府立大学)
13:30~13:45 公募研究班 安永 憲司 (金沢大学)
13:45~14:00 公募研究班 泉 泰介 (名古屋工業大学)
14:00~14:15 公募研究班 塩浦 昭義 (東北大学)
14:15~14:30 休憩
14:30~14:45 公募研究班 森山 園子 (東北大学)
14:45~15:00 公募研究班 山中 克久 (岩手大学)
15:00~15:15 公募研究班 伊藤 健洋 (東北大学)
15:15~15:30 公募研究班 永田 賢二 (東京大学)
15:30~16:00 休憩&ポスターセッションの準備
16:00~18:00 ポスターセッション
(注:17:00より総合研究8号館 3階 Nホールにて総括班会議を開催)
懇親会
時間 19:00~
場所: 百万遍 しゃらく
http://r.gnavi.co.jp/k614100/map/
6月14日(場所:総合研究7号館 1階 情報2講義室)
9:00~ 9:40 講演: 脊戸 和寿 (電気通信大学)
9:40~ 9:50 休憩
9:50~10:30 講演: 上野 賢哉 (京都大学)
10:30~10:40 休憩
10:40~11:20 講演: 内澤 啓(山形大学)
脊戸 和寿 (電気通信大学)
タイトル: Circuit Satisfiability
アブストラクト: Circuit Satisfiability (CktSAT)とは与えられた論理
回路の出力が1になる入力割当が存在するかどうかを判定する問題である.これは
有名なNP完全問題の1つであり,入力変数の多項式時間では解けそうにない.
それどころか,一般の多項式サイズの回路が与えられるとその充足可能性判定には,
2^n時間必要であると思われている.2010年,Ryan WilliamsはCktSATが2^n
よりも超多項式的に高速にとけるなら,NEXPが多項式サイズの回路をもたないことを
示した.(NEXP not in P/poly) さらに,ある特定の回路クラスCに制限した
CktSAT (C-SAT)が同じように高速にとけるなら,NEXPが多項式サイズのクラスCの
回路をもたないことも示している.(NEXP not in C) これ以降,CktSATに対する
研究は加速し,様々なC-SATに対するアルゴリズムが開発された.現時点でCktSATの
アルゴリズムの開発によって計算量クラスの分離に成功したのは,Ryan Williamsの
NEXP not in ACC0のみであるが,多くのC-SATの結果に付随して,Average
Case HardnessやCorrelation Boundが示されている.これは一種の計算限界を
示すものである.本発表では,一連のCktSATの結果を紹介し,今後の展開について述べる.
上野 賢哉 (京都大学)
タイトル: 非平衡な再帰関数の計算限界
アブストラクト:再帰的に定義された論理関数に対して,論理式サイズ下界を証明する
方法として量子敵対者法を説明し,再帰が非平衡な場合への適用を考えるとともに,
下界証明に対する一般的な証明限界について議論する.
内澤 啓 (山形大学)
タイトル: 論理回路の出力パターン数とその応用
アブストラクト:論理回路とは,AND素子やOR素子などの論理素子を基本素子とする
組合せ回路である.入力が与えられた時に論理回路が行う計算は,回路を構成する
各素子の出力値の組合せ,即ち,出力パターンとして表現できる.ここで,ある回路に
現れる出力パターンの種類の総数を,その回路の出力パターン数と呼ぶ.本講演で
は,この回路の出力パターン数を解析することによって得られる論理回路の下界や,
その他の応用について述べる.
|
6/14 - 19
| [elc] ELC Workshop on Polyhedral Approaches: Extension complexity and pivoting lower bounds |
| Place : Kyoto |
| ELC Workshop on Polyhedral Approaches:
Extension complexity and pivoting lower bounds
(organized by ELC B01,B02)
June 14-19 Kyoto
Please register at https://www.al.ics.saitama-u.ac.jp/elc/reg/2013_wpa/
Click to Continue ...Workshop information: http://www.al.ics.saitama-u.ac.jp/elc/en/?event/2013/0614_0619
There have been some exciting new lower bound results related to
LP pivoting and extension complexity for integer programs, which
are of direct relevance to the ELC project. Progress is swift at
the moment and there are many interesting open problems.
The format of the workshop will be a three day meeting June 14-16
"Bellairs style"(see below) at the guest house Community Sagano
in Arashiyama. All participants are expected to stay on-site. The
meeting will then move to the Clock tower at Yoshida campus of Kyoto
university for June 17-19. A detailed schedule will be prepared at the meeting.
By 'Bellairs style' is meant a workshop which is focused on trying
to solve, or at least make progress on, a fairly narrowly defined
set of problems. There are relatively few talks, and certainly no
pressure to give one. The main point is to be present and actively
participate in the discussions. Due to the nature of the meeting,
the number of participants is limited to about 25 people. Confirmed
overseas participants are:
D. Bremner, B. Cook, K. Fukuda, V.Kaibel, S. Polutta and H. Tiwary
David Avis (avis@i.kyoto-u.ac.jp)
Naoki Katoh (naoki@archi.kyoto-u.ac.jp)
|
6/16 - 20
| EC 2013 |
| 投稿〆切 : 2013/2/11 |
| Place : Philadelphia, Pennsylvania |
6/16 - 21
| ICML 2013 |
| Place : Atlanta, USA |
6/17 - 20
| SoCG 2013 |
| 投稿〆切 : 2013/3/12 |
| Place : Rio de Janeiro, Brazil |
6/21 - 23
| COCOON 2013 |
| 投稿〆切 : 2013/1/6 |
| Place : Hangzhou, China |
6/22 - 27
| SIGMOD/PODS 2013 |
| Place : New York, USA |
6/24
| 電子情報通信学会コンピュテーション研究会 |
| Place : 奈良女子大学 |
6/24
| 電子情報通信学会 コンピュテーション研究会 チュートリアル講演 |
| Place : 奈良女子大学 |
6/24
| [elc] 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 奈良女子大学 |
6/25 - 28
| LICS 2013 |
| 投稿〆切 : 2013/1/14 |
| Place : New Orleans, USA |
6/25 - 29
| CSR 2013 |
| 投稿〆切 : 2012/12/11 |
| Place : Ural Federal University, Ekaterinburg |
6/26
| [elc] NII & ELC Joint Seminar (Saraf & Kopparty) |
| Place : CELC Seminar Room |
| 15:00-17:30
Speaker: Shubhangi Saraf (Rutgers University)
Title: Incidence geometry and applications to theoretical computer
science
The classical theorem of Sylvester-Gallai states the following: given
Click to Continue ...a finite set of points in the Euclidean plane, not all on the same
line, there exists a line passing through exactly two of the points.
This result has a rich and interesting history in mathematics.
Surprisingly in recent years variants of the theorem have been
influential in various diverse areas of theoretical computer science.
In this talk I will describe several extensions to the Sylvester
Gallai theorem - quantitative versions, high dimensional versions,
colorful versions and average case versions. I will also describe
some of the applications and connections in theoretical computer
science to areas such as polynomial identity testing, local
algorithms for error correcting codes as well as lower bounds for
arithmetic computation.
Based on joint works with Albert Ai, Zeev Dvir, Neeraj Kayal and
Avi Wigderson
======================
Speaker: Swastik Kopparty (Rutgers University)
Title: CONSTANT RATE PCPS FOR CIRCUIT-SAT WITH SUBLINEAR QUERY
COMPLEXITY
The PCP theorem says that every NP-proof can be encoded to another
proof, namely, a probabilistically checkable proof (PCP), which can
be tested by a verifier that queries only a small part of the PCP. A
natural question is how large is the blow-up incurred by this
encoding, i.e., how long is the PCP compared to the original NP
proof. The state-of-the-art works of Ben-Sasson, Sudan and Dinur show
that one can encode proofs of length n by PCPs of length
(n polylog n) that can be verified using a constant number of
queries.
I will talk about a recent result, joint with Eli Ben-Sasson, Yohay
Kaplan and Or Meir, showing that one can encode proofs of length n by
PCPs of length O(n), such that the proofs can be checked
with n{epsilon} query complexity (for every epsilon > 0). This is
the first constant-rate PCP construction that achieves constant
soundness with nontrivial query complexity (o(n)).
Our proof replaces the low-degree polynomials codes in traditional
algebraic PCP constructions with algebraic-geometric (AG) codes. We
show that the automorphisms of an AG code can be used to simulate the
role of affine transformations which are crucial in earlier high-rate
algebraic PCP constructions. Using this observation we conclude that
any asymptotically good family of transitive AG codes over a constant
sized alphabet leads to a family of constant-rate PCPs with
polynomially small query complexity. The required family of
transitive AG codes was recently constructed by Henning Stichtenoth,
and appears in the appendix to our paper.
|
6/26 - 28
| FAW-AAIM 2013 |
| 投稿〆切 : 2013/2/16 |
| Place : Dalian Maritime University, Dalian, China (大連海事大学, 大連, 中国) |
| Invited Speakers:
- Jin Akiyama (Tokyo University of Science, Japan)
- Daniel Marx(Computer and Automation Research Institute, Hungarian Academy of Science)
|
7/1 - 3
| SIROCCO 2013 |
| 投稿〆切 : 2013/4/24 |
| Place : Ischia, Italy |
| url : https://sites.google.com/site/sirocco2013italy/ |
7/1 - 4
| EURO 2013 (XXVI EURO – INFORMS Joint International Conference |
| 投稿〆切 : 2013/3/1 |
| Place : Rome, ITALY |
7/1 - 5
| CiE (Computability in Europe) 2013 |
| 投稿〆切 : 2013/5/31 |
| Place : ミラーノ(伊) |
| 査読つき講演は既に締切られましたが一般講演(Informal Presentations)を5月末まで受付けています
|
7/7
| ICALP 2013 Satellite Workshop on Learning Theory and Complexity |
| 投稿〆切 : 2013/4/10 |
| Place : Riga, Latvia |
7/8 - 11
| CCA 2013 (Tenth International Conference on Computability and Complexity in Analysis) |
| 投稿〆切 : 2013/5/20 |
| Place : ナンシー(仏) |
| 論文つき発表の締切:4月1日
論文なし発表の締切:5月20日
|
7/8 - 12
| SAT 2013 |
| 投稿〆切 : 2013/2/8 |
| Place : Helsinki, Finland |
7/8 - 12
| ICALP 2013 |
| 投稿〆切 : 2013/2/15 |
| Place : Riga, Latvia |
7/10 - 12
| IWOCA 2013: 24th International Workshop On Combinatorial Algorithms |
| 投稿〆切 : 2013/4/1 |
| Place : Rouen, France |
7/14 - 18
| AAAI-13 |
| 投稿〆切 : 2013/1/22 |
| Place : Bellevue, Washington, USA |
7/16
| [elc] ELC Seminar on Quantum Query Complexity (C02) |
| Place : CELC |
| 量子ウォークのグラフ問題の適用について議論する。
|
7/16 - 18
| 夏のLAシンポジウム |
| 投稿〆切 : 2013/6/14 |
| Place : 志賀島 (福岡県) |
7/22 - 24
| PODC 2013 |
| 投稿〆切 : 2013/2/10 |
| Place : Montreal, Canada |
7/23 - 25
| SPAA 2013 |
| 投稿〆切 : 2013/2/13 |
| Place : Montreal, Canada |
7/28 - 30
| [elc] ELC International Meeting on ''Inference, Computation, and Spin Glasses'' (ICSG2013) |
| Place : Hokkaido Univ. (Sapporo) |
| 韓国で開かれる統計力学の大きな国際会議のサテライトワークショップとしてC01班で企画
したワークショップです.是非ご参加をご検討ください.
|
7/29 - 30
| 回路とシステムワークショップ |
| 投稿〆切 : 2013/4/12 |
| Place : 淡路夢舞台国際会議場 |
8/1
| [elc] ELC Seminar on Computation and Stat. Physics (C01) |
| Place : CELC seminar room |
| Date: 2013.8.1 (Thu)
Time: 14:00 - 18:00
Place: CELC seminar room
Speakers (only guest speakers, some from C01 will give a talk also)
Erik Aurell (KTH, Stockholm)
Click to Continue ...
Title: The inverse Ising problem and its generalizations have
emerged as a common point of interest
Abstract:
Learning spatial amino acid contacts from many homologous protein sequences
of statistical physics and machine learning. A major success has been
achieved in determining physical proximity of amino acid residues in
families of homologous proteins by learning an appropriate Potts model
where each variable can take 21 states representing the 20 amino acids
and a gap in an alignment (Lapedes et al 2001 (unpub), Weigt et al 2009,
Marcos et al 2011, Hopf et al 2012 and many follow-up papers).
Improving such contact predictions can be achieved by (at least) (i) starting
from better and/or more appropriate protein families and sequence alignments
(ii) learning the Potts model more accurately and (iii) learning other models
which allow for better prediction of the protein structures. I will review
these points with an emphasis on (ii) and (iii) and discuss why it appears
to make sense to learn such relatively simple models as Potts models to
describe in principle a quite complicated trace left in the molecular
record by evolution.
Our work in this direction is presented in Ekeberg et al Phys. Rev. E 87,
012707 (2013) and our codes are available at plmdca.csc.kth.se.
Pinyang Lu (Microsoft, Shanghai)
Title: Approximate Counting via Correlation Decay
Abstract:
In this talk, I will survey some recent development of approximate counting
algorithms based on correlation decay technique. Unlike the previous major
approximate counting approach based on sampling such as Markov Chain Monte
Carlo (MCMC), correlation decay based approach can give deterministic fully
polynomial-time approximation scheme (FPTAS) for a number of counting
problems.
|
8/3 - 9
| IJCAI 2013 |
| Place : Beijin, China |
8/7 - 10
| CCCG 2013 (25th Canadian Conference on Computational Geometry) |
| 投稿〆切 : 2013/5/6 |
| Place : ウォータールー(加) |
8/12 - 14
| WADS 2013 |
| 投稿〆切 : 2013/2/20 |
| Place : University of Western Ontario |
8/16 - 17
| [elc] ELC Mini-Workshop (B03) |
| Place : 奈良 |
| 会場: やまとビル 5F 大会議室B
やまと会議室 http://www.yamatobill.jp/
奈良県奈良市登大路町36番地 (近鉄奈良駅そば)
予定:
8月16日(金) 13:00~16:30 話題提供セッション
8月17日(土) 09:00~12:30 問題解決セッション
Click to Continue ...
|
8/18 - 20
| CRYPTO 2013 |
| Place : Santa Barbara, California |
8/21 - 23
| APPROX-RANDOM 2013 |
| 投稿〆切 : 2013/4/17 |
| Place : UC Berkeley, USA |
8/22 - 12/20
| Real Analysis in Computer Science |
| Place : UC Berkeley, USA |
8/22 - 12/20
| Theoretical Foundations of Big Data Analysis |
| Place : UC Berkeley |
8/23 - 25
| ISORA 2013: The 11th International Symposium on Operations Research and its Applications in engineering, technology and management |
| 投稿〆切 : 2013/5/31 |
| Place : 黄山 (Yellow Mountain), 中国 |
8/26 - 30
| MFCS 2013 |
| 投稿〆切 : 2013/4/19 |
| Place : Klosterneuburg, Austria |
8/26 - 30
| VLDB 2013 |
| Place : Riva del Garda, Italy |
8/27 - 29
| Horizons in TCS: A Celebration of Mihalis Yannakakis’s 60th Birthday |
| Place : NJ, USA |
9/2 - 5
| CSL 2013 |
| Place : Torino |
9/2 - 6
| ALGO 2013 |
| Place : Sophia Antipolis, France |
| ESAはこの中で行われます。
|
9/3
| 電子情報通信学会コンピュテーション研究会 |
| 投稿〆切 : 2013/6/5 |
| Place : 鳥取環境大 |
9/4 - 6
| FIT |
| Place : 鳥取大学 鳥取キャンパス |
9/6
| [elc] FIT2013 イベント企画 (JST ERATO 湊PJ/河原林PJとの共同企画) |
| Place : 鳥取大学 鳥取キャンパス |
| FIT 2013 (第12回情報科学技術フォーラム) でのイベント企画で、
JST ERATO 湊 離散構造処理系プロジェクト、JST ERATO 河原林 巨大グラフプロジェクト
との共同企画です。
|
9/8
| [elc] ELC Mini-Workshop (B01) |
| Place : 京都大学桂キャンパスC2棟213号室 |
| プログラム:
10:30 -- 12:00 研究進捗状況の報告
12:00 -- 13:00 昼休み
13:00 -- 14:30 研究進捗状況の報告
14:30 -- 15:00 休憩
15:00 -- 17:00 議論
Click to Continue ...
|
9/10 - 12
| 日本OR学会秋期研究発表会・シンポジウム |
| 投稿〆切 : 2013/7/1 |
| Place : 徳島大学常三島キャンパス |
| 9/10 シンポジウム
9/11-12 研究発表会
|
9/10 - 14
| Graph Theory Conference(江川嘉美教授還暦記念研究集会) |
| Place : 東京理科大(神楽坂) |
9/16 - 20
| CP 2013 |
| Place : Uppsala |
9/17
| [elc] ELC Seminar (C01 and A01) |
| Place : CELC |
| Date: 2013.9.17 (Tue)
Time: 14:00 - 17:00
Place: CELC seminar room (new one! on the 4the floor)
Speakers:
1. Sebastian Muller (ELC Postdoc fellow, C01 and A01)
Polylogarithmic Cuts in Models of Weak Arithmetic
Click to Continue ...
2. Xiaohui Bei (Nanyang Technological Univ., Singpore)
On the Complexity of Trial and Error
3. Ning Chen (Nanyang Technological Univ., Singpore)
Solving Linear Programming with Constraints Unknown
Details (with abstracts):
1. Sebastian Muller (ELC postdoc reseaercher, C01 and A01)
Title: Polylogarithmic Cuts in Models of Weak Arithmetic
Abstract:
Propositional proof systems are polynomial time computable surjective
functions that map strings to propositional tautologies. We call any
preimage of a tautology a proof. Properties of such systems are
closely related to the coNP = NP question; in fact, coNP = NP iff
such a proof system exists with short proofs for every tautology.
In this light it is interesting to compare two proof systems by
their minimal lengths of proofs for any family of tautologies. We say
that one proof system simulates another, if for any proof in the
latter system there is one in the former system that is approximately
of the same length. Two examples of propositional proof systems are
Frege systems and bounded depth Frege systems. These systems are
textbook style proof systems as are depicted in most basic logic
literature. They differ in strength, however, and we do not expect
bounded depth Frege systems to simulate Frege systems.
Models of weak arithmetics are well known to capture the strength of
certain such propositional proof systems. We exploit this property
to explore the relation between Frege and bounded depth Frege systems.
More precisely we will show that a certain initial segment of any
model that relates to bounded depth Frege systems, relates to Frege
systems. An easy argument will then allow us to turn Frege proofs of
any given length into bounded depth Frege proofs such that the proof
length is not increased exponentially. This yields a sub-exponential
simulation of Frege by bounded depth Frege systems.
2. Xiaohui Bei (Nanyang Technological Univ., Singpore)
Title: On the Complexity of Trial and Error
Abstract:
Motivated by certain applications in which the objects
under investigation are unknown or not directly accessible because
of various limitations, we propose a trial-and-error model to examine
search problems in which inputs are unknown.
More specifically, we consider constraint satisfaction problems
$\bigwedge_i C_i$, where the constraints $C_i$ are hidden, and the
goal is to find a solution satisfying all constraints. We can
adaptively propose a candidate solution (i.e., trial), and there is
a verification oracle that either confirms that it is a valid solution,
or returns the index $i$ of a violated constraint (i.e., error), with
the exact content of $C_i$ still hidden.
We studied the time and trial complexities of a number of natural
CSPs, summarized as follows. On one hand, despite the seemingly very
little information provided by the oracle, efficient algorithms do
exist for Nash, Core, Stable Matching, and SAT problems, whose
unknown-input versions are shown to be as hard as the corresponding
known-input versions up to a factor of polynomial. The techniques
employed vary considerably, including, e.g., order theory and the
ellipsoid method with a strong separation oracle.
On the other hand, there are problems whose complexities are
substantially increased in the unknown-input model. In particular,
no time-efficient algorithms exist for Graph Isomorphism and Group
Isomorphism (unless PH collapses or P = NP). The proofs use quite
nonstandard reductions, in which an efficient simulator is carefully
designed to simulate a desirable but computationally unaffordable
oracle.
Our model investigates the value of input information, and our
results demonstrate that the lack of input information can introduce
various levels of extra difficulty. The model accommodates a wide
range of combinatorial and algebraic structures, and exhibits
intimate connections with (and hopefully can also serve as a useful
supplement to) certain existing learning and complexity theories
3. Ning Chen
Title: Solving Linear Programming with Constraints Unknown
Abstract:
What is the value of information in solving linear programming?
The celebrated ellipsoid algorithm tells us that the full
information of input constraints is not necessary; the algorithm
works as long as there exists an oracle that, on a proposed
candidate solution, returns a violation in the format of a
separating hyperplane. Can linear programming still be efficiently
solved if the returned violation is in another format?
We study this question in the aforementioned trial-and-error setting.
We give an algorithm with running time $O(m^{poly(n)} * L)$,
where $m$ and $n$ are the numbers of constraints and variables,
respectively, and $L$ is the input size of the linear program.
The exponential dependence on $n$ is unfortunately unavoidable; we
show a lower bound of $\Omega(m^{[n/2]})$ on the number of queries
needed. Meanwhile, if the oracle provides more violation
information---the index of a "most violated" constraint, measured
by the Euclidean distance of the proposed solution and the
half-spaces defined by the constraints---then we show that the
linear program can be solved in polynomial time.
The proofs of the results employ a variety of geometric techniques,
including McMullen's Upper Bound Theorem, the weighted spherical
Voronoi diagram, and the furthest Voronoi diagram. In addition, we
give an alternative proof to a conjecture of Laszlo Fejes Toth on
bounding the number of disconnected components formed by the
union of $m$ convex bodies in $R^n$. Our proof, inspired by the
Gauss-Bonnet Theorem in global differential geometry, is independent
of the known and clearly reveals more insights into the problem
and bound.
END OF SEMINAR INFO.
|
9/17 - 19
| The 12th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2013) |
| 投稿〆切 : 2013/6/28 |
| Place : 東京理科大学(神楽坂キャンパス) |
| 秋山仁先生の東京理科大着任記念の国際会議です。
Invited Plenary Speakers:
- Sergey Bereg (The University of Texas at Dallas)
- Erik Demaine (MIT)
- Ferran Hurtado (Universitat Politecnica de Catalunya)
- Ken-ichi Kawarabayashi (NII)
Click to Continue ...- David Kirkpatrick (UBC)
- Stefan Langerman (ULB)
- Janos Pach (NYU)
- Kokichi Sugihara (Meiji U)
- Jorge Urrutia (Universidad Nac. Aut. de Mexico)
|
9/20
| [elc] UEC & ELC Joint Seminar on Theoretical Computer Science |
| Place : AV hall, 3F, West-9 BLDG, The University of Electro-Communications(電気通信大学, 西9号館, 3F AVホール) |
| Speakers: 1. John Iacono (Polytechnic Institute of New York University),
2. Stefan Langerman (Universite Libre de Bruxelles)
3. Erik D. Demaine (MIT)
--
UEC & ELC Joint Seminar on Theoretical Computer Science
We are going to have a seminar on Theoretical Computer Science,
Click to Continue ...which consists of three talks by distinguished researchers.
We hope you all participate.
--
Time and Date: 13:30--16:20, Sept.20, 2013.
Place: AV hall, 3F, West-9 BLDG, The University of Electro-Communications
Program ----
13:30--14:30
John Iacono (Polytechnic Institute of New York University)
Title: In pursuit of the dynamic optimality conjecture
Abstract:
In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting
binary search tree algorithm. Splay trees were conjectured to perform
within a constant factor as any offline rotation-based search tree
algorithm on every sufficiently long sequence---any binary search tree
algorithm that has this property is said to be dynamically optimal.
However, currently neither splay trees nor any other tree algorithm is
known to be dynamically optimal. Here we survey the progress that has
been made in the almost thirty years since the conjecture was first
formulated, and present a binary search tree algorithm that is
dynamically optimal if any binary search tree algorithm is dynamically
optimal.
--
14:30--15:20
Stefan Langerman (Universite Libre de Bruxelles)
Title: Bichromatic compatible matchings
Abstract:
For a set $R$ of $n$ red points and a set $B$ of $n$ blue points, a
$BR$-matching is a non-crossing geometric perfect matching where each
segment has one endpoint in $B$ and one in $R$. Such a matching always
exists. Two $BR$-matchings are compatible if their union is also
non-crossing. We prove that, for any two distinct $BR$-matchings $M$
and $M'$, there exists a sequence of $BR$-matchings $M = M_1, ..., M_k
= M'$ such that $M_{i-1} $ is compatible with $M_i$.
Joint work with Greg Aloupis, Luis Barba, and Diane L. Souvaine
--
15:30--16:20
Erik D. Demaine (MIT)
Title: Geometric Folding Algorithms: Linkages, Origami, Polyhedra
Abstract:
What forms of origami can be designed automatically by algorithms?
How might we build reconfigurable robots like Transformers or Terminator 3,
hinging together a collection of pieces that dynamically reconfigure
into arbitrary shapes? When can a robotic arm of rigid rods be folded into
a desired configuration? What shapes can result by folding a piece of
paper flat and making one complete straight cut? What 3D surfaces can be
manufactured from a single sheet of material? How might proteins fold?
Geometric folding is a branch of discrete and computational geometry
that addresses these and many other intriguing questions.
I will give a taste of the many results that have been proved in the past
several years, as well as the several exciting unsolved problems that remain
open. Many folding problems have applications in areas including
manufacturing, robotics, graphics, and protein folding.
--
Organizer: Hiro Ito (School of Informatics and Engineering, UEC)
|
9/20
| [elc] ELC・岡田新学術領域合同シンポジウム/公募説明会 |
| Place : 九州大学 伊都キャンパス ウエスト2号館3F 325・326号室 |
| 日程:2013年9月20日(金) 10:30 - 16:45
会場:九州大学 伊都キャンパス
ウエスト2号館3F 325・326号室
ホームページ(岡田新学術領域):
http://sparse-modeling.jp/symposium/mini_symposium_Kyushu.html
Click to Continue ...
プログラム
10:30 - 11:30 岡田真人(東京大学/新領域創成科学研究科)
「新学術領域 疎性モデリングの目的・狙い / 公募研究募集についての説明 」
11:30 - 12:00 瀧本英二(九州大学)
「新学術領域 ELCの概要+C03 班の研究概要」
12:00 - 13:30 昼食
13:30 - 14:00 末廣大貴(九州大学)
「1ノルムソフトマージン最適化に基づくランキング学習」
14:00 - 14:30 内澤啓(山形大学)
「Computational Power of Threshold Circuits with Sparse Activity」
14:30 - 15:00 篠原歩(東北大学)
「決定性有限オートマトンの最小無矛盾問題について」
15:00 - 15:15 休憩
15:15 - 15:45 高橋成雄(東京大学)
「微分トポロジーに基づく多次元・多変量データ解析と可視化」
15:45 - 16:15 永田賢二(東京大学)
「スペクトル分解によるデータ駆動科学」
16:15 - 16:45 渡辺澄夫(東京工業大学)
「非正則な統計モデルのベイズ法における評価方法について」
なお,シンポジウム終了後懇親会を予定しています.
参加希望の方は9/17までに九大畑埜(hatano(a)inf.kyushu-u.ac.jp)までお知らせください.
|
9/24 - 26
| [elc] ELC 計算量理論の秋学校 |
| Place : 文化軽井沢山荘 |
| --------------
[日時] 9/24(火)14時〜9/26(木)12時
(初日受付は 13:30〜を予定)
[場所] 文化軽井沢山荘
http://www.bunkakaruizawasansou.com/
Click to Continue ...
軽井沢駅から車で15分(現在,送迎バスの依頼を検討中)
[プログラム]
9月24日(火) 14:00〜 9月26日(木) 12:00
(1時間x2コマ)x4人+自由討論
※ 詳細は決まり次第アナウンス致します
・河村彰星先生(東大)
「連続系の計算量」
・神山直之先生(九大)
「最適化手法と計算限界解析:双対性と整数性」
・津田宏治先生(産総研)
「ZDDに基づくグラフ要素列挙と、配電網最適化への応用」
・森前智行先生(群馬大)
「量子計算の基礎とInstantaneous Quantum Polynomial time」
(*) 自由討論で話題提供できる方を募集しています.
ELC関係者で共有したい話題,例えば
「ご自身または他人の面白い結果」「未解決問題や研究課題」
などがございましたら,ご一報いただけますと幸いです.
[参加費] 無料(宿泊費と懇親会代は現地で実費精算です)
大学院生以上で旅費支援が必要な場合にもご相談ください.」
宿泊費用
一般 27,000円程度
学生 20,000円程度
です.
当日受付にてお支払ください.
お釣りのないようにご準備お願いいたします.
----------------
問い合わせ先:小柴健史(koshiba@mail.saitama-u.ac.jp)
|
9/24 - 27
| [elc] ELC 暗号理論秋学校 |
| Place : 河口湖クラブセントビレッヂ |
| 実行委員: 河内 亮周 (東工大), 田中 圭介 (東工大)
講師: 河内亮周(東工大), 草川 恵太(NTT), 安永 憲司(金沢大), 松田 隆宏(AIST)
プログラム:
1限 9:00-10:15
2限 10:45-12:00
Click to Continue ...3限 13:00-14:15
4限 14:45-16:00
5限 16:30-17:45
9月24日
3限 河内: 擬似乱数性の統一理論(1)
4限 河内: 擬似乱数性の統一理論(2)
5限 河内: 擬似乱数性の統一理論(3)
25日
1限 草川: 完全準同型性暗号(1)
2限 安永: ブラックボックス構成とその限界(1)
3限 草川: 完全準同型性暗号(2)
4限 安永: ブラックボックス構成とその限界(2)
5限 草川: 完全準同型性暗号(3)
26日
1限 草川: 完全準同型性暗号(4)
2限 安永: ブラックボックス構成とその限界(3)
3限 草川: 完全準同型性暗号(5)
4限 松田: 公開鍵暗号の基礎理論(1)
5限 松田: 公開鍵暗号の基礎理論(2)
27日
1限 松田: How to Write a Paper (1)
2限 松田: How to Write a Paper (2)
|
9/25 - 27
| RP2013 (The 7th International Workshop on Reachability Problems) |
| 投稿〆切 : 2013/5/24 |
| Place : University of Uppsala, Sweden |
10/6 - 9
| ALT 2013 |
| 投稿〆切 : 2013/5/11 |
| Place : Singapore |
10/17
| [elc] ELC Seminar (Andrej Bogdanov) |
| Place : CLEC Seminar Room |
| ELC C01 Seminar Announcement
Date: Oct. 17th (Thu)
Time: 14:00 - (followed by some talk by Osamu Watanabe)
Place: CELC Seminar room
http://www.al.ics.saitama-u.ac.jp/elc/celc/
Title: On the complexity and security of homomorphic encryption
Click to Continue ...Speaker: Andrej Bogdanov (Chinese Univ. of Hong Kong)
An encryption scheme is called homomorphic if given encryptions of
several plaintexts, one can compute an encryption of some function of
them (for example their sum) using public information only. This
feature is useful for applications like electronic voting and secure
outsourcing of computation.
We study homomorphic encryption from a complexity-theoretic
perspective. We show that:
1. For any sufficiently "sensitive" function f, if an encryption
scheme supports homomorphic evaluation of f, then this scheme cannot
be proved NP-hard to break (under widely believed complexity
assumptions).
2. For almost any function f, the ability to homomorphic evaluate f
implies the ability to rerandomize ciphertexts (turn a ciphertext
into another functionally equivalent but statistically independent
one).
3. Certain encryption schemes (both private and public key) can be
implemented by circuits of small depth, but homomorphic evaluation of
any nontrivial functionality requires large circuit depth.
Our results can be viewed as evidence that homomorphic encryption
schemes are inherently more complex and possibly less secure than
ordinary ones.
The talk is based on joint works with Chin Ho Lee.
END OF ANNOUNCEMENT
|
10/18
| 電子情報通信学会コンピュテーション研究会 |
| Place : 名工大 |
10/18
| [elc] 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 名古屋工業大学 |
10/23 - 9/26
| TUG 2013 (TeXの国際会議) |
| 投稿〆切 : 2013/7/15 |
| Place : 東京大学 駒場キャンパス |
10/27 - 29
| FOCS 2013 |
| 投稿〆切 : 2013/4/3 |
| Place : Berkeley Marina, Berkeley, California, USA |
10/29 - 30
| RAMPシンポジウム |
| Place : 鹿児島大学稲盛会館 |
11/7
| [elc] ELC Mini-Workshop (C01) |
| Place : CELC seminar room |
| Date: Nov. 7th (Thu)
Time: 14:00 - 17:00 (with some coffee breaks)
Place: CELC Seminar room
(In the order of talks)
Speaker: Haiping Huang (JSPS research fellow, Tokyo Inst. of Tech., Japan)
Title: Entropy landscape analysis of the binary perceptron problem
Click to Continue ...Abstract:
In artificial intelligence, a binary perceptron is a device classifying
patterns with many inputs by assigning individual weights to each input,
and the weights take binary values. Often, these weights have to be
inferred from a set of examples. However, it is difficult to find a
low-complexity algorithm to identify these weights. Statistical
physicists started to study this problem 25 years ago by analyzing
the solution space of binary weights. However, the relation between
the solution space structure and the algorithmic hardness has not yet
been fully understood. Our work demonstrates two interesting effects
in the solution space through the entropy landscape analysis:
(1) clustering refers to the fragmentation of the solution space into
well-separated clusters; (2) freezing refers to the appearance of
isolated solutions instead of clusters of exponentially many close-by
solutions.
Our results explain the observed glassy behavior of stochastic local
search heuristics and are also expected to shed light on other hard
problems in information processing (e.g., channel coding systems).
Speaker: Mikko Vehkapera (Aalto University, Finland and KTH, Sweden)
Title: Compressed sensing with correlated measurement matrices and
application to metagenomics
Abstract:
In the first part of the talk, we review some analytical results
that characterize the performance of convex relaxation
based recovery algorithms used in compressed sensing.
In particular we are interested in the case where the
measurement matrix is of some other type than the standard
Gaussian ensemble. Using replica method, we show that under certain
conditions there are matrix ensembles that offer improved
performance of convex relaxation based recovery when compared
to the standard Gaussian ensemble.
The second part of the talk consists of examining a practical
problem of estimating bacterial community composition from
a high-throughput sequenced sample. Current estimation methods
that provide accurate results are typically computationally complex
and require the use of computing cluster. Using a method inspired by
sparsity enforcing techniques from compressed sensing, we propose a
fast solution to the aforementioned metagenomics problem. The model
solution is obtained both by using convex optimization tools and
through a greedy iterative algorithm and shown to provide good
accuracy-complexity tradeoff for the current problem.
END OF ANNOUNCEMENT
|
11/11 - 15
| 1st Mexican Conference on Discrete Mathematics and Computational Geometry |
| Place : Oaxaca, Mexico |
| Honoring Jorge Urrutia on the occasion of his 60th birthday
|
11/12
| [elc] サイエンスカフェ 「計算の限界って?」 |
| Place : 東京工業大学 大岡山キャンパス 博物館・百年記念館 3階フェライト記念会議室 |
11/13 - 16
| [elc] SSS 2013 |
| 投稿〆切 : 2013/7/15 |
| Place : 大坂 |
11/18
| [elc] ELC Seminar (Ralf Borndrfer) |
| Place : 九州大学 伊都キャンパス |
| 日時:2013年11月18日(月)13:30-16:00
場所:九州大学 伊都キャンパス 数理学研究教育棟/マス・フォア・インダストリ研究所3F 中セミナー室7
講演者:Ralf Borndörfer (Zuse Institute Berlin)
参考URL:
http://www.imi.kyushu-u.ac.jp/seminars/view/1211
http://www.imi.kyushu-u.ac.jp/seminars/view/1212
Click to Continue ...13:30-14:30
Title: Optimization in Traffic and Transport
Speaker: Ralf Borndörfer (Zuse Institute Berlin)
Abstract:
The mathematical treatment of planning problems in public transit,
air, and rail traffic has made enormous advances in the last decade.
Classical problems of vehicle and crew scheduling can nowadays be
solved on a routine basis and for large scenarios using combinatorial
optimization methods. This is not yet the case for problems that
pertain to the design of public transit networks, and for problems of
operations control that address the implementation of a schedule in
the presence of disturbances. The talk surveys the state-of-the-art
and some exciting developments in the area, and it addresses major
challenges for the future.
15:00-16:00
Title: Configuration Models in Transport Optimization
Speaker: Ralf Borndörfer (Zuse Institute Berlin)
Abstract:
Configurations are local solutions of network optimization problems
that can be used to assemble an overall solution. They are used to
express complex requirements, that would be hard to formulate using
constraints, by means of a local and hence manageable enumeration of
``feasible configurations''. This gives rise to an extended
formulation involving additional configuration variables. Usually,
one has to make choices between several possible configurations, such
that configuration models are often of a set packing, partitioning,
or covering type. Such a formulation is combinatorially clean and
lends itself to column generation techniques. If the configurations
capture a core aspect of the problem, such a model will be provably
strong, if the configurations can be computed efficiently, it is
algorithmically tractable. Typical examples of configuration models
come up in transport optimization, where the integrated treatment of
technical etc. constraints or the simultaneous solution of
multi-stage models is a major challenge. Successful applications
include railway track allocation, leading to path packing
configuration models, railway rotation planning, resulting in
hypergraph assignment and flow models, and depot management as well
as line planning, leading to set partitioning type models. All of
these models provide strong LP bounds and can be solved efficiently
for large scale real-world problems. The talk surveys these results.
It is based on joint work with Martin Grötschel, Olga Heismann, Heide
Hoppmann, Marika Karbstein, Torsten Klug, Markus Reuther, Thomas
Schlechte, Elmar Swarat, and Steffen Weider.
問合せ先:来嶋(B01)
|
11/21
| 情報処理学会関西支部 定期講演会『ゲーム・パズルの数理』 |
| Place : 大阪大学中之島センター 3F講義室301 |
11/22
| [elc] ELC Seminar (Ravi Montenegro) |
| Place : 九州大学 伊都キャンパス |
| 日時:11/22(金)10:30-12:00
場所:九州大学 伊都キャンパス ウェスト2号館 3階 第5・6講義室
講演者:Ravi Montenegro (University of Massachusetts Lowell)
題目:A sharp heuristic for complexity of some Birthday attacks
inspired by Markov Processes
概要:
Click to Continue ...Birthday attacks use probabilistic "paradoxes'' to solve
cryptographic problems. However, the heuristics used to justify such
methods are usually not strong enough to differentiate a more
efficient approach from a less efficient one. We remedy this
shortcoming with a rigorous result for Pollard's Kangaroo method for
discrete logarithm, and extend it with a very precise heuristic that
applies to those attacks which are modeled on a Markov chain. This
precision makes it possible to explain the differing performance
between attacks that are superficially similar, such as Pollard's
Rho for discrete logarithm when compared to Teske's additive
version, and can also be used in optimizing birthday attack design.
問合せ:来嶋(B01)
|
11/29 - 30
| [elc] 平成25年度 第2回領域会議 |
| Place : 東北大学 |
| 平成25年度第2回 ELC領域会議
日時 11月 29日,30日
場所:東北大学 青葉山キャンパス 情報科学研究科棟 2階 大講義室
アクセス情報:下記のサイト参照
Click to Continue ... http://www.is.tohoku.ac.jp/access/index.html
仙台駅前(西口)バス停から,710, 713, 715, 719 のいずれかに乗り,
情報科学研究科前バス停にて下車.所要時間は,20~40分です.
時刻表: http://www.donto.co.jp/timetable/citybus/bus_d_result.cgi?SW=90&TG=C&BSC=0050052
プログラム
11月29日
12:45~13:00 事務局連絡
13:00~13:50 講演: Benjamin Rossman (NII)
13:50~14:05 休憩
14:05~14:55 講演: 吉田 悠一 (NII)
14:55~15:10 休憩
15:10~16:00 講演: 畑埜 晃平 (九大)
16:10~17:30 総括班会議 (情報科学研究科棟2階 中講義室)
18:30~ 懇親会 居酒屋赤べこ
http://www.hotpepper.jp/strJ000026165/
11月30日
9:30~11:40 ポスターセッション
A01~C03 班までの各班が1件のポスター発表を**必ず**行う.
ここで,各班には,計画班だけでなく,公募班も含まれる.
13:00~13:50 講演: David Avis (京大)
13:50~14:05 休憩
14:05~14:55 講演: 渋谷 哲朗 (東大)
14:55~15:10 休憩
15:10~16:00 講演: 渡辺 治 (東工大)
16:00~16:15 事務局連絡
Benjamin Rossman (NII)
タイトル: Formulas vs. Circuits for Small Distance Connectivity
アブストラクト: We give the first super-polynomial separation in the power
of bounded-depth (unbounded fan-in) boolean formulas vs.
circuits. We consider the problem STCONN(k(n)) of
determining whether or not an n-vertex graph contains a
path of length <= k(n) between two distinguished vertices.
It is well known that STCONN(k(n)) has *circuits* of size
poly(n) and depth log(k). In contrast, we prove that
*formulas* of depth log(k) require size n^Omega(log(k)) for
all k(n) <= loglog(n). As a corollary, this implies a tight lower
bound of Omega(log(k)) on the depth of polynomial-size
circuits for STCONN(k(n)), improving the previous
Omega(loglog(k)) lower bound of Beame, Impagliazzo and
Pitassi [FOCS 1995].
吉田 悠一 (NII)
タイトル: A Characterization of Locally Testable Affine-Invariant
Properties through Decomposition Theorems
アブストラクト: Let P be a property of functions Fp^n → {0, 1} for a fixed
prime p. An algorithm is called a tester for P if, given a query
access to the input function f, with high probability, it accepts
when f satisfies P and rejects when f is “far” from satisfying
P. In this paper, we give a characterization of affine-invariant
properties that are testable with a constant number of
queries. The characterization is stated in terms of
decomposition theorems, which roughly say that any function
can be decomposed into a structured part that is a function
of a constant number of polynomials, and a pseudo-random
part whose Gowers norm is small. We first show an algorithm
that tests whether the structured part of the input function
has a specific form. We then show that an affine-invariant
property is testable with a constant number of queries if and
only if it can be reduced to the problem of testing whether the
structured part of the input function is close to one of a
constant number of candidates.
畑埜 晃平 (九大)
タイトル: メタラウンディングに基づく離散構造のオンライン予測
アブストラクト: 離散構造のオンライン予測問題は,ルーティングやランキング,ス
ケジューリングなど多くの分野に現れる.離散構造の例としては
s-t パス,集合被覆,順列などが挙げられる.予測者の目標は後
から見て最適な固定の離散構造に匹敵する予測をオンラインで
行うことである.この問題に対する汎用的なアプローチは,対応す
るオフライン(近似)離散最適化アルゴリズムをオラクルとして用
いる事である.これをオフライン-オンライン変換と呼ぶ.しかし,
現在知られ ているオフライン-オンライン変換手法は効率的で
はない.そこで本研究では,オフライン近似アルゴリズムが緩和
に基づく場合において,より効率的なオフライン-オンライン変
換手法を提案する.本研究ではメタラウンディングという特殊な
ウンディングを用いる事により,見通しのよい アルゴリズム設
計・解析が可能となった.
David Avis (京大)
タイトル: Exponential bounds for linear programs
アブストラクト: The first part of talk outlines joint work with Hans Tiwary
on finding exponential bounds for the extension complexity
of various NP-hard problems, including restrictions of
MAX_CUT. The second part outlines joint work with Oliver
Friedmann on finding an exponential lower bound on
Cunninham's pivot selection rule for linear programs and
unique sink orientations of hypercubes. Finally I will
discuss briefly some experimental results on a parallel
implementation of reverse search for vertex and
triangulation enumeration, which is joint work with Gary
Roumanis and Yuji Ishikawa.
渋谷 哲朗 (東大)
タイトル: Indexing Protein 3-D Structures for Faster Similarity Search
アブストラクト: Searching for protein structure-function relationships using
three-dimensional (3D) structural coordinates represents
a fundamental approach for determining the function of
proteins with unknown functions. Since protein structure
databases are rapidly growing in size, the development of
a fast search method to find similar protein substructures
by comparison of protein 3D structures is essential. In this
talk, we introduce a new indexing algorithm for fast protein
3-D structure similarity queries which is designed based
on a statistical model of the target 3-D structures. The new
method runs in O(m + N/m^{0.5}) average-case time, after
O(N log N) preprocessing, where N is the database size
and m is the query length. It is about 2 to 50 times faster
than the previous practically best-known O(N) algorithm,
which was also proposed previously by us, even if we
include the preprocessing time. It is almost 20-1000 times
faster than the naive comparison algorithm, according to
experiments on a huge SCOP database.
渡辺 治 (東工大)
タイトル:平面グラフの到達可能性の省スペース計算可能性
アブストラクト: We show that the reachability problem over directed planar
graphs can be solved simultaneously in polynomial time
and sublinear space, more precisely, O(n^{1/2+eps}) space
by using sublinear space algorithm computing a constant
ratio separator of planar graphs. In this talk we explain the
outline of our approach and report and then we report our
recent improvements on both reachability algorithm and
separator algorithm, which leads us to a new O(n^{1/2})
space and polynomial time algorithm for the planar graph
reachability problem. This is a joint work with T. Asano,
D.G. Kirkpatrick, T. Imai, K. Nakagawa, A. Pavan, and
N.V. Vinodchandran.
|
11/30 - 12/1
| [elc] ELC Mini-Workshop (B01 + C03) |
| 場所:
11/30(土)東北大学情報科学研究科棟 2F 大講義室
12/1(日)パームシティ131ビル 5F Room 5B
仙台市青葉区一番町3丁目1-16
プログラム:
Click to Continue ...11/30(土)16:45~
【チュートリアル】正代 隆義(九大)
グラフパターン言語の正例からの帰納推論と最適化問題
(懇親会)
12/1(日)9:30~
【チュートリアル】来嶋 秀治(九大)
置換多面体上の乱択丸め
【問題提起】
・畑埜 晃平(九大)
オフライン-オンライン変換について
・内澤 啓(山形大)
整数計画問題とCircuit-SAT
(昼食)
13:30~15:30
【問題提起】
・神山 直之(九大)
On the complexity of trial and error (STOC13) の紹介と問題発掘
・篠原 歩(東北大)
連の下界とオートマトンの学習問題(仮)
|
12/5 - 10
| NIPS 2013 |
12/6
| [elc] ELC Mini-Workshop on Sublinear-Time Algorithms (A02) |
| Place : Room 2208 (22th floor), The National Institute of Informatics (国立情報学研究所). |
| 末尾に懇親会情報があります。
Program:
*** Note ***: Eric Blais (Carnegie Mellon University)'s talk was canceled
due to his emergency surgery. (It's not severe. He is recovering favorably.)
10:55-11:00: Opening: Hiro Ito (University of Electro-Communications)
11:00--11:30: Francois Le Gall (University of Tokyo)
- Sublinear Quantum Algorithms for Graph-theoretic Properties
Click to Continue ...(Lunch Break: 90 min.)
13:00--14:00: Invited: Comandur Seshadhri (Princeton University)
- Monotonicity and Lipschitz testing on hypergrids: alternating paths
to the rescue
14:00--14:30: Mitsuru Kusumoto (Kyoto University & ERATO)
- Testing Forest-Isomorphism in the Adjacency List Model
(Break: 20 min.)
14:50--15:20: Skip Jordan (Hokkaido University & ERATO)
- Property Testing, Logic and Complexity
15:20--15:50: Takahiro Ueda (Kyoto University)
- Sublinear-Time Cake-Cutting Algorithms
(Break: 20 min.)
16:10--16:40: Yuichi Yoshida (NII & Preferred Infrastructure)
- A Characterization of Locally Testable Affine-Invariant Properties
via Decomposition Theorems
16:40--17:10: Hiro Ito (University of Electro-Communications)
- A Paradigm Shift Toward The Big-Data Era
Abstracts:
- Eric Blais (Carnegie Mellon University) (Canceled)
Title: The communication complexity method in property testing
Abstract:
Since it’s introduction by Yao in 1979, the communication complexity method has been
spectacularly successful in establishing lower bounds in a wide variety of settings
throughout computer science. In this talk, we will survey recent work that shows how
this method can also be used to prove lower bounds on the complexity of property
testing algorithms. During the talk, we will explore some of the lower bounds that can
be obtained with this method, we will examine connections with the Fourier analysis of
functions, and we will discuss some of the fundamental open problems suggested by the
use of this method.
- Francois Le Gall (University of Tokyo)
Title: Sublinear Quantum Algorithms for Graph-theoretic Properties
Abstract:
Sublinear-time algorithms are omnipresent in the field of quantum algorithms. A typical
example is the well-known quantum search algorithm (discovered by Grover in 1996), which
finds a marked element among n elements in O(n^{1/2}) time, while any classical algorithm
for this task requires linear time. Recently, several new algorithmic techniques have
been developed and used to construct quantum algorithms for testing many graph-theoretic
properties, such as deciding if a given graph contains a triangle of not. In this talk
I will first survey these recent developments, and then present new quantum algorithms
for testing several properties over hypergraphs.
- Comandur Seshadhri (Princeton University)
Title: Monotonicity and Lipschitz testing on hypergrids: alternating paths to the rescue
Abstract:
Monotonicity testing is a classic problem in property testing. The domain [n]^d
is equipped with the natural coordinate-wise partial order. A function f:[n]^d -> R is
called monotone, if for all x < y, f(x) \leq f(y). A function is f is said to be \eps-far
from monotone, if it needs to be changed at at least \eps n^d values to make it monotone.
The problem of monotonicity testing is to decide (in sublinear queries to f) whether f is
monotone or \eps-far from monotone. We prove there exists a tester making O(\eps^{-1} d log n)
queries. This matches all known lower bounds, and completely resolves the problem of
monotonicity testing on hypergrids. (The complexity even for the case of the boolean
hypercube {0,1}^d was open until this result.)
The main technique is a new framework of alternating paths that is used to relate distant
violations of monotonicity to local violations. This framework allows us to get optimal
algorithms for this problem. It also gives optimal results for Lipschitz testing,
a property with known connections to data privacy. Indeed, the alternating paths framework
gets testers for a large class of "derivative-bounded properties" on hypergrids.
Joint work with Deeparnab Chakrabarty
- Mitsuru Kusumoto (Kyoto University & ERATO)
Title: Testing Forest-Isomorphism in the Adjacency List Model
Abstract:
We consider the problem of testing whether two input forests are isomorphic
or far from being so. An algorithm is called an $\epsilon$-tester for forest-isomorphism
if given query access to two forests $G$ and $H$ in the adjacency list model, with high
probability, accepts if $G$ and $H$ are isomorphic and rejects if we must modify at least
$\epsilon n$ edges to make $G$ isomorphic to $H$. We show an $\epsilon$-tester for
forest-isomorphism with query complexity $\poly \log n$ and an almost matching lower bound
of $\Omega(\sqrt{\frac{\log n}{\log \log n}})$. With the aid of the tester, we also show
that every graph property is testable in the adjacency list model with $\poly \log n$
queries if the input graph is a forest.
- Skip Jordan (Hokkaido University & ERATO)
Title: Property Testing, Logic and Complexity
Abstract:
Given a computationally intractable problem, it is natural to consider
approximations and hope to gain efficiency. In property testing, we consider what can
be achieved given only a sublinear or constant sample of the input.
Here, I will introduce various open questions concerning combinations of
property testing and logic. Most are inspired by complexity theory,
and especially by descriptive complexity.
- Takahiro Ueda (Kyoto University)
Title: Sublinear-Time Cake-Cutting Algorithms
Abstract:
In this research, we show sub-linear time algorithms for the cake-cutting problem.
The cake-cutting problem is a problem of dividing a cake into pieces and handing them down
to players who have different measures of the value of the cake, and then they must be
``satisfied.'' Though the definition of ``satisfaction'' are various, e.g. simple-fair,
envy-free and so on, we talk about simple-fair division such that each player has 1/n values
in his/her piece of cake in his/her own value function. It is known that the query complexity
for the cake-cutting problem is \Theta(n logn) for both deterministic and random algorithms.
But no o(n)-time algorithm have been knows for dividing a piece only for the first player.
We construct a framework to solve the cake-cutting problem in sublinear-time, and show
algorithms in this framework. In particular, algorithms with {\eps n}-victims for
dividing a cake for r=o(n) players in O(r/\eps) times. And then the first r players who
are assigned a piece of cake must be satisfied. Furthermore, we extend this algorithm to
general f(n)-victims.
- Yuichi Yoshida (NII & Preferred Infrastructure)
Title: A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems
Abstract:
Let P be a property of functions Fnp → {0, 1} for a fixed prime p. An algorithm is called
a tester for P if, given a query access to the input function f, with high probability,
it accepts when f satisfies P and rejects when f is “far” from satisfying P. In this paper,
we give a characterization of affine-invariant properties that are testable with a constant
number of queries. The characterization is stated in terms of decomposition theorems, which
roughly claim that any function can be decomposed into a structured part that is a function
of a constant number of polynomials, and a pseudo-random part whose Gowers norm is small.
We first show an algorithm that tests whether the structured part of the input function has
a specific form. We then show that an affine-invariant property is testable with a constant
number of queries if and only if it can be reduced to the problem of testing whether the
structured part of the input function is close to one of a constant number of candidates.
- Hiro Ito (University of Electro-Communications)
Title: A Paradigm Shift Toward The Big-Data Era
Abstract:
In this century we are facing the big-data era. For treating big data, traditional
common sense sometimes does not work. Though we thought that polynomial-time algorithms
are fast algorithms in the past century, it is not always true for big data, e.g.,
an O(n^2)-time algorithm may be no longer fast! For such problems, sublinear-time,
especially constant-time algorithms should take important roles.
Yes, we need a new paradigm! In this talk, we try to consider what should be this
paradigm and how does it work.
懇親会:
日時: 2014年 12月 6日 (金) 17:45 〜
場所: しゃぶしゃぶ温野菜 神保町白山通り店
懇親会参加費: 4,000円 (予定) (会場で集めます)
懇親会参加申込(〆切:12月 3日 (火) 19:00)は下記URL:
https://www.al.ics.saitama-u.ac.jp/elc/reg/2013_1206_a02/
(人数確定の必要上、懇親会は事前申し込みが必要です。)
|
12/10 - 14
| FSTTCS 2013 |
12/12 - 14
| COCOA'13 (The 7th Annual International Conference on Combinatorial Optimization and Applications) |
| 投稿〆切 : 2013/8/2 |
| Place : 成都(中国) |
12/16 - 18
| ISAAC 2013 |
| 投稿〆切 : 2013/6/15 |
| Place : Hong Kong |
12/17
| [elc] ELC Seminar (Dr. Siu-On Chan) |
| Place : CELC Seminar Room (4F) |
| Date: 2003.12.17, 13:00-14:00
Place: CELC Seminar Room, Tokyo Tech. Tamachi 4F
http://www.al.ics.saitama-u.ac.jp/elc/en/celc/
Title: Approximation Resistance from Pairwise Independent Subgroups
by: Siu-On Chan (MSR New England)
Click to Continue ...Abstract:
We show optimal (up to a constant factor) NP-hardness for maximum
constraint satisfaction problem with k variables per constraint
(Max-k-CSP), whenever k is larger than the domain size. This follows
from our main result concerning CSPs given by a predicate: a CSP is
approximationresistant if its predicate contains a subgroup that is
balanced pairwise independent. Our main result is analogous to Austrin
and Mossel’s, bypassing their Unique-Games Conjecture assumption
whenever the predicate is an abelian subgroup.
Our main ingredient is a new gap-amplification technique inspired by
XOR-lemmas. Using this technique, we also improve the NP-hardness of
approximating Independent-Set on bounded-degree graphs, Almost-Coloring,
Two-Prover-One-Round-Game, and various other problems.
|
12/20
| [elc] 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 沖縄産業支援センター |
12/20 - 21
| 電子情報通信学会コンピュテーション研究会 |
| Place : 沖縄 |
12/23 - 24
| [elc] FOCS 報告会 |
| Place : 東京大学本郷キャンパス 工学部6号館3階セミナー室AD |
| キャンパス マップ
http://www.u-tokyo.ac.jp/campusmap/cam01_04_07_j.html
12月23日の夕方に,懇親会を行います.
参加申込は,下記のページからお願いします.
https://www.al.ics.saitama-u.ac.jp/elc/reg/2013_1223_focs_report/
Click to Continue ...
プログラム
12月23日
12:20-13:00 フリーディスカッション
13:00-14:10 山内 由紀子 (九州大学)
担当論文:Tight Bounds for Set Disjointness in the Message Passing Model
M. Braverman, F. Ellen, R. Oshman, T. Pitassi and V. Vaikuntanathan
14:30-15:40 森 立平 (東京工業大学)
担当論文: Approximate Constraint Satisfaction Requires Large LP Relaxations
S.O. Chan, J.R. Lee, P. Raghavendra and D. Steurer
16:00-17:10 斎藤 惇 (群馬大学)
担当論文:A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
R. Impagliazzo, R. Paturi, and S. Schneider
12月24日
10:30-11:40 長尾 篤樹 (京都大学)
担当論文: Average Case Lower Bounds for Monotone Switching Networks
Y. Filmus, T. Pitassi, R. Robere and S.A. Cook
11:40-13:00 フリーディスカッション
13:00-14:10 河瀬 康志 (東京大学)
担当論文: The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant
V. Bilò, M. Flammini and L. Moscardelli
14:30-15:40 山口 裕生 (東京工業大学)
担当論文: Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
A. Marcus, D.A. Spielman and N. Srivastava
16:00-17:10 中川 航太郎 (東京工業大学)
担当論文:Towards a Better Approximation for Sparsest Cut?
S. Arora, R. Ge and A.K. Sinop
#なお,担当論文は変更する可能性があります.
|