研究活動

2016年12月13日GCT Workshop 5

Time & Date	Dec. 18 (SUN) 2016, 13:00~
Place	Rm 056 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker	徳山豪 Takeshi Tokuyama (Tohoku University)
Title	“On Erdos distance problem”

»続きを読む

2016年10月16日GCT Workshop 4

Time & Date	Oct.16 (SUN) 2016, 13:00~
Place	Rm 056 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker 1	山本亮 Ryo Yamamoto (Osaka Univ)
Title	(perm_n+det_n)/2の固定化部分群の決定について
Speaker 2	徳山豪 Go Tokuyama (Tohoku University)
Title	Larry Guth, Nets Hawk Katz, Algebraic Methods in Discrete Analogs of the Kakeya Problem arXiv:0812.1043.

»続きを読む

2016年8月26日ELC 計算量理論の秋学校2016

開催日時	2016年 9月20日（火）～ 9月22日（木）
開催場所	湘南国際村

「Online Learning: robustness and adaptivity」
　Wouter Koolen (Centrum Wiskunde & Informatica, Netherland)
「統計的学習における学習の限界とは? -深層学習での学習の失敗例とその対策-」
(What is the error of the statistical learning?　-failure and its remedy in deep learning-)
　前田　新一（京都大学）
「データ解析におけるプライバシ保護: 差分プライバシーと秘密計算」
(Privacy preservation in data analysis: differential privacy and secure multiparty computation)
　佐久間　淳（筑波大学）
「劣モジュラ関数最小化とその関連問題～理論と応用～」
(Submodular function minimization and related problems -Theory and Applications-)
　永野　清仁（公立はこだて未来大学）

プログラム
9月20日	[13:30-16:30] Online Learning: robustness and adaptivity 講演資料	Wouter Koolen (CWI, Netherlands)
	[16:30-17:30] 質問・回答・未解決問題セッション
	ナイトセッション
9月21日	[09:00-12:00] 統計的学習における学習の限界とは？- 深層学習での学習の失敗例とその対策- (What is the error of the statistical learning?　-failure and its remedy in deep learning-) 講演資料	前田　新一（京都大学）
	[13:30-16:30] データ解析におけるプライバシ保護: 差分プライバシーと秘密計算」 (Privacy preservation in data analysis: differential privacy and secure multiparty computation) 講演資料１　講演資料２　講演資料３	佐久間　淳（筑波大学）
	[16:30-17:30] 質問・回答・未解決問題セッション
	ナイトセッション
9月22日	[09:00-12:00] 劣モジュラ関数最小化とその関連問題～理論と応用～ (Submodular function minimization and related problems -Theory and Applications-) 講演資料	永野　清仁（公立はこだて未来大学）

2016年7月27日GCT Workshop 3

Time & Date	Sep. 4 (SAT) 2016, 13:00~
Place	Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker	Francois Le Gall（Kyoto University）
Title	“On Matrix Multiplication ”

»続きを読む

2016年7月9日GCT Workshop 1

Time & Date	May 22 (SUN) 2016, 13:00~
Place	Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker	Susumu Ariki(Osaka University)
Title	“Burgisser, Ikenmeyer and Panova: No occurrence obstructions in geometric complexity theory, arXiv:1604.0643(Part 1)”

»続きを読む

2016年7月9日GCT Workshop 2

