2016年 | |
1/6 - 8
| Workshop on Big Graphs: Theory and Practice |
| Place : University of California, San Diego |
1/10 - 12
| SODA 2016 |
| 投稿〆切 : 2015/7/1 |
| Place : Arlington, Virginia, USA |
| July 1, 2015, 4:59 PM EDT - Deadline - Short Abstract Submission and Paper Registration Deadline
July 8, 2015, 4:59 PM EDT - Deadline - Full Paper Submission
|
1/10 - 13
| TCC 2016-A |
| Place : Tel Aviv, Israel |
1/12 - 5/13
| Counting Complexity and Phase Transitions |
| Place : Simons Institute, Berkeley |
1/12 - 5/13
| Algorithmic Challenges in Genomics |
| Place : Simons Institute, Berkeley |
1/14 - 16
| ITCS 2016 |
| 投稿〆切 : 2015/8/10 |
| Place : Cambridge, MA |
1/17 - 21
| Combinatorics: Challenges and Applications |
| Place : Tel Aviv University, Israel |
| Celebrating Noga Alon's 60th Birthday
|
1/24
| [elc] GCT Workshop |
| Place : Komaba Campus @ The University of Tokyo |
| Date: JAN 24(SUN), 2016
Time: 13: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: Hisayoshi Matsumoto(The University of Tokyo)
Title:
Click to Continue ...orbit closureの不変式について
Speaker: Jun Tarui(The University of Electro-Communications )
Title:
natural proofについて
|
1/25 - 4/1
| Nexus of Information and Computation Theories |
| Place : Paris, France |
2/3 - 12
| WACT 2016 |
| Place : Tel Aviv, Israel |
| url : https://www.cs.tau.ac.il/~shpilka/wact2016/ |
2/12 - 17
| AAAI-16 |
| 投稿〆切 : 2015/9/15 |
| Place : Phoenix, Arizona, USA |
| Workshop on Beyond NP
http://beyondnp.org/workshop16/
Submission Deadline: October 23, 2015
Notification: November 23, 2015
Workshop Dates: February 12-13, 2016
|
2/15
| [elc] ELC Seminar (Prof. Hans L. Bodlaender) |
| Place : ELC Center |
| ELC Seminar (A03)
Date: February 15 (2016)
Time: 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
Click to Continue ...
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) running 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)
|
2/17 - 20
| STACS 2016 |
| 投稿〆切 : 2015/9/18 |
| Place : Orleans, France |
2/19
| [elc] ELC Seminar (Prof. Hans L. Bodlaender) |
| Place : ELC Center |
| ELC Seminar (A03)
Date: February 19 (2016)
Time: 14:00-16:15
Place: CELC Seminar room (Rm. 404)
Speaker: Hans L. Bodlaender
Title: Kernelization: upper and lower bound techniques
Click to Continue ...
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)
|
3/7
| 第11回 組合せゲーム・パズル研究集会 |
| 投稿〆切 : 2016/2/12 |
| Place : 電気通信大学 西9号館 1階 135号室 |
| 3/07(日) アルゴリズム研究会
3/08(月)ゲーム情報学研究会
と連続開催。
|
3/10
| [elc] ELC Seminar (A03) |
| Place : CEL Center |
| ELC Seminar (A03)
Date: Mar.10
Time: TBA
Place: CELC Seminar room (Rm. 404)
Speaker: Goran Zuzic(CMU)
Title: TBA
Click to Continue ...Abstract : TBA
|
3/17 - 20
| [elc] ELC School on Parameterized Algorithms |
| Place : Kwansei Gakuin University, Umeda campus, Osaka |
| Speakers:
1. Daniel Lokshtanov, University of Bergen, Norway
2. Michał Pilipczuk, University of Warsaw, Poland
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
Click to Continue ...researchers who wish to get acquainted with and further their
knowledge of this rapidly growing field. (More information will
be available in Feb. at this page.)
|
3/22
| [elc] ELC Seminar (Dr. David Rosenbaum) |
| Place : Center for ELC Seminar room |
| Date and Time: March 22nd(Tue) 13:30-14:30
Place: Center for ELC, Seminar Room (Tamachi CIC 4F)
http://www.al.ics.saitama-u.ac.jp/elc/en/celc/
Speaker: Dr. David Rosenbaum (The University of Tokyo)
Title: Algorithms for hard instances of group isomorphism
Click to Continue ...
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)
|
3/27
| [elc] GCT Workshop |
| Place : Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo |
| GCT Warkshop
Date: Mar.27
Time: 15:00~
Place: Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo
http://www.u-tokyo.ac.jp/campusmap/cam02_01_27_j.html
Click to Continue ...Speaker: Susumu Ariki (Osaka Univ)
Title: "Fundamental invariants of orbit closures by Burgisser and Ikenmeyer (arXiv:1511.02927)"
Speaker: Jun Tarui(The University of Electro-Communications )
Title: "natural proof"
|
3/29
| [elc] ELC Seminar (Gregory Gutin) |
| Place : CELC Seminar room (Room 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
Click to Continue ...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.
|
3/29 - 31
| WALCOM 2016 (The 10th International Workshop on Algorithms and Computation) |
| 投稿〆切 : 2015/10/10 |
| Place : Kathmandu, Nepal |
4/- - 6/-
| Special Semester Program on Complexity Theory |
| Place : Chebyshev Laboratory, St.Petersburg State University |
4/10 - 15
| INFOCOM 2016 |
| Place : San Francisco, CA, USA |
4/11 - 16
| LATIN 2016 |
| 投稿〆切 : 2015/9/20 |
| Place : Ensenada, Mexico |
4/15
| [elc] ELC Seminar (Prof. Venkatesan Guruswami) |
| Place : CELC (Center for ELC), Seminar room (Rm. 404) |
4/22
| コンピューテーション研究会 |
| Place : 奈良先端科学技術大学院大学 |
5/8 - 12
| Eurocrypt 2016 |
| Place : Vienna, Austria |
5/14 - 16
| AAAC 2016 |
| 投稿〆切 : 2016/2/26 |
| Place : 台湾 |
5/22
| GCT Workshop |
| Place : Rm 118 Suri-Kenkyuka-tou, Komaba Campus of 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: Susumu Ariki (Osaka University)
Title: Burgisser, Ikenmeyer and Panova: No occurrence obstructions in geometric complexity theory, arXiv:1604.0643(Part 1)
Click to Continue ... |
5/22
| [elc] GCT Workshop 1 |
| Place : Komaba Campus @ The University of Tokyo |
| Date: May 22(SUN), 2016
Time: 13: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: Susumu Ariki(Osaka University)
Title:
Click to Continue ...Burgisser, Ikenmeyer and Panova: No occurrence obstructions in geometric complexity theory,
arXiv:1604.0643(Part 1)
|
5/29 - 6/1
| [elc] CCC 2016 |
| 投稿〆切 : 2015/11/23 |
| Place : Hitotsubashi Hall, Tokyo |
| Pre Event: May 28, Gakushi Kaikan, Tokyo
Post WS: June 2–3, Kyoto Univ.
|
6/1 - 3
| IPCO 2016 (IPCO XVIII) |
| Place : University of Liege, Belgium |
6/6 - 8
| Highlights of Algorithms 2016 |
| Place : Paris |
6/8 - 10
| FUN 2016 (The 8th International Conference on Fun with Algorithms) |
| 投稿〆切 : 2016/2/21 |
| Place : La Maddalena, Maddalena Islands, Italy |
6/9
| [elc] ELC Seminar (Prof. Avi Wigderson) |
| Place : 東京工業大学(大岡山)西8号館10F大会議室 |
| ランダムネスの神秘を語る
Avi Wigderson 教授(プリンストン高等研究所)
日時:6月9日(木)16時~17時
場所:東京工業大学(大岡山)西8号館E棟10F大会議室
(説明:英語の概要は最後に)
Click to Continue ...Wigderson(ヴィグダーソン)教授は,計算の理論において数々の重要な結果を挙げ
国際数学者会議ネヴァンリンナ賞やゲーデル賞を受賞している著名な研究者です.
この度,国際会議で来日される機会に,永年研究されてきたランダムネスについて
講演して頂くことになりました.高校生,学部生でも十分わかるお話しだそうです.
皆様のご参加をお待ちしています.
Randomness
Avi Wigderson, Institute for Advanced Study, Princeton Univ.
Abstract
Is the universe inherently deterministic or probabilistic? Perhaps
more importantly - can we tell the difference between the two?
Humanity has pondered the meaning and utility of randomness for
millennia. There is a remarkable variety of ways in which we
utilize perfect coin tosses to our advantage: in statistics,
cryptography, game theory, algorithms, gambling... Indeed,
randomness seems indispensable! Which of these applications
survive if the universe had no randomness in it at all? Which of
them survive if only poor quality randomness is available, e.g.
that arises from "unpredictable" phenomena like the weather or the
stock market?
A computational theory of randomness, developed in the past three
decades, reveals (perhaps counter-intuitively) that very little is
lost in such deterministic or weakly random worlds. In the talk
I'll explain the main ideas and results of this theory.
HOST: Osamu Watanabe
contact: elc-office@is.titech.ac.jp
|
6/9 - 13
| CSR 2016 |
| 投稿〆切 : 2015/12/11 |
| Place : St.Petersburg, Russia |
6/15 - 17
| 解析学と計算理論(CCA) |
| 投稿〆切 : 2016/3/14 |
| Place : ファーロ(葡) |
6/15 - 18
| SoCG 2016 |
| 投稿〆切 : 2015/11/27 |
| Place : Boston, MA, USA |
| * November 27, 2015: Paper abstracts (at most 300 words) due (23:59, UTC-9)
* December 4, 2015: Paper submissions due (23:59, UTC-9)
STOC2016と連続開催
|
6/19 - 21
| STOC 2016 |
| 投稿〆切 : 2015/11/2 |
| Place : Cambridge, MA |
| SoCG2016と連続開催
|
6/19 - 24
| ICML 2016 |
| Place : New York |
6/22 - 24
| SWAT 2016 |
| 投稿〆切 : 2016/2/14 |
| Place : Reykjavik, Iceland |
6/23
| [elc] ELC Seminar (Sebastian Pokutta) |
| Place : 九州大学 伊都キャンパス ウェスト2号館 3階 大講義室(W2-313) |
| 日時:6月23日(木)15:00-16:30
場所:九州大学 伊都キャンパス ウェスト2号館 3階 大講義室(W2-313)
Speaker:Dr. Sebastian Pokutta (Georgia Institute of Technology)
Title: An introduction to Extended Formulations
- capturing the expressive power of LPs and SDPs
Click to Continue ...
Abstract:
Linear and semidefinite programming are two core optimization
paradigms with many important applications in mathematics,
engineering, and business. However, the expressive power of these
modeling paradigms is only partially understood so far and extended
formulations are a powerful and natural tool to analyze the
possibilities and limitations of linear and semidefinite programming
formulations.
In this talk I will provide an overview of recent breakthrough
results in extended formulations, both in the linear and the
semidefinite setting, and lay out a reduction frameworks for
establishing upper and lower bounds for the size of exact and
approximate LP and SDP formulations. This framework allows for
surprisingly simple and convenient analyzes without relying on any
heavy machinery.
ホスト:来嶋(B01)
|
6/23 - 26
| COLT 2016 |
| 投稿〆切 : 2016/2/12 |
| Place : New-York City, USA |
6/24 - 25
| コンピュテーション研究会・アルゴリズム研究会(合同) |
| Place : 石川県教育会館 (金沢市) |
| http://www.ieice.org/~comp/
|
6/25 - 28
| PODC 2016 |
| Place : Chicago, Illinois |
6/26 - 7/1
| SIGMOD/PODS 2016 |
| Place : San Francisco, USA |
6/30 - 7/2
| FAW 2016 (The 10th International Frontiers of Algorithmics Workshop) |
| 投稿〆切 : 2016/2/15 |
| Place : 青島(Qingdao), 中国 |
| 投稿締切が2/15に延期されました。
|
7/1 - 2
| [elc] 2016年度第1回領域会議 |
| Place : 東北大学 情報科学研究科棟 |
| 7月1日
13:30~13:45 事務局連絡
13:45~14:45 最終評価に向けて
14:45~15:00 休憩
15:00~15:20 A01班
Click to Continue ...15:20~15:40 A02班
15:40~16:00 A03班
16:00~16:15 休憩
16:15~16:35 B01班
16:35~16:55 B02班
16:55~17:15 B03班
18:30~ 懇親会
7月2日
9:40~10:00 C01班
10:00~10:20 C02班
10:20~10:40 C03班
10:40~11:00 休憩 & ポスターセッション準備
11:00~14:00 ポスターセッション (お昼休みを含む)
(11時~13時 総括班会議)
14:00~14:20 休憩
14:20~15:20 領域の今後
15:20~15:30 事務局連絡
|
7/5 - 8
| SAT 2016 |
| 投稿〆切 : 2016/2/21 |
| Place : Bordeaux, France |
7/5 - 8
| LICS 2016 |
| Place : New York City, USA |
7/9
| [elc] GCT Workshop 2 |
| Place : Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo |
| Date: July 9(SAT), 2016
Time: 13: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: Susumu Ariki(Osaka University)
Title:
Click to Continue ...Burgisser, Ikenmeyer and Panova: No occurrence obstructions in geometric complexity theory,
arXiv:1604.0643(Part 2)
|
7/9 - 15
| IJCAI-16 |
| Place : New York |
7/11 - 13
| SPAA 2016 |
| Place : Asilomar State Beach, California, USA |
7/11 - 15
| ICALP 2016 |
| 投稿〆切 : 2016/2/17 |
| Place : Rome, Italy |
7/19 - 21
| 夏のLAシンポジウム |
| 投稿〆切 : 2016/6/15 |
| Place : 奈良県生駒郡平群町「かんぽの宿 大和平群」 |
7/20 - 22
| ISSAC 2016 |
| 投稿〆切 : 2016/1/15 |
| Place : Waterloo, Ontario, Canada |
7/20 - 22
| TAMC 2016 |
| Place : Xidian University, Xi'an, China. |
7/25
| [elc] ELC Seminar (Dr. Akihiro Kishimoto) |
| Place : Tokyo Inst. of Tech. Ookayama Campus W8 10F Seminar Room W1008 |
| 日時:7月25日(月)16:30-17:30
場所:東京工業大学 大岡山キャンパス 西8号館W棟10F W1008
Speaker:Dr. Akihiro Kishimoto (IBM Research, Ireland)
Title: Efficient AND/OR search algorithms for exact MAP inference
task over graphical models
Click to Continue ...Abstract
Graphical models provide a powerful framework for reasoning with
probabilistic information. Combinatorial maximization, or maximum
a posteriori (MAP) tasks arise in many applications and often can
be efficiently solved by search schemes, especially in the context
of AND/OR search spaces that are sensitive to the underlying
problem structure.
In this talk, I present the power of limited memory best-first
search over AND/OR search spaces, named RBFAOO, which performs
exact MAP inference over graphical models. I also present a
parallelized version of RBFAOO which runs in a shared-memory
environment. I show that RBFAOO is empirically superior to the
current state-of-the-art approaches based on AND/OR search,
especially on very hard problem instances.
ホスト 渡辺治(C01)
watanabe@c.titech.ac.jp
|
7/27 - 29
| 組合せ最適化セミナー (第13回) |
| Place : 京都大学 北部総合教育研究棟 益川ホール |
8/2 - 4
| COCOON 2016 |
| 投稿〆切 : 2015/3/3 |
| Place : Ho Chi Minh City, Vietnam |
| 投稿〆切が3月3日に延期されました。
|
8/10
| [elc] ELC Seminar (Leszek A Gasieniec) |
| Place : 九大伊都キャンパスウェスト2号館7階720 |
| 日時:8月10日(水)10:00-12:00
場所:九州大学 伊都キャンパス ウェスト2号館 7階 720
Speaker:Prof. Leszek Gasieniec (University of Liverpool)
10:00-11:00
Deterministic Majority/Plurality Consensus Protocols
Click to Continue ...Leszek Gasieniec, University of Liverpool
Joint work with D. Hamilton, R. Martin, P. Spirakis, and G. Stachowiak
We study space-optimal population protocols for several variants of the
majority and plurality consensus problems. We start with an important
amendment allowing majority population protocols to report equality if
neither of the original colours dominates the others in the population.
Further we study space efficient plurality consensus protocols in
populations with an arbitrary number C of colours represented by k-bit
labels, where k = log C. In particular we present: (1) an asymptotically
space-optimal O(k)-bit protocol for the absolute majority, i.e., a
protocol which decides whether a single colour dominates all other
colours considered together, (2) an asymptotically space-optimal O(k)-bit
protocol for the relative majority where colours declare their volume
superiority versus other individual colours. The new population protocols
rely on a novel dynamic formulation of the majority problem in which the
colours originally present in the population can be changed during the
communication process by an external force. The new dynamic formulation
of the majority and plurality protocols provides a novel framework for
multi-stage population protocols.
11:00-12:00
Perpetual maintenance of machines with different attendance urgency factors
Leszek Gasieniec, University of Liverpool
Joint work with R. Klasing, Ch. Levcopoulos, A. Lingas, J. Min, and T. Radzik
A garden G is populated by n \leq 1 bamboos b_1, b_2, ..., b_n with the
respective daily growth rates h_1, h_2, ..., h_n. It is assumed that the
initial height of each bamboo is null. The gardener maintaining the garden
is attending bamboos and trimming them to null height according to some
schedule. The Bamboo Garden Trimming (BGT) problem is to design a perpetual
schedule of cuts with the goal of keeping the highest bamboo in the garden
as low as possible. The bamboo metaphor refers to a system of machines which
needs to be serviced with different frequencies by a robot which can service
only one machine a day. The main objective is to design a perpetual schedule
of servicing the machines which minimizes the maximum weighted waiting time.
We consider two variants of the BGT problem.
In the discrete variant the gardener is allowed to trim only one bamboo at
the end of each day and is not allowed to trim bamboos at any other time.
In the continuous variant the bamboos can be cut at any time. However, the
gardener needs time to move some distance across from one bamboo to the next
one and this time is defined by a weighted network of connections. We show a
close relationship between the BGT problem and the classical Pinwheel
scheduling problem, which is known to be intractable and present several
approximation algorithms for both variants of BGT.
ホスト:来嶋(B01)
|
8/14 - 18
| Crypto 2016 |
| 投稿〆切 : 2016/2/9 |
| Place : Santa Barbara, CA, USA |
8/17 - 12/16
| Algorithms and Uncertainty |
| Place : Simons Institute, Berkeley |
8/17 - 12/16
| Logical Structures in Computation |
| Place : Simons Institute, Berkeley |
8/19 - 25
| IJCAI-17 |
| Place : Melbourne, Australia |
8/19 - 25
| IJCAI-17 |
| Place : Melbourne, Australia |
8/22 - 26
| MFCS 2016 |
| 投稿〆切 : 2016/4/25 |
| Place : Krakow, Poland |
8/22 - 26
| ALGO 2016 |
| Place : rhus, Denmark |
| Participating conferences:
ESA, 22-26
ALGOCLOUD, ??--??
ATMOS, ??--??
IPEC, ??--??
WAOA, ??--??
WABI, 22-24
Click to Continue ...
|
8/23
| [elc] ELC seminar (Elad Hazan) |
| 日時:2016年8月23日(火) 14:00-16:00
場所:九州大学 伊都キャンパス ウエスト2号館 3階313号室
主催:新学術領域研究「多面的アプローチの統合による計算限界の解明」
講師:Elad Hazan 氏 (Princeton University)
Click to Continue ...
Title:How to classify from sparse data
Abstract:
For many data sets that are sparse and structured, data reconstruction is computationally hard.
A notable example is the case for media-recommendation data, which is sparse and low-rank.
We consider general model for classification and regression tasks where we have missing data
and assume that the (clean) data resides in a low dimensional subspace.
We give a non-reconstructive learning approach for this setting with provable guarantees.
based on joint work with Tomer Koren, Roi Livni and Yishay Mansour (COLT 2016)
ホスト:瀧本英二,畑埜晃平
|
8/24 - 27
| KDD 2016 |
| Place : San Francisco, California |
8/29 - 9/3
| CSL 2016 |
| Place : Marseille, France |
8/30 - 31
| WAAC 2016 |
| 投稿〆切 : 2016/6/26 |
| Place : Hakodate, Japan |
9/1
| [elc] ELC Seminar on Algorithmic Fun (Erik Demaine & Stefan Langerman 講演会) |
| Place : 電気通信大学 西9号館 3階 AVホール |
| 場所:電気通信大学 西9号館3階AVホール(地図↓)
http://www.uec.ac.jp/about/profile/access/
懇親会情報が末尾にあります。
プログラム:
15:00 -- 16:00: Stefan Langerman (Universite Libre de Bruxells)
Click to Continue ...Title: a covering of the plane with copies of a geometric shape (tiles)
without gaps or overlaps.
Abstract:
An unfolding is obtained by cutting along the surface of a polyhedron through
all its vertices, and opening all the dihedral angles between adjacent faces
to obtain a single flat nonoverlapping geometric shape.
In this hands-on talk, I will explore connections between these two
fascinating concepts, in an attempt to shed some light on the following still
unsolved algorithmic problem:
How easy (or hard) is it to determine if a given geometric shape can tile
the plane?
and the following more artistic and no less fundamental problem:
How to create beautiful (or even ugly) tilings?
---
16:00 -- 17:00: Erik D. Demaine (MIT)
Title: Why Mario is so Hard/Fun
Abstract:
One hypothesis for why humans like to play games and solve puzzles is that
they enjoy the challenge. We can formalize the notion of challenge using
computational complexity theory: if it's challenging for even a computer
to play perfectly, then it's going to be challenging for a human as well.
I will describe several such results, including that Super Mario Bros. and
Mario Kart are PSPACE-complete, which essentially means that you can build
typical computers inside these games. Proving these hardness results is
itself a fun kind of game/puzzle, where we need to construct pieces of
game levels to implement pieces of a computer, like memory and wires.
終了後懇親会を行います。
懇親会参加者は下記URLからお申し込みください(8/30 17:00〆切)。
https://www.al.ics.saitama-u.ac.jp/horiyama/party/2016_0901_fun/
(講演会本体の事前申し込みは不要です。)
オーガナイザー・問合せ先:伊藤大雄(電通大)
http://www.alg.cei.uec.ac.jp/itohiro/index-j.html
|
9/2 - 4
| JCDCG^3 2016 (The 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games) |
| 投稿〆切 : 2016/7/1 |
| Place : 東京理科大学(神楽坂キャンパス) |
| Invited Speakers:
- Erik Demaine (MIT, USA)
- Nikolai Dolbilin (Steklov Institute of Mathematics, Russia)
- Ruy Fabila-Monroy (Cinvestav, Mexico)
- Janos Pach (EPFL, Switzerland and Renyi Institute, Hungary)
- Vera Sacristan (UPC, Spain)
- Ikuro Sato (佐藤郁郎) (Miyagi Cancer Center, Japan)
Click to Continue ...- Tomohiro Tachi (舘知宏) (Univ. Tokyo, Japan)
|
9/4
| [elc] GCT Workshop 3 |
| Place : Komaba Campus @ The University of Tokyo |
| Date: Sept 4(SUN), 2016
Time: 13: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: Francois Le Gall(Kyoto University)
Title:
Click to Continue ...On Matrix Multiplication
|
9/5 - 9
| VLDB 2016 |
| Place : New Delhi, India |
9/5 - 9
| CP 2016 |
| Place : Toulouse, France |
9/6
| コンピュテーション研究会 |
| Place : 富山県立大学 (射水市) |
9/7
| FIT2016イベント企画「劣線形 --- ビッグデータ時代を切り開くキーワード」(COMP研主催) |
| Place : 富山大学(第2イベント会場(A棟A21)) |
| 15:30〜17:30
内容:クレスト「ビッグデータ時代に向けた革新的アルゴリズム基盤 (ABD14)」の活動と成果の紹介。
講演者:
・加藤直樹(関西学院大学):プロジェクト代表者、チームA
・渋谷哲朗(東京大学):チームD
・安田宗樹(山形大学):チームM
・徳山豪(東北大学)
Click to Continue ...・瀧澤重志(大阪市立大学):チームA
・坂本比呂志(九州工業大学):チームD
・大関真之(京都大学):チームM
・司会:宇野裕之(大阪府立大学):チームA
|
9/7 - 9
| RANDOM-APPROX 2016 |
| 投稿〆切 : 2016/4/19 |
| Place : Institut Henri Poincare, Paris, France |
9/7 - 9
| 第十五回情報科学技術フォーラム(FIT) |
| Place : 富山大学 |
9/12
| [elc] ELC Seminar (Pascal Schweitzer) |
| Place : CELC Seminar room (Rm. 404) |
| Time & Date: Sep. 12 (Mon) 2016, 14:00-15:10
Place: CELC Seminar room (Rm. 404)
Speaker: Pascal Schweitzer
Title: Symmetry in Algorithm Design
Abstract:
In discrete mathematics, symmetry is a ubiquitous concept that can both be a blessing and
Click to Continue ...a curse. Symmetry arises naturally in many computational problems and can be used for
search space compression or pruning. However, its presence can also hinder algorithms from
making progress. Both in theory and practice, the algorithmic state-of-the-art techniques
used to detect and exploit symmetry in combinatorial objects are a combination of
algorithmic graph and group theory. With this in mind we take a journey from theory over
implementations to applications.
Highlighting both the theoretical and practical validity of this insight, I will describe
novel applications of symmetry in machine learning and static program analysis as well as
discuss the more complexity theoretic foundation.
(Hosts: Masashi Kiyomi and Yota Otachi)
|
9/20 - 22
| [elc] ELC 秋学校 |
| Place : 湘南国際村 |
| 日程:9月20日午後~22日午前
場所:湘南国際村
http://www.shonan-village.jp/
費用:約 3 万円(2 泊 3 日;20 日,22 日の昼食は別料金)
※学生割引も検討中です.また,学生の方を中心に希望者にはELCから
の旅費支援を行う予定です.
Click to Continue ...募集人員 60 名(シングル 30 室,ツイン 15 室)
※応募多数の場合には枠を増やす可能性もあります。
申込みは参加さは各自で以下のURLからお願いします。
https://www.al.ics.saitama-u.ac.jp/elc/reg/2016_autumn_school/
【内容】(予定です)
テーマ1:機械学習の理論と実際のギャップ解析
・Learning from easy data(仮称)Wouter Koolen (CWI)
・深層学習(仮称)前田 新一(京大)
テーマ2:最適化,プライバシー保護と機械学習
・劣モジュラ最適化と機械学習(仮称)永野 清仁(はこだて未来大)
・プライバシー保護技術(仮称) 佐久間 淳(筑波大)
ホスト 瀧本,畑埜(C03)渡辺(C01)
|
9/23
| アルゴリズム研究会 |
| 投稿〆切 : 2016/7/15 |
| Place : 徳島大学 |
10/5
| [elc] ELC C01 seminar (Dr. Mohit Garg) |
| Place : Ookayama Campus@TITECH, W8E-10F seminar room |
| ELC C01 seminar (Dr. Mohit Garg)
I am pleased to announce that we will have a new PD fellow
Dr. Mohit Garg from Tata Inst. of Fundamental Research as a
member of C01 and jointly A01. He wil give the following talk
at Ookayama campus. Even if you cannot attend this seminar,
please stop by at the ELC office to chat with him.
Click to Continue ...
Host: Osamu Watanabe
Date: Oct. 5th, 2016
Time: 16:40 - 17:40
Place: Tokyo Inst. of Tech, Ookayama Campus, W8E-10F seminar room
Speaker: Mohit Garg
Title: Set membership with non-adaptive bit-probes
Abstract:
We will consider the fundamental trade-off between the
compactness of information representation and the efficiency of
information extraction in the context of the set membership problem.
In the set membership problem, 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
(non-adaptively) probing the bit vector at t places. The bit-probe
complexity s(m,n,t) is the minimum number of bits of storage needed
for such a scheme. Improving on the works of Buhrman, Milterson,
Radhakrishnan and Venkatesh (2002) and Alon and Feige (2009) we
provide better bounds on s(m,n,t) for a range of m, n and t.
In this talk, we will see the existence of non-adaptive schemes for
odd t > = 5 that use O(m^(2/(t-1)) n^(1-2/(t-1))lg (2m)/n) space and
the membership queries are answered by applying the Majority
function to the t bits probed.
In the case of t=3 probes, we will see that Majority does not help;
all schemes that use Majority for answering membership queries and
can represent large sets (n>= lg m) must use \Omega(m) space (a task
that can be accomplished by just a single bit probe using the
characteristic vector representation). In fact, this is true not just
for Majority but also for most three variable boolean functions.
However, for two types of functions, the lower bound that is obtained
is \Omega(\sqrt(mn)).
(Joint work with Jaikumar Radhakrishnan)
|
10/5 - 8
| A Celebration of Mathematics and Computer Science |
| Place : Institute for Advanced Study, Princeton, NJ USA |
| url : https://www.math.ias.edu/avi60 |
| Celebrating Avi Wigderson's 60th Birthday
|
10/9 - 11
| FOCS 2016 |
| 投稿〆切 : 2016/4/5 |
| Place : New Brunswick, New Jersey, USA |
10/16
| [elc] GCT Workshop 4 |
| Place : Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo |
10/19 - 21
| ALT 2016 |
| Place : Bari, Italy |
10/21
| コンピュテーション研究会 |
| Place : 東北大学 (仙台市) |
10/29
| The International Workshop on Innovative Algorithms for Big Data (IABD 2016) |
| Place : Umeda Campus, Kansai University |
11/1 - 3
| TCC 2016-B |
| Place : Beijing, China |
11/14
| [elc] ELC C01 Seminar (Professor T. Pitassi) |
| Place : CELC Seminar Room |
| ELC C01 Seminar
Date: November 14th, 2016, 15:00-16:00
Place: Center for ELC Seminar Room, Tokyo Tech. Tamachi CIC 4F
Title: The Amazing Power of Composition
Speaker: Toniann Pitassi (Unv. of Toronto)
Click to Continue ...
Abstract:
In the last 10 years, hardness escalation theorems have proven to be
very powerful in communication complexity. Such theorems start with
a base function that is "lifted" via function composition
in order to get a new function whose communication complexity
is essentially the same as the much simpler query complexity of the
base function.
Simulation theorems, while often very difficult to prove,
have led to the resolution of many open problems in complexity theory.
In this talk, we will survey recent simulation theorems
for a variety of query complexity/communication complexity models.
We will show how they, in turn, resolve several longstanding open
problems including:
(1) The resolution of the partition number versus communication complexity;
(2) The resolution of Yannakakis' famous Clique versus Independent Set
problem from 1988, and the Alon-Saks-Seymour conjecture in graph theory.
(3) The best known lower bounds for the famous log-rank conjecture of
Lovasz and Saks (FOCS 1988), and
(4) Optimal lower bounds for monotone formula size
Host: Osamu Watanabe, watanabe@is.titech.ac.jp
|
11/14
| [elc] ELC C02 Seminar (Abuzer Yakaryilmaz) |
| Place : 山形大学 地域教育文化学部2号館4階 共通第1実習室 |
| ELC C02 Seminar
11月14日(月)16:30〜17:30
山形大学地域教育文化学部2号館4階 共通第1実習室
講演者: Abuzer Yakaryilmaz氏 (University of Latvia)
Click to Continue ...講演題目: Bit versus qubit
概要:
In this talk, we shortly describe finite automata models and then
basics of probabilistic and quantum computation. After this, we
compare them based on simple problems and show how quantum models can
be more powerful in different computational settings.
|
11/24 - 25
| アルゴリズム研究会 |
| Place : 神戸情報大学院大学 |
12/2
| [elc] ELC Seminar (Prof. Hubie Chen) |
| Place : CELC seminar room |
| Date: Dec. 2nd (Fri) 10:30-11:45
Place: ELC Seminar room (Tokyo Tech. CIC Tamachi)
Speaker: Professor Hubie Chen (Universidad del Pais Vasco)
Title: Proof Complexity Modulo the Polynomial Hierarchy:
Understanding Alternation as a Source of Hardness
Abstract:
Click to Continue ...If one looks at typical proof systems for QBF, such as Q-resolution,
a dilemma is encountered: lower bounds for Q-resolution are implied
immediately by lower bounds for resolution, yet this says nothing
about Q-resolution's ability to cope with quantifier alternation---
and moreover clashes severely with the contemporary QBF view of SAT
as "easy".
In this talk, we will discuss this dilemma and present a possible
way to escape it. In particular, we present and study a framework
in which one can present alternation-based lower bounds on proof
length in proof systems for quantified Boolean formulas. A key notion
in this framework is that of proof system ensemble, which is
(essentially) a sequence of proof systems where, for each, proof
checking can be performed in the polynomial hierarchy. We introduce a
proof system ensemble called relaxing QU-res which is based on the
established proof system QU-resolution. Our main technical results
include an exponential separation of the tree-like and general
versions of relaxing QU-res, and an exponential lower bound for
relaxing QU-res; these are analogs of classical results in
propositional proof complexity.
This talk will focus on a conceptual discussion of the work's
motivation, the framework and the main definitions.
(host: Osamu Watanabe, watanabe@is.titech.ac.jp)
|
12/5 - 6
| APWC on CSE 2016 (3rd Asia-Pacific World Congress on Computing Science 2016) |
| Place : Fiji |
12/5 - 10
| NIPS 2016 |
| Place : Centre Convencions Internacional Barcelona, Barcelona, Spain |
| url : https://nips.cc/Conferences/2016 |
12/12 - 14
| ISAAC 2016 |
| 投稿〆切 : 2016/6/24 |
| Place : Sydney, Australia |
12/13 - 15
| FSTTCS 2016 |
| Place : Chennai Mathematical Institute, Chennai |
12/18
| [elc] GCT Workshop 5 |
| Place : Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo |
| Date: Dec. 18 (SUN) 2016,
Time: 13: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: 徳山 豪 Go Tokuyama (Tohoku University)Title:
Title: "On Erdos distance problem"
Click to Continue ... |
12/21 - 22
| コンピュテーション研究会 |
| Place : 広島大学 |
12/22 - 23
| 情報系 WINTER FESTA |
| Place : 一橋講堂2F 中会議場(所在地:東京都千代田区一ツ橋2-1-2) |