2015年 | |
1/4 - 6
| SODA 2015 |
| Place : San Diego, California, USA |
1/6
| [elc] ELC Seminar (Kazuhisa Makino) |
| Place : CELC seminar room (CIC 4F) |
| Date: Jan. 6 (Tue), 2015
Time: 10:00 - 12:00
Place: CELC 404
Speaker: Kazuhisa Makino (Univ. of Kyoto)
Title: Posimodular function optimization
Abstract:
Click to Continue ...Given a posimodular function f: 2^V \to \mathbb{R} on a finite set V, we
consider the problem of finding a nonempty subset X of V that minimizes
f(X). Posimodular functions often arise in combinatorial optimization such
as undirected cut functions. In this paper, we show that any algorithm for
the problem requires \Omega(2^{\frac{n}{7.54}}) oracle calls to f, where
n=|V|. It contrasts to the fact that the submodular function minimization,
which is another generalization of cut functions, is polynomially solvable.
When the range of a given posimodular function is restricted to be
D=\{0,1,...,d\} for some nonnegative integer d, we show that
\Omega(2^{\frac{d}{15.08}}) oracle calls are necessary, while we propose an
O(n^dT_f+n^{2d+1})-time algorithm for the problem. Here, T_f denotes the
time needed to evaluate the function value f(X) for a given X \subseteq V.
We also consider the problem of maximizing a given posimodular function. We
show that \Omega(2^{n-1}) oracle calls are necessary for solving the
problem, and that the problem has time complexity \Theta(n^{d-1}T_f) when
D=\{0,1,..., d\} is the range of f for some constant d.
This is a joint work with Toshimasa Ishii.
|
1/11 - 13
| ITCS 2015 |
| 投稿〆切 : 2014/8/8 |
| Place : Weizmann Institute of Science, Israel |
1/13 - 5/15
| Information Theory |
| Place : Simons Institute, Berkeley |
1/23 - 24
| JST ERATO 河原林/湊 合同ワークショップ |
| Place : 日本科学未来館 7F 未来館ホール |
1/28 - 30
| 冬のLAシンポジウム |
| Place : 京都大学 数理解析研究所 |
2/13 - 14
| [elc] 計算理論とビッグデータ |
| Place : 会場:東北大学青葉山キャンパス情報科学研究科棟2階大講義室,http://www.is.tohoku.ac.jp/access/index.html 〒980-8579 宮城県仙台市青葉区荒巻字青葉6番3号09 |
| 「計算理論とビッグデータ」ワークショップ
(文部科学省新学術領域研究「計算限界解明」
+JST CREST「アルゴリズム基盤」+JST CREST「データ粒子化」)
※以下のURLで本ワークショップへの参加登録を行っています。
https://www.al.ics.saitama-u.ac.jp/elc/reg/2015_elc_bigdata/
登録は必須ではありませんが、会場準備(人数把握)のために、事前の登録にご協力お願いいたします。懇親会や二日目昼食の申込みも同時に可能です。
Click to Continue ...
2月13日(金)
12:55--13:00 3プロジェクト合同ワークショップ開催挨拶
13:00--13:30 渡辺治(東工大)「新学術領域「計算限界解明」の紹介」
13:30--14:30 加藤直樹(京都大)「ビッグデータ時代に向けた革新的アルゴリズム基盤」
14:30--14:45 【休憩】
14:45--15:45 宇野毅明(NII)「新世代のデータマイニング技術における計算技術的な課題」
15:45--16:00 【休憩】
16:00--16:30 吉田悠一(NII)「劣モジュラ関数最大化:理論と応用」
16:30--17:00 中野眞一(群馬大)「On gatherings」
18:00-- 【懇親会】 https://www.al.ics.saitama-u.ac.jp/elc/reg/2015_elc_bigdata/
2月14日(土)
10:00--10:30 山本章博(京都大)「データ粒子化と意味論構造」
10:30--11:00 渡辺治(東工大)「省領域計算の可能性」
11:00--11:15 【休憩】
11:15--11:45 田中和之(東北大)「劣線形モデリングにむけての情報統計力学的アプローチ」
11:45--12:15 羽室行信(関西学院大)「グラフ研磨手法のテキスト解析への応用」
12:15--13:45 【昼食休憩】 https://www.al.ics.saitama-u.ac.jp/elc/reg/2015_elc_bigdata/
13:45--16:00 ポスターセッション
- 伊藤健洋(東北大)「Algorithms for Reconfiguration Problems」
- 桂敬史(東北大)「マルチトラック文字列の順列パターン照合の効率化」
- 瀧澤重志(大阪市立大)「避難計画に対する効率的アルゴリズムの開発(仮題)」
- 小林拓人・片岡駿(東北大)「ノードデータを考慮したネットワークのコミュニティ構造抽出」
- 高畠嘉将(九工大)「大規模ストリームデータ圧縮処理」
- 中原孝信(専修大)「データ研磨技術のビジネス応用」
- 大滝啓介(京都大)「Pattern Structure Analysis of Episodes for Sequence Analysis
via Extracting Pattern Concepts」
|
2/24
| [elc] ELC Mini-Wokshop (C01) |
| Place : CLEC seminar room |
| ELC Mini-Workshop on Boolean Function Complexity (C01)
Date: Feb. 24th (Tue)
Time: 15:00 - 17:00
This is an informal seminar for discussing various aspects of
the complexity of Boolean functions, which we hope to be a
Click to Continue ...good starting point of our new collaboration on this topic.
For starting our disucssion, we will have the following two
talks.
Title : Strong ETH holds for Resolution with Bounded Read
Speaker: Navid Talebanfard (ELC C01 PD)
Abstract: Strong Exponential Time Hypothesis (SETH) states that
k-SAT requires time complexity 2^{(1 - c_k)n} for some c_k -> 0
as k -> infinity. Of course this is stronger that NP != P and
hence verifying this hypothesis remains way beyond our reach at
the moment. However we can ask whether currently known algorithms
or classes of algorithms are consistent with SETH. We construct
unsatisfiable k-CNF formulas which require resolution refutations
of size at least 2^{(1 - c_k)n} where each variable in the proof
is resolved at most a bounded number of times. Prior
to this work such a lower bound was known only for tree-like and
regular resolution.
This is a joint work with Ilario Bonacina.
Title: On restricting no-Junta Boolean function and
It's application on the degree lower bound
Speaker: MingChuan Yang (National Taiwan ChaoTong Univ.)
Abstract: Let f be a Boolean function depending on n variables. We
prove that at least one of its subfunction derived from a restriction
depends on the remaining n-1 variables, for some variable. This
existent result suggests a possible way to deal with general Boolean
functions via its subfunctions. We can apply this idea to obtain a
degree lower bound of representing polynomials over finite rings.
(Host: Osamu Watanabe watanabe@is.titech.ac.jp)
(Please let me know if anyone wants to join it via polycom.)
|
2/26
| 日英Big Data Workshop ウイリアム王子来日記念 「Innovation is GREAT」 |
| Place : 国立情報学研究所 |
2/26 - 28
| WALCOM 2015 |
| 投稿〆切 : 2014/9/18 |
| Place : Dhaka, Bangladesh |
2/28 - 3/1
| [elc] ELC Workshop on Parameterized Algorithms |
| Place : University of Electro-Communications |
| ELC Workshop on Parameterized Algorithms
Dates: February 28-March 1, 2015
Place: The University of Electro-Communications
Building E-3, 3rd Floor
(Building No. 27 in http://www.uec.ac.jp/eng/about/access/)
Click to Continue ... 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585
Program:
Saturday February 28th
10:00 – 10:15 | Welcoming participants (opening address)
10:15 – 11:15 | Michał Pilipczuk (New results on computing tree decompositions of graphs)
11:15 – 13:00 | Lunch
13:00 – 14:00 | Valia Mitsou (The computational complexity of two card games with theoretical applications)
14:00 – 14:15 | Coffee break
14:15 – 15:15 | Bingkai Lin (The parameterized complexity of k-Biclique)
15:15 – 15:30 | Coffee break
15:30 – 16:15 | Yushi Uno (Fixed-parameter algorithms for vector dominations)
16:15 – 16:30 | Coffee break
16:30 – 17:30 | Discussion and open problems
18:30 - | Reception
Sunday March 1st
09:30 – 10:30 | Saket Saurabh (Graph Modification Problems: A Modern Perspective)
10:30 – 10:45 | Coffee break
10:45 – 11:45 | Michael Lampis (Parameterized Approximation Schemes Using Graph Widths)
11:45 – 13:00 | Lunch
13:00 – 14:00 | Yixin Cao (Linear Recognition of Almost Interval Graphs)
14:00 – 14:15 | Coffee break
14:15 – 15:15 | Rémi Watrigant (Cardinality constraint optimisation problems)
15:15 – 15:30 | Coffee break
15:30 – 17:00 | Discussion and open problems
Organizers:
Rémy Belmonte
Naoki Katoh
Yoshio Okamoto
|
3/2
| 組合せゲーム・パズル研究集会 |
| Place : 電気通信大学 |
3/4
| [elc] ELC Seminar (Dr. XiaoHui Bei) |
| Place : CELC seminar room |
| ELC Seminar (C01)
Date: March 4th
Time: 15:00-16:00
Place: CELC Seminar room
Title: Balancing Efficiency and Fairness in Resource Allocation
Click to Continue ...Speaker: XiaoHui Bei (Max Plank Institute)
Abstract:
In this work, we study the resource allocation problem from the lens
of welfare economics. We focus on two critical criteria: efficiency
and fairness, and address the problem of allocating resources that
account for the natural tension between efficiency and fairness.
We consider a broad class of resource allocation problems, and
quantitatively analyze the tradeoffs between efficiency and fairness
by employing the approach of approximation. We show nearly optimal
bicriteria approximation Pareto curves, which give an explicit
answer to the question that if there exists an allocation that
achieves (almost) any targeted efficiency and fairness. Our results
improve on the approximation curves provided by Bertsimas et al.
and yield nearly complete characterization on the tradeoff inherent
in efficiency and fairness.
This is a joint work with Ning Chen and Hongyang Zhang.
(Host: Osamu Watanabe and Navid Tablefard)
|
3/4 - 6
| 計算錯覚学国際シンポジウム (International Symposium on Psychological vs Mathematical Approaches to Optical Illusion) |
| Place : 明治大学中野キャンパス |
3/4 - 7
| STACS 2015 |
| 投稿〆切 : 2014/9/21 |
| Place : Munich, Germany |
3/10 - 13
| 電子情報通信学会 総合大会 |
| 投稿〆切 : 2015/1/7 |
| Place : 立命館大学 草津キャンパス |
3/12
| [elc] サイエンスカフェ@東工大(田町) Science Cafe at TITECH on Tamachi Campus |
| Place : 東京工業大学 田町キャンパス 1階 国際会議室 ( TITECH Tamachi Campus 1F) |
| サイエンスカフェ「P≠NP予想を語る」
21世紀の数学の7大未解決問題と言われている「P≠NP予想」は,計算とは何か?
計算で何がどこまでできるのか?など,計算とその限界についての基本的な問いです.
このP≠NP予想とは何か,計算の面白さと魅力,そして計算限界とは何か?について,
最先端の研究をカフェでの雑談のようなリラックスした雰囲気の中でご紹介します!
Click to Continue ...内容(予定):
・P≠NP予想とは何か?の簡単なお話し
・小さなグループにわかれて,P≠NP予想や計算機科学に関連するパズルやゲームなどを楽しむ
※優れたホストを多数ご用意してお待ちしています ;‐)
会場:東京工業大学・田町キャンパス キャンパスイノベーションセンター 1F国際会議室(JR 田町駅徒歩1 分)
地図: http://www.cictokyo.jp/access.html
日時:3 月12 日(木)18:30 ~ (18:00 受付開始)
対象:高校生以上
定員:50 名(※申込順/参加無料)
申込:電子メールにて計算限界解明事務局まで申し込みください
E-mail:elc-cafe@is.titech.ac.jp
申込み時には,氏名,年齢,性別,連絡先( E-mail, 電話番号など),職業(学生は,学校名と学年) を明記してください.
※このサイエンスカフェは科研費新学術領域「計算限界解明」のアウトリーチ活動の1つとして行います.
※計算限界解明については, http://www.al.ics.saitama-u.ac.jp/elc/ をご覧ください.
Date: March 12 (THU), 2015
Time: 18:30 -
Place: TITECH TAMACHI CYAMPUS 1F, http://www.cictokyo.jp/access.html
Registration: Please send an email to elc-cafe@is.titech.ac.jp
with your name, age, email address, affiliation.
It is said that P≠NP is one of the seven major unresolved problem of 21st century.
Researchers have proposed various techniques for investigating the limits of computation,
many of which have been sharpened in depth during the last two decades.
What’s P≠NP? We are going to introduce you the charm of calculation
and also show you our most resent research in a relaxing atmosphere.
So let join us to know more about P≠NP !
|
3/13
| ワークショップ「計算機科学・OR・建築のこれから」 |
| Place : メルパルク京都 5階 京極 |
| 加藤先生退職記念のワークショップです。
プログラム
12:50 -- 13:00 開会の挨拶
13:00 -- 13:45 瀧澤 重志 先生(大阪市大)の講演
14:00 -- 14:45 藤澤 克樹 先生(九州大)の講演
15:00 -- 15:45 徳山 豪 先生(東北大)の講演
Click to Continue ...16:20 -- 17:20 加藤 直樹 先生の講演
終了後パーティあり
|
3/15 - 18
| EuroCG 2015 |
| 投稿〆切 : 2015/1/7 |
| Place : Ljubljana, Slovenia |
3/17 - 19
| 情報処理学会 第77回全国大会 |
| 投稿〆切 : 2014/11/21 |
| Place : 京都大学 |
3/19 - 20
| Workshop on Secure Quantum Computing |
| Place : Tokyo Univ. (Room 007 in the 7th Building of Science) |
| Invited speakers:
Joseph Fitzsimons (Singapore University of Technology and Design)
Si-Hui Tan (Singapore University of Technology and Design)
Yingkai Ouyang (Singapore University of Technology and Design)
Tommaso Demarie (Singapore University of Technology and Design)
Michal Hajdusek (Singapore University of Technology and Design)
Joshua Kettlewell (Singapore University of Technology and Design)
Click to Continue ...Zhao Liming (Singapore University of Technology and Design)
Atul Mantri (Singapore University of Technology and Design)
Zhao Zhikuan (Singapore University of Technology and Design)
Kentaro Honda (University of Tokyo)
Takeshi Koshiba (Saitama University, Japan)
Stacey Jeffery (Caltech)
Program:
19th
9:40-10:20 Joseph Fitzsimons
Blind quantum computing
10:20-11:00 Si-Hui Tan
Practical Homomorphic Encryption with Coherent States
11:00-11:40 Kentaro Honda
Blind quantum computation with public verifiability
13:40-14:20 Yingkai Ouyang
A quantum approach to fully homomorphic encryption: Information theoretic security
14:20-15:00 Takeshi Koshiba
Quantum Bloom Filter
15:00-15:40 Tommaso Demarie
Anonymous broadcasting with a continuous-variable topological quantum code
20th
9:40-10:20 Michal Hajdusek
Device-Independent Verifiable Blind Quantum Computation
10:20-11:00 Joshua Kettlewell
A quantum approach to fully homomorphic encryption: Universality.
11:00-11:40 Stacey Jeffery
Quantum homomorphic encryption for circuits of low T-gate complexity
13:40-14:20 Zhao Liming
Graph state data structures
14:20-15:00 Atul Mantri
Optimal Blind Quantum Computation
15:00-15:40 Zhao Zhikuan
A Review Of Position-based Quantum Cryptography
Registration:
This workshop is free of charge and open to anyone.
No registration is needed.
Venue:
The workshop will be held in Room 007 in the 7th Building of Science
of the University of Tokyo (Hongo campus).
Organizer:
Tomoyuki Morimae (Gunma University)
Masami Hagiya (University of Tokyo)
|
3/24 - 25
| [elc] ELC Workshop on Exponential Lower Bounds for Pivoting Algorithms |
| Place : CELC, Tokyo |
3/26 - 28
| OR学会春季研究発表会・シンポジウム |
| 投稿〆切 : 2015/1/7 |
| Place : 東京理科大学 神楽坂キャンパス |
| 26日:シンポジウム
27、28日:研究発表会
|
3/30
| [elc] ELC勉強会(C02): 量子計算モデルと計算量クラスに関する勉強会 |
| Place : CELC |
| 量子計算モデルと計算量クラスに関する勉強会
日時:3月30日(月)10:40-
場所:CELC(http://www.al.ics.saitama-u.ac.jp/elc/celc/) セミナー室
スケジュール:
Click to Continue ...時間:10:40-11:40
話題提供者:森前智行(群馬大)
話題:one clean qubit 量子計算モデルの古典シミレート不可能性
参考文献:
On the hardness of classically simulating the one clean qubit model
Tomoyuki Morimae, Keisuke Fujii, Joseph F. Fitzsimons
Physical Review Letters 112, article number 130502 (2014)
時間:12:45-13:45
話題提供者:藤井啓祐(京都大)
話題:Instantaneous quantum polynomial time modelとイジング分配関数
参考文献:
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Michael J. Bremner, Richard Jozsa, Dan J. Shepherd
Proceedings of Royal Society A 467: 459–472 (2011)
Quantum Commuting Circuits and Complexity of Ising Partition Functions
Keisuke Fujii, Tomoyuki Morimae
arXiv:1311.2128
時間:14:00-15:00
話題提供者:玉手修平(NII)
話題:相互作用なしのボソン粒子を用いた量子計算機モデルの古典シミレート不可能性
参考文献:
The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov,
Proc. 43th ACM Symposium on Theory of Computing (STOC11), pp. 333-342 (2011);
Journal version appeared in Theory of Computing 9: 143-252 (2013)
時間:15:15-
フリーディスカッション
問合せ先:西村治道(名古屋大,C02班)
|
4/13 - 15
| Green Computing (ITNG2015 Track) |
| 投稿〆切 : 2014/10/17 |
| Place : Las Vegas, Nevada, USA |
| ITNG 2015: 12th International Conference on Information Technology : New Generations
http://www.itng.info
|
4/16 - 17
| MATCH-UP 2015 (3rd International Workshop on Matching Under Preferences) |
| 投稿〆切 : 2014/12/1 |
| Place : University of Glasgow, グラスゴー, 英国 |
4/22
| [elc] ELC Seminar (Prof. M. Golin) |
| Date: April 22nd
Time: 16:00 - 17:00
Optimal Binary Comparison Search Trees
Professor Mordecai Golin (CSE Dept, Hong Kong UST)
Historically, constructing optimal (minimum average search time)
Click to Continue ...binary search trees (BSTs) is one of the canonical examples of
dynamic programming. In 1971, Knuth described how to solve this
problem in O(n^2) time, with input specifying the probability of the
different successful and unsuccessful searches. While the trees
constructed were binary, the comparisons used were ternary.
Successful searches terminated at internal nodes and unsuccessful
searches at leaves.
By contrast, in binary comparison trees (BCSTs), internal nodes
perform binary comparisons; the search branches left or right
depending upon the comparison outcome and all searches terminating at
leaves. Polynomial algorithms exist for solving the optimal BCST
problem restricted to successful searches. Hu and Tucker gave an O(n
log n) algorithm when all comparisons are the inequality “<”;
Anderson et. al. developed an O(n^4) algorithm when both “<” and “=”
comparisons are allowed.
In this talk we present the first polynomial time algorithms for
solving the optimal BCST problem when unsuccessful searches are
included in the input and any set of comparisons are permitted. Our
running times depend upon the comparisons allowed. If equality is
not allowed, our algorithm runs in O(n log n) time; if equality is
allowed, O(n^4). We also demonstrate O(n) time algorithms that yield
almost optimal binary comparison trees, with tree cost within
constant additive factor of optimal.
This is joint work with Marek Chrobak, Ian Munro and Neal Young.
(Host: Osamu Watanabe)
|
5/9 - 10
| AAAC 2015 (The 8th Annual Meeting of Asian Association for Algorithms and Computation) |
| 投稿〆切 : 2015/2/28 |
| Place : 宮島(広島) |
| 投稿は1ページのアブストラクト
|
5/18 - 8/14
| Cryptography |
| Place : Simons Institute, Berkeley |
5/20 - 22
| TQC 2015 |
| 投稿〆切 : 2015/2/6 |
5/21
| [elc] ELC Seminar (Prof. Toran and Prof. Radhakrishnan) |
| Place : Center for ELC, Seminar room |
| Date: May 21st
Time: 15:00 - 17:30
Center for ELC, Seminar room, Tokyo Tech. CIC 4F
* After the seminar, we will go out for dinner to some place.
Please let me know if you want to join us.
Click to Continue ...
===============
Speaker: Jacobo Toran (Univ. of Ulm)
Title: Graph Isomorphism is not AC_0 reducible to Group Isomorphism
Abstract:
We give a new upper bound for the Group and Quasigroup Isomorphism
problems when the input structures are given explicitly by
multiplication tables. We show that these problems can be computed by
polynomial size nondeterministic circuits of unbounded fan-in with O(log
log n) depth and O(log2 n) nondeterministic bits, where n is the number
of group elements. This improves the previously existing upper bound for
the problems. In the previous upper bound the circuits have bounded fan-
in but depth O(log2 n) and also O(log2 n) nondeterministic bits. We then
prove that the kind of circuits from our upper bound cannot compute the
Parity function. Since Parity is AC0 reducible to Graph Isomorphism,
this implies that Graph Isomorphism is strictly harder than Group or
Quasigroup Isomorphism under the ordering defined by AC0 reductions.
===============
Speaker: Jaikumar Radhakrishnan (Tata Institute of Fundamental Research)
Title: Set membership with two bit probes
Abstract:
We will consider the bit-probe complexity of the set membership
problem, where a set S of size at most n from a universe of size
m is to be represented as a short bit vector in order to answer
membership queries of the form ``Is x in S?'' by adaptively
probing the bit vector at t places. Let s(m,n,t) be the minimum
number of bits of storage needed for such a scheme. Alon and Feige
showed that for t=2 (two bit probes) such schemes can be obtained
from dense graphs with large girth. In particular, they showed that
for n < log m,
s(m,n,2) = O(m n log((log m) / n) / log m).
We improve their analysis and obtain a better upper bound and
a corresponding lower bound.
Upper bound: There is a constant C>0, such that for all large m,
s(m,n,2) <= C m^{1-1/(4n+1)}.
Lower bound: There is a constant D>0, such that for n>=4 and all
large m, we have s(m,n,2) >= D m^{1-{4}{n}}.
(This is joint work with Mohit Garg.)
END
Host: watanabe(at)is.titech.ac.jp
|
5/29 - 30
| [elc] 平成27年度 第1回領域会議 |
| Place : ELCセンター |
| 領域会議
日時: 5月29,30日
場所: ELCセンター
http://www.al.ics.saitama-u.ac.jp/elc/celc/
東京工業大学 田町キャンパス キャンパス・イノベーションセンター 1階 国際会議室
総括班会議
日時: 5月30日 お昼
Click to Continue ...場所: ELCセンター
http://www.al.ics.saitama-u.ac.jp/elc/celc/
東京工業大学 田町キャンパス キャンパス・イノベーションセンター 404号室
プログラム
5月29日
13:00-13:55 「Deterministic Random Walks on Finite Graphs」来嶋 秀治 (九大)
14:10-15:05 「列挙に対するアルゴリズム設計戦略」宇野 毅明 (NII)
15:15-15:30 事務局連絡
15:30-15:55 (公募班) 「論理式の探索と自動合成による計算限界解析」ジョーダン チャールズハロルド (北大)
15:55-16:20 (公募班) 「パラメータ化計算に関する未解決問題の調査と探求による計算複雑さ解明」宇野 裕之 (大阪府大)
16:35-17:00 (公募班) 「分散並列計算と逐次計算における計算限界導出技法の融合と深化」泉 泰介 (名工大)
17:00-17:25 (公募班) 「非線形整数計画問題の組合せ構造解析による計算限界の解明」塩浦 昭義 (東工大)
18:00- 懇親会: IL FILO(イルフィーロ) 田町駅より徒歩10分
http://tabelog.com/tokyo/A1314/A131403/13013997/
5,000円 貸切、着席のブッフェスタイル(テラス使用可)飲み放題
5月30日
09:15-10:10 「有向木詰め込み問題に対するアルゴリズム」小林 佑輔 (筑波大)
10:25-11:20 「一般の凸錐を用いた拡張定式化と一般確率論における通信複雑度:計算量理論に基づく量子力学の
特徴付けへ向けて」森 立平 (東工大)
11:20-11:45 (公募班) 「符号理論における計算限界の解明」安永 憲司 (金沢大)
11:50-13:00 (総括班会議 4階 404号室)
13:00-13:25 (公募班) 'Time-Space trade-off algorithms for sens' Korman Matias (NII)
13:25-13:50 (公募班) 「解空間のパラメータ化解析による計算困難性と容易性の解明」伊藤 健洋 (東北大)
13:50-14:15 (公募班) 「計算量的仮定に基づくノンユニバーサル量子計算の研究-SBQPと多項式階層」
森前 智行 (群馬大)
14:15-14:25 事務局連絡
アブストラクト
5月29日
来嶋 秀治(九州大学)
タイトル: Deterministic Random Walks on Finite Graphs
アブストラクト:
数え上げ困難な(#P-hard)問題に対して,1980年代後半から,マルコフ連鎖モンテカルロ(MCMC)法を中心とする
様々な乱択近似計算法が開発されてきた一方,決定性の近似アルゴリズムの開発は,近年の重要な挑戦課題になっている.
本発表ではMCMC法の脱乱択化へのアプローチとして,決定性ランダムウォークを紹介する.
ロータールーターモデル(あるいはPropp機械とも呼ばれる)はグラフ上のランダムウォークに似た決定性の過程である.
本発表では,これを一般化し,無理数の推移確率をも模倣する関数ルーターモデルを扱う.
関数ルーターモデルと対応するマルコフ連鎖の「分布」について議論し,マルコフ連鎖の混交時間(mixing time)を使って
単一頂点誤差の上界を与える.
宇野 毅明(NII)
タイトル:「列挙に対するアルゴリズム設計戦略」
アブスト:
列挙アルゴリズムに対する研究は、構造的、あるいは計算的なアプローチに基づくものが多く、数理的アプローチを多く取る
最適化型のアルゴリズムに対する研究と比べると少し味付けが異なるような感覚を覚えることと思う。
この講演では、その中でもまた少し異質な、計算的なアプローチに基づくアルゴリズムの設計戦略について話をしたい。
具体的には、遅延時間を短くする方法を2つ、それと計算量を小さくする方法を1つ、
両方ともアルゴリズムデザイン的なアプローチからのものである。
ジョーダン チャールズハロルド(北大)
タイトル:論理式の探索と自動合成による計算限界解析
アブストラクト:
最近は形式検証や機械学習で論理式の探索と自動合成に関する研究が増えている。
そこで、形式論理と計算量クラスとの関係や、様々な論理の標準系などを用いる。
ここでは、このような応用をunifyする論理式の探索と自動合成について一般的なモデルを紹介する。
特にグラフなどの関係ストラクチャーだけではなく、metafiniteストラクチャーについて考える。
また、応用などで必要なソルバや大規模な計算機への対応について紹介する。
宇野 裕之(大阪府大)
タイトル:「パラメータ化計算に関する未解決問題の調査と探求による計算複雑さ解明」
アブストラクト:
本課題は, パラメータ化計算分野において提示される大小さまざまな未解決問題に着目し,
幅広い調査や整理とともに過去の研究で自身が得た未解決問題との間に有機的な関連を見出し,
それらを解決することにより計算複雑さ解明への突破口を見出すことを目指す.
パラメータ化計算分野の未解決問題として現時点で注目するものとしては,
たとえば平面的有向グラフにおける最長路問題に対する劣指数時間アルゴリズムや,
辺グラフ枝削除問題に対する高速固定パラメータアルゴリズムなどがある.
泉 泰介(名工大)
タイトル:公募班テーマ紹介「分散並列計算と逐次計算における計算限界導出技法の融合と深化」
アブストラクト:
分散計算における計算複雑性の理論は、種々の特徴的な要因により逐次計算における複雑性理論とは異なる形で
発展を遂げてきたが、両者をより高次な視点から考察し、共通の困難性を見いだすような視点からの研究はあまり進んでいない。
このような状況を打破するため、本研究では特に分散並列計算をある種の情報欠落計算の一種と位置づけ、
逐次計算における同種のパラダイムとの間で共通する困難性の本質を括り出すことを目標とする。
本発表ではこのような研究の方向性に対する現状の俯瞰,また研究課題として取り組んでいく具体的なテーマ等を紹介する.
塩浦 昭義(東工大)
タイトル:非線形整数計画問題の組合せ構造解析による計算限界の解明
アブストラクト:
私の研究課題では,整数格子点上で定義される非線形な関数(離散関数)が与えられ,それを最小化する整数ベクトルを求める,
という非線形整数計画問題を扱う.
本研究課題では,離散関数の多面体構造に注目し,効率的に最小化可能な離散関数のクラスを,その凸閉包関数の
多面体構造によって特徴付けることを目的とする.
本発表では,この課題に関連するこれまでの研究成果,および今後の方針について説明する.
5月30日
小林佑輔(筑波大学)
タイトル:有向木詰め込み問題に対するアルゴリズム
アブストラクト:有向木詰め込みに関する Edmonds の定理は,互いに辺を共有しない有向木の最大個数が
ある種の最小カット値と等しいことを示すものであり,この最大最小定理に基づいて有向木詰め込みに関する
様々な最適化問題のアルゴリズムが与えられている.
近年,Edmonds の定理やアルゴリズムの様々な方向への一般化,抽象化が研究されており,組合せ最適化問題に対する
多面体的なアプローチの適用範囲が徐々に拡がっている.
本講演では,有向木詰め込みに関する既存研究について紹介した後,さらなる拡張に関する成果について紹介する.
なお,講演内容の一部は Kristof Berczi氏,Tamas Kiraly氏との共同研究に基づくものである.
森 立平(東工大)
タイトル:一般の凸錐を用いた拡張定式化と一般確率論における通信複雑度: 計算量理論に基づく量子力学の特徴付けへ向けて
アブストラクト:
線形関数を目的関数に持つ0-1最適化問題Pについてその実行可能解それぞれを頂点として持つ多面体上の線形関数最適化が
元の問題Pを厳密に解く一方、その多面体の表現に必要な不等式の数は一般的に変数の数に関して指数関数的に増大する。
近年 P vs NP 問題へのアプローチの一つとしてNP困難である特定の0-1線形関数最適化問題に対応する
多面体の表現の最小サイズを「多面体の複雑度」とみなし、その下界を評価する研究が盛んである。
線形不等式制約を用いた表現における多面体の複雑度について研究が進んでいる一方で一般の凸錐制約を用いた表現を扱う研究は
まだあまりなされていない。
最近 Fiorini達は「ハミルトン閉路多面体を含む大きな多面体のクラス(多面体のクラスにおけるNPの類似とでも言うべきもの)
について常に完全正値錐制約を用いた多項式サイズの表現が存在する」ことを示した。
また多面体の複雑度と一般確率論における通信複雑度の等価性より「量子力学の特徴付けに通信複雑度を用いること」を提案した。
本発表では上記のFiorini達の結果及び一般確率論(量子力学を単純な要請から特徴付けることを目的とする数理物理の分野)
について紹介する。
Fiorini達の提案に関連して「計算量理論を一般確率論への要請として用いること」を考察する。
また発表者による関連研究として古典グラフィカルモデル上のいくつかのテクニック(ホログラフィック変換、
確率伝搬法、ループ計算)の一般確率論への一般化を簡単に紹介する。
安永 憲司 (金沢大)
タイトル:符号理論における計算限界の解明
アブストラクト:
本研究では、誤り訂正符号化技術における計算限界の解明を目的とする。
特に、計算量制限通信路に対して訂正能力の可能性と限界を明らかにすることを目指す。
可能性を探る方向として、暗号理論で発展してきた漏洩耐性暗号技術や難読化技術を用いることで、
これまでに示されていなかった誤り訂正の可能性および明示的構成法を示すことを目指す。
限界を探る方向として、計算量理論や暗号理論で発展してきたブラックボックス分離技法を用いることで、
効率的な訂正の不可能性を示すことを目指す。
コルマン・マティアス(NII)
Title: Time-Space Trade-off algorithms for Sensor Networks
Abstract:
In this talk we will discuss relationship between the running time of the algorithms
and the amount of available space. Clearly, if we give more resources (say, memory)
to any program, we expect it to find the solution faster.
We are interested in how much of a reduction will that bring. Say, will the running time of
the algorithm halve if we double the available space? Or will it only be reduced by a 10%?
We study the exact dependency between these parameters.
伊藤 健洋(東北大学)
タイトル: 解空間のパラメータ化解析による計算困難性と容易性の解明
アブストラクト:
本研究では,解空間の連結性を問う「解の遷移問題」をパラメータ化計算量の観点から研究する.
解の遷移問題とは,基となる問題の実行可能解が2 つ与えられたとき,その間を段階的に遷移できるか判定する問題である.
本研究では,主に解のサイズをパラメータに用いて,遷移問題の解空間をパラメータ化解析する.
PSPACE 完全である遷移問題では,その解空間の直径(遷移にかかる最短ステップ数の最悪値)は超多項式長となるが,
本研究ではパラメータにどのように依存した直径になるのか,より詳細な解析を与える.
森前 智行(群馬大)
タイトル:BQPのちょっと下とちょっと上
アブストラクト:
BQPの「ちょっと下」と「ちょっと上」のクラスを調べることにより、 量子計算量の理解を深めるとともに、
古典計算量の研究にもつなげる、というのが本研究の目的である。
1.BQPのちょっと下:
量子回路で使うキュービットの1つを除き全てが古典ランダムビットにおきかわった
ような量子回路はDQC1回路と呼ばれている。
DQC1回路が解ける問題のクラスは明らかにBQPではなく、それどころかBPPに
入ってしまうように見える。しかしながら、面白いことに、
DQC1回路の出力確率分布が古典計算機で効率的にサンプルできたら
多項式階層が第二レベルで崩壊することが示された[1,2]。多項式階層の崩壊が
ありえないと仮定するならば、このような大きく制限された量子計算モデルでも、
ある意味「古典計算機よりも速い」ということがいえるのである。
2.BQPのちょっと上:
量子論を拡張した理論の計算量を考えることにより、BQPの理解が深まるとともに、
なぜ量子論は今のような理論体系をしているのかと言う物理的な問題に
計算量の立場からアプローチすることもできる。例えば、ポストセレクションやタイムトラベルが可能で
あるような拡張された量子論の計算量はPPやPSPACEになることが
証明されている。しかしながら、PPやPSPACEはBQPのはるか上空にあるため、
もうすこしBQPの「ちょっと上」にある例が欲しいところである。
最近、ポストセレクションにある制限を加えると、PPから、AWPPとWPPの間に
落ちることが示された[3]。AWPPはBQPの現状でベストな上界であるし、BQPはWPPを
含まないと考えられているので、これはBQPの「ちょっと上」の良い例となっている。
[1] TM, Fujii, and Fitzsimons, Physical Review Letters 112, 130502 (2014)
[2] Fujii, Kobayashi, TM, Nishimura, Tamate, and Tani, arXiv:1409.6777
[3] TM and Nishimura, arXiv:1502.000
|
6/2 - 5
| [elc] The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications |
| 投稿〆切 : 2015/2/15 |
| Place : Fukuoka, Japan |
6/14 - 17
| STOC 2015 |
| 投稿〆切 : 2014/11/4 |
| Place : Portland, Oregon |
6/17 - 19
| CCC 2015 |
| 投稿〆切 : 2014/11/26 |
| Place : Portland, Oregon |
6/22 - 25
| SoCG 2015 (31st International Symposium on Computational Geometry) & CG Week 2015 |
| Place : TU Eindhoven, the Netherlands |
6/27
| OR学会関西支部研究講演会「ビッグデータに挑むアルゴリズム理論」 |
| Place : 中央電気倶楽部西館214号室(大阪市北区堂島浜2丁目1番25号) |
| 関西支部研究講演会
テーマ:「ビッグデータに挑むアルゴリズム理論」
日時:2015年6月27日(土)13:30-17:00
場所: 中央電気倶楽部西館214号室(下記のURLをご参照ください)
大阪市北区堂島浜2丁目1番25号(TEL:06-6345-6351(代))
http://www.chuodenki-club.or.jp/
◎大阪駅より徒歩約12分 ◎JR北新地駅より徒歩6分
Click to Continue ...◎地下鉄四ツ橋線西梅田駅より徒歩6分 ◎京阪中之島線渡辺橋駅より徒歩5分
オーガナイザー:
岳五一(甲南大学知能情報学部 教授)
伊藤大雄(電気通信大学大学院情報理工学研究科 教授)
研究講演会の趣旨:
近年、ビッグデータに関する問題が注目されており、それに関する大規模
研究プロジェクトが世界各国で発足しています。我が国でもJSTクレスト
「ビッグデータ時代に向けた革新的アルゴリズム基盤 (Foundations of
Innovative Algorithms for Big Data; ABD14)」が昨年秋に始まりました。
このプロジェクトの中から、基礎理論から実用化まで3名の研究者を講師と
して迎え、最新の研究を紹介していただきます。
---
プログラム:
「開会のあいさつ」: 岳五一(甲南大学知能情報学部 教授・関西支部長)
講演1 「各施設にr人以上集まるような施設配置問題(r-gathering問題)とデータ俯瞰」
中野眞一(群馬大学工学部情報工学科 教授)
講演2 「避難計画問題に対するアルゴリズム支援の可能性」
瀧澤重志(大阪市立大学大学院工学研究科 准教授)
講演3 「複雑ネットワークの定数時間検査」
伊藤大雄(電気通信大学大学院情報理工学研究科 教授)
「閉会のあいさつ」:伊藤大雄
参加費:無料
懇親会情報****
シンポジウム終了後、会場近辺にて懇親会を予定しております
(1) 開催場所:中央電気倶楽部レストラン
(研究講演会会場と同じ建物内です)
(2) 開催時刻:研究会終了後.17:15を予定
(3) 費用:5,000円程度
準備の都合がございますので,ご参加いただける方は,
なるべく早く
幹事の小出まで電子メールにてご連絡お願いいたします.
問合せ先:or-west-office [at] orsj.or.jp 小出 武(甲南大学)
|
7/1
| [elc] ELC Seminar ( Anish Mukherjee & Swagato Sanyal) |
| Place : ELC Center |
| ELC Seminar (C01)
Date: July 1st
Time: 10:00-12:00
Place: CELC Seminar room (Rm.404)
Speaker: P.D. Arnish Mukherjee(Chennai Mathematical Institute)
Title : The Dynamic Complexity of Reachability and Related Problems.
Click to Continue ...
Abstract :
In most real-life databases data changes frequently and
thus makes efficient query answering challenging. Auxiliary data might
help to avoid computing query answers from scratch all the time. One
way to study this incremental maintenance scenario is from the
perspective of dynamic algorithms with the goal of reducing
(re-)computation time. Another option is to investigate it from the
perspective of low-level parallel computational complexity.
As the "lowest" complexity class AC^0 (with a suitable unifomity
condition) and the core of the standard database query language SQL
both coincide with first-order predicate logic, one naturally arrives
at the question which queries can be maintained dynamically with
first-order predicate logic (DynFO). The dynamic complexity framework
independently introduced by Dong, Su and Topor as well as Patnaik and
Immerman models this setting.
Very recently we have shown that the Reachability query can be
maintained in DynFO, confirming a two decade old conjecture of Patnaik
and Immerman. After introducing the dynamic complexity framework and
surveying previous upper and lower bounds for the Reachability query
and related problems briefly, I will present the main ideas of the
proof of this result.
The talk is based on joint work with Samir Datta, Raghav Kulkarni,
Thomas Schwentick and Thomas Zeume.
Speaker: P.D. Swagato Sanyal(Tata Institute of Fundamental Research)
Title: Fourier Dimension and Sparsity
Abstract:
We prove that the Fourier dimension of any Boolean function with
Fourier sparsity $s$ is at most $O\left(\sqrt{s} \log s\right)$.
This bound is tight up to a factor of $O(\log s)$ as the Fourier
dimension and sparsity of the addressing function are quadratically
related. We obtain our result by bounding the non-adaptive parity
decision tree complexity, which is known to be equivalent to the
Fourier dimension. A consequence of our result is that XOR functions
have a one way deterministic communication protocol of communication
complexity $O(\sqrt{r} \log r)$, where $r$ is the rank of its communication matrix.
|
7/2
| [elc] ELC Seminar (Prof. Jaikumar Radhakrishnan) |
| Place : ELC Center |
| ELC Seminar (C01)
Date: July 2nd
Time: 13:30-14:30
Place: CELC Seminar room (Rm.404)
Speaker: Jaikumar Radhakrishnan
(Tata Institute of Fundamental Research)
Click to Continue ...Title: Communication assisted agreement distillation
Abstract: Bogdanov and Mossel (2011) consider the following problem.
"Suppose Alice receives a string of unbiased independent random bits
and Bob receives a noisy copy of the same bits, where each bit is
flipped with probability eps < 1/2. Alice and Bob wish to extract a
common sequence of k random bits."
Bogdanov and Mossel show that for any strategy where Alice and Bob,
with no communication, produce k uniformly distributed bits, the
probability that their outputs agree is at most $2^{- k
eps/(1-eps)}$. Furthermore, they show that the bound is tight by
exhibiting a strategy for Alice and Bob, where their outputs agree
with probability at least $2^{-k eps/(1-eps) - O(log k)}$. Note that
this strategy does better than the natural strategy where Alice and
Bob just use their first k bits (which agree with probability
(1-eps)^k).
We study the relationship between communication and probability of
agreement. Suppose Alice wishes to send Bob a message of delta k bits
to ensure their k-bit outputs agree with probability 2^{-gamma k}. How
big must delta be as a function of gamma? We show the following:
delta(gamma) >= C (1-gamma) - 2 sqrt{C(1-C) gamma}.
where C = 4 eps (1-eps).
This implies that that for delta(gamma) = 0, we have gamma >=
eps/(1-eps), thus recovering the the above mentioned result of
Bogdanov and Mossel for zero communication. Also, if Alice and Bob
wish to agree with constant probability (say 1/2), then Alice must
send about 4 eps (1-eps) k bits; this slightly improves a result of
Canonne, Meka, Sudan and Guruswami (2014), who showed that at least
eps k bits of communication are necessary. We also obtain strategies
that show that this trade-off between communication and probability of
error above is asymptotically tight. This result can also be used to
recovers similar results obtained by Chandar and Tchamkerten (2014) in
the regime when the error probability is assumed to go to zero.
In this talk, we will describe the above trade-off, which is based on
the standard hypercontractivity inequality. We will also outline the
protocols that achieve this trade-off.
(This is part of joint work with Venkat Guruswami.)
|
7/3 - 5
| FAW 2015 (The 9th International Frontiers of Algorithms Workshop) |
| 投稿〆切 : 2015/2/1 |
| Place : 桂林(中国) |
7/4
| [elc] Workshop on Quantum Computational Complexity (Satellite Workshop of ICALP/LICS 2015) |
| Place : Kyoto University |
| ICALP/LICS2015のサテライトワークショップとして開催します.
(本ワークショップのみの参加も可能です.)
参加申込等,詳細は下記ホームページをご参照ください.
http://cs.e.yamagata-u.ac.jp/qcc/
Invited speakers:
Richard Cleve (Waterloo University / IQC)
Click to Continue ... Matthew Coudron (MIT)
Joseph Fitzsimons (Singapore University of Technology and Design)
Keisuke Fujii (Kyoto University)
Troy Lee (CQT Singapore)
Jamie Sikora (CQT Singapore)
Seiichiro Tani (NTT)
|
7/6 - 10
| LICS 2015 |
| 投稿〆切 : 2015/1/19 |
| Place : Kyoto, Japan |
| Title and Short Abstracts Due: January 12, 2015
|
7/6 - 10
| ICALP 2015 |
| Place : Kyoto, Japan |
| Their affiliated workshops will be jointly held on July 4-5 and July 11-12.
|
7/12
| German-Japanese Workshop on Theory and Practice of Real Computation |
| Place : 東京(明治大) |
| Zin Arai
Akitoshi Kawamura
Norbert Th. Mueller
Shin'ichi Oishi
Siegfried M. Rump
Martin Ziegler
Click to Continue ...Program TBA
|
7/12 - 15
| EURO 2015 (27th European Conference on Operational Research) |
| 投稿〆切 : 2015/3/16 |
| Place : Glasgow, UK |
7/12 - 15
| [elc] Twelfth International Conference on Computability and Complexity in Analysis (CCA 2015) |
| 投稿〆切 : 2015/4/10 |
| Place : 明治大学駿河台キャンパス紫紺館4階(東京都千代田区) |
| 初日(日)の「実数計算の理論と実際」ワークショップは参加無料・登録不要です。
|
7/12 - 17
| ISMP 2015 (International Symposium on Mathematical Programming) |
| 投稿〆切 : 2015/3/2 |
| Place : Pittsburgh, PA |
7/13 - 17
| CSR 2015 |
| 投稿〆切 : 2014/12/14 |
| Place : Listvyanka (Lake Baikal), Russia |
7/14 - 16
| 夏のLAシンポジウム |
| 投稿〆切 : 2015/6/15 |
| Place : ゆのくに天祥(石川県加賀市山代温泉) |
7/15
| [elc] ELC Seminar (Prof. Nir Ailon & Prof. Albert Atserias) |
| ELC Seminar (C01)
Date: July 15th
Time: 15:00 - 17:30
Place: CELC Seminar room (Rm.404)
*** NOTICE ***
The order of the talks has been changed. Prof. Asterias first
Click to Continue ...(from 15:00) and then Prof. Ailon next (from 16:15).
Speaker: Professor Nir Ailon(Technion)
Title: Fast Johnson-Lindenstrauss: History, Recent Progress and Open Questions
Abstract:
A Johnson-Lindenstrauss Transform is defined to
be a distribution over k-by-n matrices with the following property:
For any fixed unit vector x in R^n, if A is drawn from the istribution
then the estimator ||Ax|| looks like a Gaussian centered at 1 with
variance roughly 1/k. A Fast Johnson-Lindenstrauss Transform (FJLT)
has the additional property that Ax can be computed in time O(n log n).
Such transformations are related to design of restricted isometry
matrices, useful for universal sparse reconstruction.
FJLT constructions are known for k at most an order of sqrt(n).
For k above sqrt(n), best constructions slightly compromise the
distribution guarantees of ||Ax||. I will survey the history
of results and efforts for constructing FJLTs, including some recent progress.
Based on joint work with Bernard Chazelle, Edo Liberty and Holger Rauhut.
Speaker: Albert Atserias( Universitat Polit�cnica de Catalunya )
Title: On Continuous and Combinatorial Relaxations of Graph Isomorphism
Abstract:
The graph isomorphism problem is one of the most celebrated
computational problems whose complexity status lies somewhere imediate
between P and NP-complete. We revisit two very different-looking
relaxations of the problem. In the first relaxation we require the graphs
to preserve the number of types of local neighborhoods through the well-known
vertex-refinement heuristic and its obvious extension to refinement of k-tuples.
In the second relaxation we write the natural 0-1 linear program for
graph isomorphism and relax it to the continuum through the hierarchy of
continuous relaxations suggested by Sherali and Adams for general 0-1
combinatorial problems. We show that these two very different-looking
relaxations are indeed equivalent. An interesting consequence of this
is that the graph isomorphism problem restricted to planar graphs
can be solved by an explicit polynomial-size linear program.
|
7/15 - 17
| SIROCCO 2015 (22nd International Colloquium on Structural Information and Communication Complexity) |
| 投稿〆切 : 2015/4/30 |
| Place : Montserrat, Spain |
7/25 - 31
| IJCAI-15 |
| 投稿〆切 : 2015/2/12 |
| Place : Buenos Aires, Argentina |
| Abstract submission: Feb 8, 2015
|
7/26
| [elc] GCT Workshop |
| Place : Komaba Campus @ The University of Tokyo |
| Date: JUL 26(SUN), 2015
Time: 12:00~
Place: Room 118 Kenkyuuka-tou, Komaba Campus of The University of Tokyo
http://www.u-tokyo.ac.jp/campusmap/cam02_01_27_j.html
Speaker: Naoya Enomoto of The University of Electro-Communications
Peter Buergisser, Christian Ikenmeyer,
Click to Continue ...Geometric Complexity Theory and Tensor Rank.
arxiv:1011.1350
Speaker: Ryo Yamamoto of Osaka University
Jarod Alper, Tristram Bogart, Mauricio Velasco,
A lower bound for the determinantal complexity of a hypersurface,
arXiv:1505.02205
|
7/30
| [elc] ELC & Kawarabayashi ERATO Seminar (Prof. Johann Makowsky) |
| Place : Center for ELC |
| ELC Seminar (C01 & Kawarabayashi ERATO)
Date: July 30
Time: 16:00 - 17:30
Place: CELC Seminar room (Rm.404)
Speaker: Johann Makowsky (Technion)
Click to Continue ...Title:
Why is the chromatic polynomial a polynomial?
Abstract 2: We give a proof different from Birkhoff's proof of
the fact that counting k-colorings of a graph gives rise to a
polynomial in k, the chromatic polynomial of the graph. We use
this to show that many counting functions on graphs ared
polynomials. We show that every univariate graph polynomial
definable in Second Order Logic is a generalized chromatic
polynomial. (Joint work with B. Zilber and T. Kotek)
|
8/2 - 4
| MOVES (Mathematics Of Various Entertaining Subject) |
| 投稿〆切 : 2015/3/15 |
| Place : MOMATH, NY, USA |
8/3 - 4
| ERATO感謝祭 Season II |
| Place : 一ツ橋講堂 |
8/4 - 6
| COCOON 2015 |
| 投稿〆切 : 2015/2/15 |
| Place : Beijing, China |
8/5 - 7
| WADS 2015 |
| 投稿〆切 : 2015/2/20 |
| Place : University of Victoria, BC, Canada |
8/10 - 12
| CCCG 2015 (27th Canadian Conference on Computational Geometry) |
| 投稿〆切 : 2015/5/1 |
| Place : Queen's University, Kingston, Ontario, CANADA |
| Invited Speakers:
- Jit Bose (Carleton University)
- Bruce Reed (McGill University)
- Jonathan Shewchuk (University of California at Berkeley)
|
8/19 - 12/18
| Fine-Grained Complexity and Algorithm Design |
| Place : Simons Institute, Berkeley |
8/19 - 12/18
| Economics and Computation |
| Place : Simons Institute, Berkeley |
8/21 - 24
| ISORA 2015 (The 12th International Symposium on Operations Research and Its Applications) |
| 投稿〆切 : 2015/7/10 |
| Place : 洛陽 (Luoyang)、中国 |
| 龍門石窟へのExcursionがあります。
*** 投稿締め切りが7月10日に延期されました。 ***
Click to Continue ... |
8/24 - 26
| RANDOM-APPROX 2015 |
| 投稿〆切 : 2015/4/17 |
| Place : Princeton University, USA |
8/24 - 28
| MFCS 2015 |
| 投稿〆切 : 2015/4/22 |
| Place : Milano, Italy |
8/28
| [elc] ELC Seminar (Prof. Peter Bro Miltersen ) |
| Place : ELC Center |
| ELC Seminar (C01)
Date: August 28(FRI), 2015
Time: 16:30 - 17:30
Place: CELC Seminar room (Rm.404)
Speaker: Prof. Peter Bro Miltersen (Aarhus University, Denmark)
Title: A dictatorship theorem for cake cutting
Click to Continue ...Abstract:
We consider discrete protocols for the classical Steinhaus cake cutting problem.
Under mild technical conditions, we show that any deterministic strategy-proof protocol
for two agents in the standard Robertson-Webb query model is dictatorial,
that is, there is a fixed agent to which the protocol allocates the entire cake.
For n > 2 agents, a similar impossibility holds, namely there always exists an agent
that gets the empty piece (i.e. no cake).
In contrast, we exhibit randomized protocols that are truthful in expectation
and compute approximately fair allocations.
Joint work with Simina Branzei, appearing at IJCAI'15
|
9/8
| [elc] ELC Seminar (Prof. Norbert Mller) |
| Place : CELC Seminar room (Rm.404) |
| ELC Seminar (A01)
Date: September 8(tue), 2015
Time: 14:00–
Speaker: Prof. Norbert Müller (Universität Trier)
Title: Real numbers and computers
Click to Continue ...Abstract:
Sometimes, people think that computers could compute correctly.
Unfortunately, this is not true in general: Overflows, underflows,
rounding errors and truncation errors can lead to grossly wrong results,
even if the used algorithm is implemented with care.
This can often be traced down to use of "double precision numbers"
as a replacement for the "real numbers".
In the talk we present how a computer can compute more precisely or
even "exact", just using basic concepts of object-oriented programming.
Additionally, we present some of the basic ideas that are used to
get an efficient implementation of exact real arithmetic.
|
9/9 - 11
| OR学会2015年秋季研究発表会 |
| 投稿〆切 : 2015/6/26 |
| Place : 九州工業大学戸畑キャンパス |
| 9日:シンポジウム
10、11日:研究発表会
|
9/14 - 16
| JCDCG^2 2015 |
| 投稿〆切 : 2015/7/1 |
| Place : 京都大学 時計台 |
| Invited Plenary Speakers:
- John Iacono (NYU, USA)
- Toshihide Ibaraki (KCGI, Japan)
- Janos Pach (EPFL, Switzerland & Renyi Institute, Hungary)
- David Rappaport (Queens Univ., Canada)
- Takeshi Tokuyama (Tohoku Univ., Japan)
Click to Continue ... |
9/14 - 17
| [elc] 2015年度暗号理論秋学校 |
| Place : 河口湖クラブセントビレッヂ |
| 2015年度暗号理論秋学校
日程: 2015年9月14日(月) 13:00 から 17日(木) 12:00 まで
場所: 河口湖クラブセントビレッヂ (http://www.stvillage.com/)
講師: 松田 隆宏 (産総研)、矢内 直人 (阪大)、吉田 真紀 (NICT)、 安永 憲司 (金沢大)、河内 亮周 (徳島大) (敬称略)
内容:
Click to Continue ...
松田 隆宏
テーマ: 公開鍵暗号の構成と安全性の証明方法について
矢内 直人
テーマ: 電子署名の構成とその応用プロトコルについて
吉田 真紀
テーマ: 暗号プロトコルの安全性確認の自動化について
安永 憲司
テーマ: 不完全な乱数と暗号
河内 亮周
テーマ: 暗号における定数段回路について
連絡先: 河内(kawachi[at]is.tokushima-u.ac.jp)
|
9/14 - 18
| ALGO 2015 |
| Place : Patras, Greece |
9/17 - 18
| IABD2015 (International Workshop on Innovative Algorithms for Big Data) |
| 投稿〆切 : 2015/7/15 |
| Place : 京都テルサ |
| クレスト「ビッグデータ時代に向けた革新的アルゴリズム基盤」主催の国際会議です。
投稿は1Pアブストラクトのみ。
JCDCG^2 2015(9/14-16, 京大時計台)と連続開催。
|
9/23 - 25
| [elc] ELC 秋学校 2015 |
| Place : ホテル アルモニーテラッセ(岐阜県) |
| 9月23日
[13:00-16:00]
「遷移問題はじめてみませんか?」 伊藤健洋(東北大)
[16:00-17:00]
オープンプロブレムの紹介+自己紹介
[20:00-22:30]
ナイトセッション:自己紹介の続き
Click to Continue ...
9月24日
[09:00-12:00]
「ネットワーク時代の符号理論」 和田山正(名工大)
[13:00-16:00]
「乱択アルゴリズムの技法」 来嶋秀治(九州大学)
[16:00-17:00]
進捗報告とディスカッション
9月25日
[9:00-12:00]
TBA 宇野毅明(NII)
[12:00-]
まとめと解散
|
9/24 - 27
| SAT 2015 |
| 投稿〆切 : 2015/4/29 |
| Place : Austin, Texas, USA |
10/4
| [elc] GCT Workshop |
| Place : Komaba Campus @ The University of Tokyo |
| Date: OCT 4(SUN), 2015
Time: 12:00~
Place: Room 118 Suri-Kenkyuuka-tou, Komaba Campus of The University of Tokyo
http://www.u-tokyo.ac.jp/campusmap/cam02_01_27_j.html
Speaker: Jun Tarui (The University of Electro-Communications)
Title:
Click to Continue ...Arithmetic Branching Program & Permanent
Speaker: Susumu Ariki (Osaka University)
Title:
Discussions about Ikenmeyer-Mulmuley-Walter2015: On vanishing of Kronecker coefficients
|
10/4 - 6
| ALT 2015 |
| 投稿〆切 : 2015/5/11 |
| Place : Banff, Canada |
10/7
| [elc] ELC Seminar(Prof. Mitsunori Ogihara ) |
| Place : Faculty of Engineering, Yamagata University |
| ELC Seminar
Date: October 7, 2015
Time: 16:10~
Place: Faculty of Engineering, Yamagata University, Building No. 4, Room 116
Speaker: Prof. Mitsunori Ogihara (University of Miami)
Title: Data Mining for Non-scientific Research
Click to Continue ...Abstract: Data mining is a research that aims at developing techniques
for discovering interesting patterns in datasets that are otherwise
trashed.
The use of data mining for knowledge discovery was limited to
businesses, but now, thanks to the proliferation of high-speed
Internet connections and data storage, data mining has been creeping
into other areas, such as biology and medicine. In this talk I will
present and discuss some instances of data mining for non-scientific
disciplines, such as humanities and music.
|
10/13
| [elc] ELC Seminar (Prof. Mitsunori Ogihara )@CELC |
| Place : ELC Center |
| ELC Seminar
Date: October 13(Tue), 2015
Time: 11:00~
Speaker: Prof. Mitsunori Ogihara (University of Miami)
Title: Complexity of Synchronous Boolean Finite Dynamical Systems
Abstract: The finite dynamical system is a system consisting of some finite
Click to Continue ...number of objects that take upon a value from some domain as a state, where
after initialization the states of the objects are updated based upon the
states of the other objects and themselves according to a certain update
schedule. The synchrnous boolean finite dynamical system (synchronous BFDS,
for short) is its subclass in which the states are boolean and the state
update takes place in discrete time and at the same on all objects.
This talk is concerned with some problems regarding the behavior of
synchronous BFDS in which the state update functions are chosen from
a predetermined finite basis of boolean functions, in particular, the
problem of deciding convergence, the problem of calculating the cycle
length, and the problem of testing whether paths originating from two
configurations intersect. I will show that:
. The three problems are each PSPACE-complete if the function basis can
generate two out of { AND, OR, NOT }.
. If the basis is AND-only, OR-only, XOR-only, or XOR+NXOR only, then
convergence is polynomial time solvable, the intersection problem is in
UP, the cycle length problem is in UP-cap-coUP.
Also, I will show that the intersection problem is randomized polynomial
time reducible to the Minimum Circuit Size Problem.
This is joint work with Kei Uchizawa
|
10/15 - 16
| RAMP シンポジウム |
| Place : 静岡大学浜松キャンパス・佐鳴会館 |
| RAMPシンポジウムは、日本オペレーションズ・リサーチ学会の数理計画研究部会によって年一度開催される、最適化、数理計画に関するシンポジウムです。
|
10/18 - 20
| FOCS 2015 |
| 投稿〆切 : 2015/4/2 |
| Place : DoubleTree Hotel at the Berkeley Marina, Berkeley, California, USA |
10/30 - 31
| [elc] 平成27年度 第2回領域会議 |
| Place : 金沢市文化ホール |
| 領域会議
日時: 10月30,31日
場所: 金沢市文化ホール
http://www.bunka-h.gr.jp/
第5・6会議室
参加登録:https://www.al.ics.saitama-u.ac.jp/elc/reg/2015_1030_elc/
Click to Continue ...10月30日
13:30~13:50 はじめに 研究代表 渡辺 治
13:50~14:03 A01班の成果発表
14:03~14:16 A02班の成果発表
14:16~14:29 A03班の成果発表
14:29~14:42 B01班の成果発表
14:42~15:00 休憩
15:00~15:13 B02班の成果発表
15:13~15:26 B03班の成果発表
15:26~15:39 C01班の成果発表
15:39~15:52 C02班の成果発表
15:52~16:05 C03班の成果発表
16:05~16:25 休憩
若手研究発表
16:25~16:55 小長谷松雄 (JAIST)
16:55~17:25 藤田隆寛 (九大)
18:00~ 懇親会
10月31日
PD関連発表
9:30~10:00 脊戸 和寿 (成蹊大)
10:00~10:30 森 立平 (東工大)
10:30~10:50 休憩
10:50~11:20 Rémy Belmonte (京大)
11:20~11:50 Navid Talebanfard (東工大)
11:50~13:15 Lunch (総括班会議 12:00~13:00)
13:15~13:45 長尾 篤樹 (電通大)
13:45~14:00 ELCの今後に向けて 研究代表 渡辺 治
総括班会議
日時: 10月31日 12:00~13:00
場所: 金沢ニューグランドホテル 3F
https://www.new-grand.co.jp/
会議室パラッツオ
|
11/5
| [elc] ELC Seminar (Prof. Pudlk) |
| Place : CELC seminar room |
| Date and place: Nov. 5th, 13:30-14:30, ELC seminar room
speaker: Pavel Pudlák (Mathematical Institute of the Academy of
Sciences of the Czech Republic)
title: Proof systems for Integer Linear Programing and monotone computations.
Click to Continue ...abstract: Many proof systems for Integer Linear Programing have been
studied. However, there are only a few for which exponential lower bounds
have been proven. One system for which no unconditional lower bounds are
known is the Lovasz-Schrijver system (with DAG-like proofs). We will
show a reduction of proving lower bounds for this system to proving lower
bounds on a computational model "monotone linear programs". This is a new
model for computing monotone Boolean functions based, as the name
suggests, on linear programs. We mention some properties of the model; in
particular, that it is strictly stronger than monotone Boolean circuits.
Furthermore, we explain a connection to lower bounds on extended
formulations in combinatorial optimization.
Part of these results is a joint work with Pavel Hrubes and
Mateus de Oliveira Oliveira.
* Please note that this seminar is a blackboard type informal one,
more formal one will be held in Kyoto next week.
* Host: Osamu Watanabe (watanabe@is.titech.ac.jp)
|
11/12
| [elc] ELC Seminar (Dr. Christian Engels) |
| Place : CELC seminar room |
| C01 Postdoc Welcome Seminar
This is a seminar for introducing Chirstian who came to Tokyo
as a C01 postdoc fellow. Please join us for this seminar.
Let me know if anyone wants to join the seminar by polycom.
Osamu Watanabe
Click to Continue ...=====
speaker: Dr. Cristian Engels
date: Nov. 12 (Thur.) 13:30 - 15:30
place: ELC seminar room
title: Two Theorems on Arithmetic Circuit Complexity
abstract:
In this presentation we give a short introduction to the field
of arithmetic circuit complexity as well as show two theorems
as examples on the kind of problems one can look at.
The first problem is based on graph homomorphisms and asks how
hard polynomials based on enumerating all homomorphisms from
some fixed graph class G to a given graph H are. We show major
dichotomies for many natural graph classes.
The second theorem looks at non-commutative permanent/determinant.
We show here that for even very restricted graph classes the
non-commutative permanent/determinant on these graphs need large
arithmetic branching programs. Arithmetic branching programs here
are a specialized arithmetic circuit class.
host: watanabe@is.titech.ac.jp
|
11/16
| [elc] ELC Seminar (Colin Cooper, Nicolas Rivera) |
| Place : 九州大学 伊都キャンパス |
| 九州大学 伊都キャンパス
ウェスト2号館3階 第5・6講義室(W2-325室)
November 16 (Mon)
13:30-14:30 Nicolas Rivera (King's College London, UK),
The Linear Voting Model
Click to Continue ...Abstract:
We study a general model of probabilistic voting on graphs called the
Linear Voting Model. The model is flexible enough to include some
well-known models as pull voting and push voting. Under certain
conditions the linear voting model has several desirable properties,
in particular it reaches consensus and the consensus time is finite.
By the use of analytic techniques we investigate problems such as the
probability that a certain opinion wins the polling, the influence of
high/low degree vertices and the time to reach consensus.
14:50-15:50 Colin Cooper (King's College London, UK),
Vacant sets and vacant nets: Critical times
for simple and modified random walks
Abstract:
The first part of the talk is an introduction to the idea of the
vacant set of a discrete random walk. The vacant set of a random walk
is the set of vertices of the graph not visited by the walk.
Similarly, the vacant net is the set of unvisited edges.
We study the change in size and structure of the graph induced by
the vacant set as the walk proceeds. A critical time is a step of
the walk before which the graph of the vacant set contains large
unexplored connected components, and after which it contains only
small unexplored components. For some classes of random graphs we can
find a precise critical time.
In the second part of the talk, we compare the critical time on
these graphs for three types of random walks (simple, non-
backtracking, unexplored edges first). In order to break the graph
up into small unexplored components as quickly as possible, the walk
with the earliest critical time is best.
問合せ:来嶋(B01)
|
11/28
| GCT研究集会 |
| Place : Komaba Campus @ The University of Tokyo |
| Date: NOV 28(SAT), 2015
Time: 14:00~
Place: Room 118 Suri-Kenkyuuka-tou, Komaba Campus of The University of Tokyo
http://www.u-tokyo.ac.jp/campusmap/cam02_01_27_j.html
Speaker: Ruo Nishiyama(Aoyama Gakuin University)
Title:
Click to Continue ..."Permanent v. determinant: an exponential lower bound assuming symmetry and
a potential path towards Valiant's conjecture, arXiv:1508.05788"
|
11/28
| [elc] GCT Workshop |
| Place : Komaba Campus @ The University of Tokyo |
| Date: NOV 28(SAT), 2015
Time: 14:00~
Place: Room 118 Suri-Kenkyuuka-tou, Komaba Campus of The University of Tokyo
http://www.u-tokyo.ac.jp/campusmap/cam02_01_27_j.html
Speaker: Kyo Nishiyama(Aoyama Gakuin University)
Title:
Click to Continue ..."Permanent v. determinant: an exponential lower bound assuming symmetry and
a potential path towards Valiant's conjecture, arXiv:1508.05788"
|
11/28 - 29
| [elc] ELC Mini-Workshop (B01,C03) |
| Place : 山形大学工学部 100周年記念館セミナールーム1 |
| 11/28(土)
13:10-13:50
吉仲 亮
連言文法の分布学習
13:50-14:30
Click to Continue ...正代 隆義
Polynomial time inductive inference of graph pattern languages
with few P4's from positive data
14:30-14:40 休憩
14:40-15:40
神山 直之
Exact and Approximation Algorithms for Weighted Matroid Intersection
15:40-16:20
内澤 啓
しきい値回路による特徴写像
16:20-16:30 休憩
16:30-17:10
篠原 歩
文字列方程式の計算量について
17:10- ディスカッション
11/29(日)
9:30-10:10
白髪 丈晴
Fast Consensus for Voting on General Expander Graphs
10:10-10:50
森富 賢一郎
相対評価に基づく協調ランキング問題
10:50-11:30
轟 奨太
ZDDの質問学習について
11:30-11:40 休憩
11:40-12:20
加藤 直樹
組合せ剛性理論とその応用
|
12/1
| [elc] 学習とメカニズムデザイン |
| Place : 九州大学 伊都キャンパス ウエスト1号館 C棟513 |
12/3
| [elc] ELC Mini-Workshop (C01) |
| Place : Center for ELC Seminar Room (CIC 4F) |
| Time & Date: Dec. 3rd (Thu): 14:00 - 16:00
Place: CELC Seminar Room (Tokyo Tech. CIC 4F)
Speaker: Alexander Knop
(St. Petersburg Department of V.A. Steklov Institute of Mathematics)
Title: Complexity of distributions and average-case hardness
Abstract:
Click to Continue ...In this talk we address to a natural question in average-case
complexity: does there exist a language L such that for all easy
distributions D the distributional problem (L, D) is easy on
the average while there exists some more hard distribution D'
such that (L, D') is hard on the average?
We prove that there exists such language L and such distribution D
samplable in n^{\log^2 n} steps and linear-time algorithm A such
that for every polynomial-time samplable distribution F,
A correctly decides L on all inputs from {0, 1}^n except of a set
that has infinitely small F-measure and for every algorithm B
there are infinitely many n such that set of all elements of {0, 1}^n
such that B correctly decides L on them has infinitely small D-measure.
Speaker: Dmitry Sokolov
(St. Petersburg Department of V.A. Steklov Institute of Mathematics)
Title: Lower bound for splitting by linear combinations.
Abstrqact:
A typical DPLL algorithm for the Boolean satisfiability problem
splits the input problem into two by assigning the two possible
values to a variable; then it simplifies the two resulting formulas.
In this talk we consider an extension of the DPLL
paradigm. Our algorithms can split by an arbitrary linear
combination of variables modulo two. These algorithms quickly solve
formulas that explicitly encode linear systems modulo two, which
were used for proving exponential lower bounds for
conventional DPLL algorithms. We prove exponential lower bounds
on the running time of DPLL with splitting by linear combinations
on 2-fold Tseitin formulas.
Raz and Tzameret introduced a system R(lin) which operates with
disjunctions of linear equalities with integer coefficients. We
consider an extension of the resolution proof system that operates
with disjunctions of linear equalities over F_2; we call
this system Res-Lin. Res-Lin can be p-simulated in R(lin) but
currently we do not know any superpolynomial lower bounds in
R(lin). Tree-like proofs in Res-Lin are equivalent
to the behavior of our algorithms on unsatisfiable instances.
We consider relations between Res-Lin semantic version of
Res-Lin and R(lin). We prove a space-size tradeoff for
Res-Lin proofs of 2-fold Tseitin formulas.
(host: watanabe@is.titech.ac.jp)
|
12/4
| [elc] ELC Seminar (A02) |
| Place : CELC Seminar Room #404 |
| Date: 11:00-12:00, Dec 4, 2015
Speaker: Jeong Han Kim, Korea Institute for Advanced Study (KIAS)
https://en.wikipedia.org/wiki/Jeong_Han_Kim
Title: How to find counterfeit coins? An algorithmic version.
Abstract:
In this talk, we consider a well-known combinatorial search problem.
Suppose that there are n identical looking coins and some of them are
Click to Continue ...counterfeit. The weights of all authentic coins are the same and known a priori.
The weights of counterfeit coins vary but different from the weight of
an authentic coin.
Without loss of generality, we may assume the weight of authentic coins is 0.
The problem is to find all counterfeit coins by weighing (queries) sets of coins
on a spring scale. Finding the optimal number of queries is difficult even
when there are only 2 counterfeit coins.
We introduce a polynomial time randomized algorithm to find all
counterfeit coins when the number of them is known to be at most
m > 1 and the weight w(c) of each counterfeit coin c satisfies
a < |w(c)| < b
for fixed constants a, b>0. The query complexity of the
algorithm is O(frac{m log n }{log m}), which is optimal up to a
constant factor. The algorithm uses, in part, random walks.
The algorithm may be generalized to find all edges of a hidden
weighted graph using a similar type of queries. This graph finding algorithm
has various applications including DNA sequencing.
No prior knowledge of graph theory is needed in this talk.
host: Ken-ichi Kawarabayashi(NII, A02)
|
12/9 - 11
| ISAAC 2015 |
| 投稿〆切 : 2015/6/19 |
| Place : Nagoya, Japan |
12/16 - 18
| FSTTCS 2015 |
| 投稿〆切 : 2015/7/13 |
| Place : Indian Institute of Science, Bangalore |
12/17
| [elc] ELC Mini-Workshop (C01) |
| Place : CELC 4F seminar room |
| ELC Mini Workshop (C01)
Dec. 17th (Thu): 14:00 - 17:00
CELC Seminar Room (Tokyo Tech. CIC 4F)
Group C01 is going to organize a mini workshop having three imporatnt
visitors, Raghunath Tewari, Hubie Chen, and Luca Trevisan.
Click to Continue ...
We are planning to go somewhere nearby for dinner welcoming the
visitors. Please let me know if any one wants to join us.
Osamu Watanabe, watanabe@is.titech.ac.jp
14:00-15:00
Speaker: Raghunath Tewari (IIT Kanpur)
Title: Simultaneous Time-Space Bounds for the Graph Reachability Problem
Abstract:
Graph reachability is a fundamental problem in computer science and
understanding it's computational complexity is of utmost importance.
There exists linear time algorithms for this problem such as BFS and
DFS however both these algorithms also require a linear amount of space.
In 1970 Savitch showed that directed graphs reachability can be
decided in $O(\log^2 n)$ space. However his algorithm requires
$\Omega(n^{\log n})$ time. This gave rise to the following question
-- can we decide reachability in polynomial time and polylogarithmic
space simultaneously? In 1992, Barnes, Buss, Ruzzo and Schieber
made some progress by giving a polynomial time and
$O(n/2^{\sqrt{\log n}})$ space algorithm for this problem.
In this talk, I will present some recent progress on this problem,
particularly for certain classes of topologically restrictive
graphs such as planar graphs, bounded genus graphs and
minor-free graphs.
15:15-15:45
Speaker: Hubie Chen (Univ. del Pai's Vasco & IKERBASQUE)
Title: Parameter Compilation
Abstract:
In resolving instances of a computational problem, if multiple
instances of interest share a feature in common, it may be
fruitful to compile this feature into a format that allows
for more efficient resolution, even if the compilation is
relatively expensive. In this article, we introduce a formal
framework for classifying problems according to their
compilability. The basic object in our framework is that of a
parameterized problem, which here is a language along with
a parameterization---a map which provides, for each instance,
a so-called parameter on which compilation may be performed.
Our framework is positioned within the paradigm of parameterized
complexity, and our notions are relatable to established concepts
in the theory of parameterized complexity. Indeed, we view
our framework as playing a unifying role, integrating
together parameterized complexity and compilability theory.
A version of the article is available on the arxiv:
http://arxiv.org/abs/1503.00260
16:00-17:00
Speaker: Luca Trevisan (UC Berkley)
Title: The Approximability of Non-Boolean Constraint Satisfaction Problem
Abstract:
We study constraint satisfaction problems in which we are given a set
of constraints such that each constraint involves at most k variables,
and each variable ranges over a finite set of R possible values, and
we want to find an assignment that satisfies the largest number of
constraints.
It was known that, for fixed k, the problem admits a polynomial time
algorithm that satisfies at least c/R^{k-1} times the optimum number
of constraints, where c is a constant, and that an approximation
better than c'/R^{k-2} is NP-hard, where c' is a different constant.
We give a polynomial time algorithm, based on semidefinite
programming, that achieves an approximation ratio of the order of (log
R)/R^{k-1}, and we show that approximation better than order of (log
R)^{k/2} / R^{k-1} is impossible in polynomial time, assuming the
unique games conjecture.
Based on joint work with Guy Kindler, Alexandra Kolla, Pasin
Manurangsi and Preetum Nakkiran
|