Time & Date	Jul. 9 (SAT) 2016, 13:00~
Place	Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker	Susumu Ariki(Osaka University）
Title	“Burgisser, Ikenmeyer and Panova: No occurrence obstructions in geometric complexity theory, arXiv:1604.0643(Part 2)”

»続きを読む

2016年3月14日ELC Seminar (Prof. Venkatesan Guruswami )

Time & Date	April 15 (Fri) 16:00-17:00
Place	CELC (Center for ELC), Seminar room (Rm. 404)
Speaker	Prof. Venkatesan Guruswami (Carnegie Mellon University)
Title	Progress in Error-Correction: New Codes for Old Noise Models

Abstract
Error-correcting codes play a crucial role in safeguarding data against the adverse effects of noise during communication and storage. They are also powerful tools that underly several modern advances in theoretical computer science. The central challenge in coding theory is to construct codes with minimum possible redundancy for different noise models and requirements on the decoder, along with efficient algorithms for error-correction using those codes. Much progress has been made toward this quest, both in theory and practice, in the 65+ years since the birth of coding theory. Several fundamental problems, however, continue to challenge us, and exciting new questions have emerged to address the demands of modern technologies. This talk will survey some of our recent works on error-correction in various noise models, such as: – worst-case errors, where we construct list decodable codes with redundancy as small as the target error fraction; – i.i.d. errors, where we show polar codes enable efficient error-correction even as the redundancy approaches Shannon capacity; – bit deletions, where we give the best known codes against both a constant number and a constant fraction of deletions; – node failure in distributed storage, where we give low-bandwidth repair algorithms for the ubiquitous Reed-Solomon codes. (host:O. Watanabe, watanabe@is.titech.ac.jp)

Abstract

Error-correcting codes play a crucial role in safeguarding data against the adverse effects of noise during communication and storage. They are also powerful tools that underly several modern advances in theoretical computer science. The central challenge in coding theory is to construct codes with minimum possible redundancy for different noise models and requirements on the decoder, along with efficient algorithms for error-correction using those codes. Much progress has been made toward this quest, both in theory and practice, in the 65+ years since the birth of coding theory. Several fundamental problems, however, continue to challenge us, and exciting new questions have emerged to address the demands of modern technologies. This talk will survey some of our recent works on error-correction in various noise models, such as:

– worst-case errors, where we construct list decodable codes with redundancy as small as the target error fraction;
– i.i.d. errors, where we show polar codes enable efficient error-correction even as the redundancy approaches Shannon capacity;
– bit deletions, where we give the best known codes against both a constant number and a constant fraction of deletions;
– node failure in distributed storage, where we give low-bandwidth repair algorithms for the ubiquitous Reed-Solomon codes.

(host:O. Watanabe, watanabe@is.titech.ac.jp)

»続きを読む

2016年3月7日ELC Seminar (Dr. David Rosenbaum)

Time & Date	March 22nd(Tue) 13:30-14:30
Place	CELC (Center for ELC), Seminar room (Rm. 404)
Speaker	Dr. David Rosenbaum (The University of Tokyo)
Title	Algorithms for hard instances of group isomorphism

Abstract
The group isomorphism problem asks us to determine if two groups defined by their multiplication tables are isomorphic. In addition to being of interest as a fundamental problem in computational group theory, it is a special case of the graph isomorphism problem and is a significant obstacle to improving Babai’s recent quasipolynomial-time algorithm for graph isomorphism. For several decades, the best worst-case algorithm known for difficult cases of group isomorphism was the generator-enumeration algorithm which runs in n^(log n + O(1)) time. In this talk, we consider several difficult cases of the group isomorphism problem and show improvements over the generator-enumeration algorithm. (host: F. Le Gall and O. Watanabe, watanabe@is.titech.ac.jp)

Abstract

The group isomorphism problem asks us to determine if two groups defined by their multiplication tables are isomorphic. In addition to being of interest as a fundamental problem in computational group theory, it is a special case of the graph isomorphism problem and is a significant obstacle to improving Babai’s recent quasipolynomial-time algorithm for graph isomorphism. For several decades, the best worst-case algorithm known for difficult cases of group isomorphism was the generator-enumeration algorithm which runs in n^(log n + O(1)) time. In this talk, we consider several difficult cases of the group isomorphism problem and show improvements over the generator-enumeration algorithm.

(host: F. Le Gall and O. Watanabe, watanabe@is.titech.ac.jp)

»続きを読む

2016年2月22日ELC Seminar (A03)

Time & Date	Mar. 10(Thu) 2016, 13:00 – 17:00 (The starting time is tentative)
Place	CELC Seminar room (Rm. 404)
Speaker	Goran Zuzic (CMU)
Title	Low-Congestion Shortcut without Embedding

Abstract
Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. Recent work by [Ghaffari and Hauepler; SODA’16] showed that this phenomenon can be seen as the broad underlying reason for the pervasive $\Omega(\sqrt{n} + D)$ lower bounds that apply to most optimization problems in the CONGEST model. On the positive side this work also introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exists good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast $O(D \log^{O(1)} n)$ distributed optimization algorithms on such topologies, e.g., for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner. Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA’16] relies heavily on having access to a bounded genus embedding of the network. Computing such an embedding distributively however is a hard problem – even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight. In this work we side-step this problem by defining a slightly restricted and more structured form of shortcuts and giving a novel construction algorithms which efficiently finds a shortcut which is, up to a logarithmic factor, as good as the best shortcut that exists for a given network. This new construction algorithm directly leads to an $O(D \log^{O(1)} n)$ round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist – without the need to compute any embedding. This includes the first efficient algorithms for bounded genus graphs or graphs with bounded pathwidth. Note: We also arrange an open slot for discussion and sharing ideas among participants. (Host: Tisuke Izumi)

