研究活動 – 多面的アプローチの統合による計算限界の解明

GCT Workshop 5

elcoffice — Tue, 13 Dec 2016 01:19:50 +0000

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”

GCT Workshop 4

elcoffice — Sun, 16 Oct 2016 08:40:51 +0000

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.

ELC 計算量理論の秋学校2016

uchizawa — Fri, 26 Aug 2016 05:02:22 +0000

開催日時	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-) 講演資料	永野　清仁（公立はこだて未来大学）

GCT Workshop 3

elcoffice — Wed, 27 Jul 2016 04:58:55 +0000

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 ”

GCT Workshop 1

elcoffice — Sat, 09 Jul 2016 06:51:11 +0000

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)”

GCT Workshop 2

elcoffice — Sat, 09 Jul 2016 04:55:21 +0000

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)”

ELC Seminar (Prof. Venkatesan Guruswami )

elcoffice — Mon, 14 Mar 2016 00:45:45 +0000

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)

ELC Seminar (Dr. David Rosenbaum)

elcoffice — Mon, 07 Mar 2016 01:58:31 +0000

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)

ELC Seminar (A03)

elcoffice — Mon, 22 Feb 2016 01:05:20 +0000

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)

GCT Workshop

elcoffice — Thu, 04 Feb 2016 06:15:04 +0000

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”

研究活動 – 多面的アプローチの統合による 計算限界の解明

GCT Workshop 5

GCT Workshop 4

ELC 計算量理論の秋学校2016

GCT Workshop 3

GCT Workshop 1

GCT Workshop 2

ELC Seminar (Prof. Venkatesan Guruswami )

ELC Seminar (Dr. David Rosenbaum)

ELC Seminar (A03)

GCT Workshop

研究活動 – 多面的アプローチの統合による計算限界の解明