Abstract

Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. Recent work by [Ghaffari and Hauepler; SODA’16] showed that this phenomenon can be seen as the broad underlying reason for the pervasive $\Omega(\sqrt{n} + D)$ lower bounds that apply to most optimization problems in the CONGEST model. On the positive side this work also introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exists good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast $O(D \log^{O(1)} n)$ distributed optimization algorithms on such topologies, e.g., for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner.
Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA’16] relies heavily on having access to a bounded genus embedding of the network. Computing such an embedding distributively however is a hard problem – even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight.
In this work we side-step this problem by defining a slightly restricted and more structured form of shortcuts and giving a novel construction algorithms which efficiently finds a shortcut which is, up to a logarithmic factor, as good as the best shortcut that exists for a given network. This new construction algorithm directly leads to an $O(D \log^{O(1)} n)$ round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist – without the need to compute any embedding. This includes the first efficient algorithms for bounded genus graphs or graphs with bounded pathwidth.

Note: We also arrange an open slot for discussion and sharing ideas among participants.

(Host: Tisuke Izumi)

»続きを読む

2016年2月4日GCT Workshop

Time & Date	Mar.27 (SUN) 2016, 13:00~
Place	Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker 1	有木進 Susumu Ariki (Osaka Univ)
Title	“Fundamental invariants of orbit closures by Burgisser and Ikenmeyer (arXiv:1511.02927)”
Speaker 2	垂井淳 Jun Tarui (The University of Electro-Communications )
Title	“natural proof”

»続きを読む

2016年1月20日ELC School on Parameterized Algorithms

Time & Date	Mar. 17(Thu) 2016 ~ Mar. 20(Sun) 2016
Place	Kwansei Gakuin University, Umeda campus, Osaka TKP Garden City Higashi Umeda (Sunday only)
Speaker	Daniel Lokshtanov, University of Bergen, Norway Michał Pilipczuk, University of Warsaw, Poland
Description	The lectures will cover introductory notions, accessible to beginners, as well as more recent and advanced results. The school is primarily intended for graduate students and young researchers who wish to get acquainted with and further their knowledge of this rapidly growing field.
Material	The course will be based on the book “Parameterized algorithms” of Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk and Saurabh, however the book will not be required during the lectures or exercise sessions.
Tentative Schedule	*Thursday to Saturday: 10:30 – 11:15: Morning lecture, part 1 11:15 – 11:30: Coffee break 11:30 – 12:15: Morning lecture, part 2 12:15 – 12:30: Questions (12:30 – 14:00: Lunch break) 14:00 – 14:45: Afternoon lecture, part 1 14:45 – 15:00: Coffee break 15:00 – 15:45: Afternoon lecture, part 2 15:45 – 16:00: Coffee break 16:00 – 17:00: Exercise session *Sunday 10:30 – 11:15: Morning lecture, part 1 11:15 – 11:30: Coffee break 11:30 – 12:15: Morning lecture, part 2 12:15 – 12:30: Questions (12:30 – 14:00: Lunch break) 14:00 – 15:00: Exercise session Local organizers: Rémy Belmonte Naoki Katoh

2016年1月20日ELC Seminar (Gregory Gutin)

Time & Date	Mar. 29(Tue) 2016, 10:30 ~ 12:00
Place	CELC Seminar room (Rm. 404)
Speaker	Gregory Gutin (Royal Holloway, University of London)
Title	Constraint Satisfaction Problems Parameterized above Average

Abstract
By computing the expected value of an appropriate random variable, it is not hard to see that every directed graph $D$ on $m$ arcs has an acyclic subgraph with at least $m/2$ arcs. The bound is tight: consider any digraph which contains arc $xy$ iff it contains arc $yx$. Similarly, it is not hard to see that we can satisfy at least $(1-2^{-r})m$ clauses in any CNF formula $F$ with $m$ clauses each with $r$ distinct variables. Again the bound is tight. Mahajan, Raman and Sikdar (IWPEC 2006 and JCSS 2009) asked whether there are fixed-parameter tractable algorithms for deciding whether $D$ has an acyclic subgraph with at least $m/2+k$ arcs and whether we can satisfy at least $(1-2^{-r})m+k$ clauses in $F$. To answer these and other questions of this nature, a new parameterized complexity method was introduced by Gutin, Kim, Szeider and Yeo (JCSS 2011) and developed in Alon, Gutin, Kim, Szeider and Yeo (Algorithmica 2011) and other papers including Makarychev, Makarychev and Zhou (FOCS 2015). We will describe the method which uses probabilistic tools as well as tools from Fourier analysis. We will also mention that to prove that MaxLin above Average is fixed-parameter tractable, required a different approach using algorithmic and linear algebraic tools.

»続きを読む

2015年12月10日ELC Seminar (A02)

Time & Date	Dec. 4(Fri) 2015, 11:00 ~ 12:00
Place	CELC Seminar room (Rm. 404)
Speaker	Jeong Han Kim, Korea Institute for Advanced Study (KIAS)
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 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 ueries. 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)

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 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 ueries. 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)

»続きを読む

2015年12月10日ELC Seminar (A03)

Time & Date	Feb. 19(Fri) 2016, 14:00 ~ 16:15
Place	CELC Seminar room (Rm. 404)
Speaker	Hans L. Bodlaender
Title	Kernelization: upper and lower bound techniques

Abstract
In this talk, a survey on the topic of kernelization is given. In the first part, the notion is introduced, and a number of examples of kernelization algorithms are given, and some techniques to obtain kernels are reviewed. In the second part, recent techniques to obtain lower bounds for kernels are surveyed: with help of compositions or cross-compositions, it can be shown for a large collection of problems that these do not have kernels of polynomial size, assuming that coNP is not a subset of NP/poly. (Host: Yota Otachi)

Abstract

In this talk, a survey on the topic of kernelization is given. In the first part, the notion is introduced, and a number of examples of kernelization algorithms are given, and some techniques to obtain kernels are reviewed. In the second part, recent techniques to obtain lower bounds for kernels are surveyed: with help of compositions or
cross-compositions, it can be shown for a large collection of problems that these do not
have kernels of polynomial size, assuming that coNP is not a subset of NP/poly.

(Host: Yota Otachi)

»続きを読む

2015年12月10日ELC Seminar (A03)

Time & Date	Feb. 15(Mon) 2016, 14:00 ~ 15:30
Place	CELC Seminar room (Rm. 404)
Speaker	Hans L. Bodlaender
Title	Subexponential time algorithms for graph embedding problems on H-minor free graphs

Abstract
In this talk, a number of graph embedding problems are considered: given a graph G and a graph P, is P isomorphic to a subgraph of G, is P isomorphic to an induced subgraph of G, is P a minor of G, and is P an induced minor of G. For each of these problems, there is an algorithm that uses 2^O(n/log n) time when there is a fixed graph H such that G does not contain H as a minor. Amongst others, this implies an algorithm for subgraph isomorphism, induced subgraph isomorphism, minor testing or induced minors for planar graphs and graphs with bounded treewidth with this running time. We also show that the result is tight: assuming the exponential time hypothesis, there is no algorithm for graphs of pathwidth 3 with 2^o(n/log n) unning time for each of these problems. Similar algorithms and lower bounds exist for the Intervalizing k-colored graphs problem, and the problem to find path or tree decompositions of bounded width with a minimum number of bags. This is joint work with Tom van der Zanden, Jesper Nederlof, and Johan van Rooij. (Host: Yota Otachi)

Abstract

In this talk, a number of graph embedding problems are considered: given a graph G and a graph P, is P isomorphic to a subgraph of G, is P isomorphic to an induced subgraph of G, is P a minor of G, and is P an induced minor of G. For each of these problems, there is an algorithm that uses 2^O(n/log n) time when there is a fixed graph H such that G does not contain H as a minor. Amongst others, this implies an algorithm for subgraph isomorphism, induced subgraph isomorphism, minor testing or induced minors for planar graphs and graphs with bounded treewidth with this running time.
We also show that the result is tight: assuming the exponential time hypothesis, there is no algorithm for graphs of pathwidth 3 with 2^o(n/log n) unning time for each of these problems.
Similar algorithms and lower bounds exist for the Intervalizing k-colored graphs problem, and the problem to find path or tree decompositions of bounded width with a minimum number of bags.
This is joint work with Tom van der Zanden, Jesper Nederlof, and Johan van Rooij.

(Host: Yota Otachi)

»続きを読む

2015年12月10日GCT Workshop

Time & Date	Nov. 28 (SAT) 2016 , 14:00~
Place	Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker	Kyo Nishiyama (Aoyama Gakuin University)
Title	“Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant’s conjecture, arXiv:1508.05788”

»続きを読む

2015年12月10日GCT Workshop

Time & Date	Jan. 24(SUN) 2016, 13:00~
Place	Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
Speaker 1	松本久義 Hisayoshi Matsumoto (The University of Tokyo)
Title	orbit closureの不変式について
Speaker 2	垂井淳 Jun Tarui (The University of Electro-Communications )
Title	Natural Proofについて

»続きを読む

2015年12月9日平成27年度第２回領域会議

開催日時	2015年10月30日（金）～ 10月31日（土）
開催場所	金沢市文化ホール　http://www.bunka-h.gr.jp/　第５・６会議室

»続きを読む

2015年9月8日ELC 計算量理論の秋学校2015

開催日時	2015年 9月23日（水）～ 9月25日（金）
開催場所	ホテルアルモニーテラッセ

参加申し込み：　~~https://goo.gl/nnh29a （google のサイト）~~締め切りました

「遷移問題はじめてみませんか？」　　　　　　　　　伊藤健洋（東北大）
「ネットワーク時代の符号理論」　　　　　　　　　　和田山正（名工大）
「乱択アルゴリズムの技法」　　　　来嶋秀治（九州大）
「データ研磨：正確に解くことと、寄り添って解くこと」宇野毅明（NII）

プログラム
9月23日	[13:30-16:30 ] 「遷移問題はじめてみませんか？」　講義資料	伊藤健洋（東北大）
	[16:30-17:30] オープンプロブレムの紹介＋自己紹介
	ナイトセッション：自己紹介の続き
9月24日	[09:00-12:00] 「ネットワーク時代の符号理論」　講義資料１　講義資料２	和田山正（名工大）
	[13:00-16:00] 「乱択アルゴリズムの技法」　講義資料１　講義資料２　講義資料３	来嶋秀治（九州大）
	[16:00-17:00]
	ナイトセッション：　つづき
9月25日	[09:00-12:00] 「データ研磨：正確に解くことと、寄り添って解くこと」　講義資料（公開予定）	宇野毅明（NII）
9月25日	[12:00-] まとめと解散

問い合わせ先：　elc-autumnschool2015 at googlegroups.com

2015年5月11日平成２７年度第１回領域会議

開催日時	2015年 5月29日（金）～ 5月30日（土）
開催場所	東京工業大学田町キャンパスキャンパス・イノベーションセンター東京１階国際会議室

»続きを読む

Menu

編集 Menu

領域関係者

研究活動