2017年 | |
3/11
| 公開シンポジウム |
| Place : 東京工業大学キャンパス・イノベーションセンター (田町) |
| 場所: 東京工業大学キャンパス・イノベーションセンター
(http://www.cictokyo.jp/access.html)
1階国際会議室
公開シンポジウム(+評価会議)
場所: 東工大田町キャンパスイノベーションセンター
(同上)
Click to Continue ...日時: 3月11日10:00~17:00
10:00-10:10 本領域について 渡辺治 代表
10:10-10:25 A01班
10:25-10:40 A02班
10:40-10:55 A03班
10:55-11:10 <休憩>
11:10-11:25 B01班
11:25-11:40 B02班
11:40-11:55 B03班
11:55-13:30 <お昼休み>
13:30-13:45 C01班
13:45-14:00 C02班
14:00-14:15 C03班
14:15-14:30 <休憩>
14:30-14:40 本領域での新たな取り組み
14:40-14:55 GCTの成果報告
14:55-15:10 スパコンの利用に関する成果報告
15:10-15:20 <休憩>
15:20-15:30 連携研究推進・若手育成の試み
15:30-15:55 若手成果発表1
15:55-16:20 若手成果発表2
16:20-16:45 若手成果発表3
16:45-16:50 閉会の辞
※発表会終了後,評価会議(非公開)を行います
|
3/10
| 2016年度第2回領域会議 |
| Place : 東京工業大学キャンパス・イノベーションセンター (田町) |
| 場所: 東京工業大学キャンパス・イノベーションセンター
(田町駅から徒歩1分 http://www.cictokyo.jp/access.html)
2階多目的ルーム 2
領域会議
13:00-13:05 はじめに
13:05-13:30 公募班(Skip Jordan)の成果報告
Click to Continue ...13:30-13:55 公募班(安永 憲司)の成果報告
13:55-14:20 公募班(泉 泰介)の成果報告
14:20-14:45 公募班(Korman Matias)の成果報告
14:45-15:00 休憩
15:00-15:25 公募班(塩浦 昭義)の成果報告
15:25-15:50 公募班(伊藤 健洋)の成果報告
15:50-16:15 公募班(森前 智行)の成果報告
16:15-16:30 休憩
16:30ー18:00 拡大総括班会議(総括班メンバー,班幹事,公募班メンバー)
|
3/6
| ELC Seminar (Prof. Pekka Orponen) |
| Place : CELC Seminar Room |
| ELC C01 Seminar
Date: March 6th, 4:00 - 5:00
Place: ELC Seminar room (Tokyo Tech CIC, Tamachi, 4F)
Title: Algorithmic design of complex 3D DNA origami structures
Speaker: Pekka Orponen
Click to Continue ... Aalto University, Computer Science
Abstract:
In a recent work (Nature 523:441-444, July 2015), we described a general
methodology and software pipeline for rendering 3D polyhedral mesh
designs in DNA. In this talk, I will first summarise the basic idea of
Paul Rothemund's DNA origami technique which also underlies our
approach, and then proceed to discuss the graph-theoretic concepts and
algorithmic ideas used in extending his technique from 2D patterns to 3D
wireframe mesh structures. The reliability and generality of the
approach is demonstrated by a number of electron microscopy images of
synthesised nanostructures, including a 50-nm rendering of the
widely-used Stanford Bunny model.
Host: Osamu Watanabe (watanabe@is.titech.ac.jp)
|
1/13
| ELCセミナー(Prof. Mitsunori Ogihara) |
| Place : CELC Seminar room |
| title: The Complexity of the Predecessor and Garden-of-Eden Problems
of Synchronous Boolean Finite Dynamical Systems
date: January 13rd, 2017, 11:00-
place: CELC Seminar room
presenter: Mitsunori Ogihara, University of Miami
Click to Continue ...Absrtact: The boolean finite dynamical system is the most stringent form
of dynamical systems in which the system size is fixed, the state of each
object in the system is boolean, and the state update occurs synchornously
for all the objects in the system. The action in one step of a system
can be viewed as a function from a set of some n boolean variables to
itself, and thus, the reversing action as a partial one-to-many function
of that set.
This talk considers the complexity of two problems related to the
reversibility:
(1) The t-Predecessor Problem: given a configuration and t >= 1,
is it possible to reverse the process from the configuration
successfully t times?
(2) The t-Garden-of-Eden Problem: given a configuration and t >= 1,
is it possible to reverse the process from the configuration
successfully t times to arrive at a configure with no inverse?
In this talk, I will present some results to pinpoint the complexity of
these problems for various sets of function basis.
(a) If the available function is pure bit transferring (i.e., assign the
value of one state to another), both problems are in AC^0.
(b) If the available function is the bounded-fan-in OR (or the
bounded-fan-in AND), both problems are in AC^0.
(c) If the available function is the unbounded-fan-in OR (or the
unbounded-fan-in AND), the t-Predecessor Problem is in AC^0 and
the t-Garden-of-Eden Problem is NP-complete for all constants t.
(d) If the functions are chosen from the 2-fan-in OR and the 2-fan-in
AND, the 1-Predecessor Problem is NL-complete and the
1-Garden-of-Eden Problem is NL-hard and is in NP.
(e) If the functions are chosen from the 3-fan-in OR and the 2-fan-in
AND (or from the 2-fan-in OR and the 3-fan-in AND), then the
t-Predecessor Problem is NP-complete and the t-Garden-Of-Eden
Problem is Sigma^p_2-complete.
This is joint wirk with Akinori Kawachi (Kochi U.) and Kei Uchizawa
(Yamagata U.)
|
2016年 | |
12/18
| 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/2
| 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)
|
11/14
| 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/14
| 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
|
10/16
| GCT Workshop 4 |
| Place : Rm 118 Suri-Kenkyuka-tou, Komaba Campus of The University of Tokyo |
10/5
| 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)
|
9/20 - 22
| 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/12
| 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/4
| 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/1
| 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
|
8/23
| 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/10
| 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)
|
7/25
| 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/9
| 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/1 - 2
| 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 事務局連絡
|
6/23
| 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/9
| 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
|
5/29 - 6/1
| CCC 2016 |
| 投稿〆切 : 2015/11/23 |
| Place : Hitotsubashi Hall, Tokyo |
| Pre Event: May 28, Gakushi Kaikan, Tokyo
Post WS: June 2–3, Kyoto Univ.
|
5/22
| 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)
|
4/15
| ELC Seminar (Prof. Venkatesan Guruswami) |
| Place : CELC (Center for ELC), Seminar room (Rm. 404) |
3/29
| 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/27
| 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/22
| 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/17 - 20
| 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/10
| 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
|
2/19
| 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)
|
2/15
| 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)
|
1/24
| 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について
|
2015年 | |
12/17
| 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
|
12/4
| 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/3
| 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/1
| 学習とメカニズムデザイン |
| Place : 九州大学 伊都キャンパス ウエスト1号館 C棟513 |
11/28 - 29
| 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
加藤 直樹
組合せ剛性理論とその応用
|
11/28
| 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/16
| 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/12
| 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/5
| 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)
|
10/30 - 31
| 平成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/
会議室パラッツオ
|
10/13
| 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/7
| 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/4
| 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
|
9/23 - 25
| 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/14 - 17
| 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/8
| 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.
|
8/28
| 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
|
7/30
| 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)
|
7/26
| 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/15
| 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/12 - 15
| Twelfth International Conference on Computability and Complexity in Analysis (CCA 2015) |
| 投稿〆切 : 2015/4/10 |
| Place : 明治大学駿河台キャンパス紫紺館4階(東京都千代田区) |
| 初日(日)の「実数計算の理論と実際」ワークショップは参加無料・登録不要です。
|
7/4
| 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/2
| 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/1
| 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.
|
6/2 - 5
| The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications |
| 投稿〆切 : 2015/2/15 |
| Place : Fukuoka, Japan |
5/29 - 30
| 平成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
|
5/21
| 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
|
4/22
| 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)
|
3/30
| 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班)
|
3/24 - 25
| ELC Workshop on Exponential Lower Bounds for Pivoting Algorithms |
| Place : CELC, Tokyo |
3/12
| サイエンスカフェ@東工大(田町) 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/4
| 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)
|
2/28 - 3/1
| 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
|
2/24
| 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/13 - 14
| 計算理論とビッグデータ |
| 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」
|
1/6
| 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.
|
2014年 | |
12/12
| ELC Seminar (Suguru Tamaki) |
| Place : CELC seminar room (CIC 4F) |
| Date: Dec. 12 (Fri), 2014
Time: 11:00 - 13:00
Place: CELC seminar room (CIC 4F)
Speaker: Suguru Tamaki(A02, Kyoto Univ.)
Title: SAT Algorithms and Average Sensitivity
Abstract:
Click to Continue ...In this talk, I will discuss a connection between satisfiability
algorithm and average sensitivity. For some circuit class C such as
CNF, AC0 and De Morgan formula, there exists a satisfiability
algorithm whose running time is of the form 2^{(1-1/as(C))n}, where
as(C) denotes the average sensitivity of C. Is this connection
coincidence? Does it hold for other circuit classes? I will explain
why we have such connections for CNF, AC0 and De Morgan formula and
would like to encourage people to seek more such connections.
|
12/4
| ELC Seminar (Toshio Suzuki) |
| Place : CELC seminar room |
| Date & Time: December 4th (Thu) 14:00- 15:00
Place: CELC 4F Seminar room
Toshio Suzuki
Tokyo Metropolitan University
*Title:
Equilibrium Points of an AND-OR Tree: under Constraints on Probability
Click to Continue ...
*Abstract:
We study a probability distribution $d$ on the truth assignments to a
uniform binary AND-OR tree. Liu and Tanaka [2007, Inform. Process.
Lett.] showed the following: If $d$ achieves the equilibrium among
independent distributions (ID) then $d$ is an independent identical
distribution (IID).
We show a stronger form of the above result. Given a real number $r$
such that $0 < r < 1$, we consider a constraint that the probability
of the root node having the value 0 is $r$. Our main result is the
following: When we restrict ourselves to IDs satisfying this
constraint, the above result of Liu and Tanaka still holds.
Keys to the solution are two fundamental relationships between
expected cost and probability in an IID on an OR-AND tree.
(1) The ratio of the cost to the probability (of the root having the
value 0) is a decreasing function of the probability $x$ of the leaf.
(2) The ratio of derivative of the cost to the derivative of the
probability is decreasing function of $x$, too.
This work is a collaboration with Yoshinao Niida. Our research is
partially supported by KAKENHI (C) 22540146 and (B) 23340020.
Preprint arXiv:1401.8175
END OF TALK INFO.
|
12/4
| ELC Seminar (Prof. Hubie Chen) |
| Place : CELC |
| Date: Dec. 4th (Thu), 2014
Time: 10:00 - 12:00
Place: CELC seminar room (CIC 4F)
Speaker: Hubie Chen
(Univ. del Pai's Vasco & IKERBASQUE, Basque Foundation for Science)
Click to Continue ...Title:
The Fine Classification of Conjunctive Queries
and Parameterized Logarithmic Space Complexity
Abstract:
Conjunctive queries are the most basic and heavily studied database
queries. The complexity of evaluating a conjunctive query on a
relational database has been, since the landmark work of Chandra and
Merlin (1977), a research subject of persistent and enduring interest.
This evaluation problem is equivalent to a number of well-known
problems, including conjunctive query containment, the homomorphism
problem on relational structures, and the constraint satisfaction
problem. Correspondingly, studies of this problem have come from a wide
variety of perspectives and motivations.
In this work, we perform a fundamental investigation of the complexity
of conjunctive query evaluation from the perspective of parameterized
complexity. We classify sets of conjunctive queries according to the
complexity of this problem. Previous work showed that a set of
conjunctive queries is fixed-parameter tractable precisely when the set
is equivalent to a set of queries having bounded treewidth. We present a
fine classification of query sets up to parameterized logarithmic space
reduction. We show that, in the bounded treewidth regime, there are
three complexity degrees and that the properties that determine the
degree of a query set are bounded pathwidth and bounded tree depth.
After presenting this classification theorem, we engage in a study of
the two higher degrees via logarithmic space machine characterizations
and complete problems. Our work yields a significantly richer
perspective on the complexity of conjunctive queries and, at the same
time, suggests new avenues of research in parameterized complexity.
We will end by discussing recent work that obtains a broad, unifying
perspective on and generalization of the discussed classifications. This
work makes use of a novel variant of the well-known notion of tree
decomposition which we call graph deconstruction. Interestingly, while
the notion of tree decomposition is typically useful for giving positive
algorithmic results, here we use the notion of graph deconstruction,
in a crucial way, to obtain complexity hardness results.
This talk is based on PODS '13 and LICS '14 articles with Moritz Muller.
|
11/29
| ELC Mini-Workshop (B01) |
| Place : 九州大学伊都キャンパス ウェスト2号館7階720 |
| 13:00 - 15:00
岡本吉央:The 5th Cargese Workshop on Combinatorial Optimization の報告
15:30 - 18:00
議論
|
11/28 - 29
| 平成26年度 第2回領域会議 |
| 場所:九州大学伊都キャンパス 稲盛財団記念館 1F 稲盛ホール(会議室A,B)
http://inamori-center.kyushu-u.ac.jp/access/index.html
日時:11月28日12時40分~11時29日12時
Click to Continue ...11月28日
12:40-13:00 事務局連絡
13:00ー13:50 講演 「P vs. NP問題解決へのアプローチを整理しよう」
玉置 卓 (京都大学)
13:50ー14:00 *休憩*
14:00ー14:15 講演 「順序制約下でのオンラインジョブスケジューリングと未解決問題」
畑埜 晃平 (九州大学)
14:15-14:30 講演 「三角形発見問題の量子質問計算量」
Le Gall Francois (東京大学)
14:30ー14:45 講演 「置換上の関数に対する2者間通信複雑性」
泉 泰介 (名古屋工業大学)
14:45ー15:00 講演 「ホログラフィック変換,量子計算,統計力学」
森 立平 (東京工業大学)
15:00-15:10 *休憩* (ポスターセッション準備)
15:10-17:30 ポスターセッション
(16:30-17:30 別室で総括班会議)
19:00- 懇親会
11月29日
9:30-11:50 ポスターセッション
11:50-12:00 事務局連絡
下記から参加申し込みをお願いいたします.締め切りは11/21です.
https://www.al.ics.saitama-u.ac.jp/elc/reg/2014_1128_elc/
懇親会の申し込みは、会場の予約の関係で、定員60名に達しましたら〆切らせていただきます。
|
11/21
| ELC 勉強会(Spectral Boot Camp. 報告 #1) |
| Place : ELC Seminar room |
| Date & Time: Nov. 21 (Fri), 15:45 -- 18:00
Simons Institute での Spectral Boot Camp に参加した山口君(東工大,
博士課程)に,その一部を以下のように報告してもらいます.勉強会ですので
お気軽にご参加ください.ポリコム参加の歓迎です.
ホスト:渡辺治
Click to Continue ...
====
タイトル:
A nearly linear time solver for linear equations in Laplacian matrices
Preconditioning via spectral graph sparsification
内容:
Laplacian行列で記述される線型方程式系を、非零要素数のほぼ線型時間
で近似的に解くアルゴリズムを説明する。解法は前処理付き共役勾配法を用い、
前処理行列を対応するグラフの疎化を用いて構成する。
以上
|
11/6 - 10
| ELC Mini-Workshop on Boolean Functions |
| Place : Center for ELC, Tokyo Institute of Technology (Tamachi), Tokyo |
| [Schedule]
11/6 (Thu) Room #501 A-B (5F)
14:00-15:00 Kenya Ueno (B02, Kyoto U.), Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
15:30-17:00 open problems & free discussion
11/7 (Fri) Room #501 A-B (5F)
10:00-11:00 Jun Tarui (A03, U. Electro-Communications), Depth-First Search using O(n) bits
Click to Continue ...11:15-12:15 Suguru Tamaki (A02, Kyoto U.), On the complexity of randomness extractors
14:00-15:00 Kazuhisa Makino (A01, Kyoto U.), Posimodular function optimization
15:30-17:00 open problems & free discussion
11/8 (Sat) International Conference Room (1F)
10:00-11:00 Ramamohan Paturi (invited, UC San Diego), Fine-grained Complexity and Satisfiability
11:15-11:55 Kazuyuki Amano (B02, Gunma U.), Graph Partition and Communication Complexity
14:00-15:00 Osamu Watanabe (PI, Tokyo Institute of Technology), A Short Implicant of a CNF Formula with Many Satisfying Assignments
15:30-17:00 open problems & free discussion
18:00- dinner
11/9 (Sun) International Conference Room (1F)
10:00-11:00 Stefan Schneider (invited, UC San Diego), A Satisfiability Algorithm for Depth Two Threshold Circuits and 0-1 Integer Linear Programming
11:15-11:45 Kei Uchizawa (C03, Yamagata U.), Lower Bounds for Linear Decision Trees with Bounded Weights
14:00-15:00 Oliver Kullmann (invited, Swansea U.), Good SAT translations: approaches via resolution and monotone circuit bounds
15:30-17:00 open problems & free discussion
11/10 (Mon) Room #501 A-B (5F)
10:00-12:00 open problems & free discussion
[Talk Slides and Abstracts]
- Kenya Ueno, Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/ueno.pdf
In this talk, we will present O(1.415^n)-time and O(1.190^n)-space
exact algorithms for 0-1 integer programs where constraints are linear
equalities and coefficients are arbitrary real numbers. Our manuscript
on these results (arXiv:1405.6851) will be renewed before the
workshop. We will also discuss ongoing work on computational
experiments by using random 0-1 integer programs.
- Jun Tarui, Depth-First Search using O(n) bits
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/tarui.pdf
- Suguru Tamaki, On the complexity of randomness extractors
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/tamaki.pdf
Randomness extractors for structured sources such as bit-fixing and
affine sources are useful in proving circuit lower bounds. One reason
is that they inherit the property of being extractors after
restriction. In this talk I will survey known results on the
complexity of such extractors, especially focusing on lower bounds
obtained by restriction method. Also, I will present some open
questions related to this topic.
- Ramamohan Paturi, Fine-grained Complexity and Satisfiability
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/paturi.pdf
- Stefan Schneider, A Satisfiability Algorithm for Depth Two Threshold Circuits and 0-1 Integer Linear Programming
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/schneider.pdf
- Kei Uchizawa, Lower Bounds for Linear Decision Trees with Bounded Weights
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/uchizawa.pdf
We consider a linear decision tree $T$ such that the sum of the
absolute values of the integer weights of a linear threshold function
at each internal node is at most $w$, and prove that if $T$ has size
(i.e., the number of leave) $s$, rank $r$, and computes a Boolean
function $f$, then there exists a depth-2 threshold circuit that
computes $f$ and has $s(2w+1)^{r}$ threshold gates with weight at most
$(2w+1)^{r+1}$ in the bottom level. Combining a known lower bound on
size of depth-2 threshold circuits, we can obtain a $2^{\Omega (n/\logw)}$
lower bound on the size of linear decision trees computing
Inner-Product function modulo 2, which improves on the previous bound
$2^{\sqrt{n}}$ if $w=2^{o(\sqrt{n})}$.
- Oliver Kullmann, Good SAT translations: approaches via resolution and monotone circuit bounds
I wish to give an overview on our work regarding aspects of a theory of
good SAT translations ("encodings"). The main tools are various "hardness
measures" for conjunctive normal forms, based on certain stable forms of
resolution complexity, extended to satisfiable CNFs via a worst-case
approach. The basic dimensions are:
1. tree-resolution versus full-resolution
2. absolute versus relative hardness (taking auxiliary variables into
account or not).
Relative hardness is closely related to monotone circuit complexity,
while the stronger approach, absolute hardness, needs new tools.
In my talk I will discuss the basic definitions, and give an overview
on our results.
[Organizers]
Kazuhisa Makino (A01, Kyoto U.)
Kazuhisa Seto (A02, Seikei U.)
Suguru Tamaki (A02, Kyoto U.)
|
9/24 - 26
| ELC 計算量理論の秋学校 |
| Place : 鬼怒川温泉ホテル |
| 日時: 9/24(水)14時~9/26(金)12時頃
(初日受付は 13:30~を予定)
場所:鬼怒川温泉ホテル
http://www.kinugawaonsenhotel.com/
Click to Continue ...プログラム:
9月24日(水) 14:00~ 9月26日(金) 12:00頃
(1時間程度x2コマ)x4人+自由討論
プログラム詳細:
http://www.al.ics.saitama-u.ac.jp/elc/blog/20140924_0926/
講演者(順不同):
・伊藤大雄先生(電通大)
「定数時間アルゴリズム」
・岡本吉央先生(電通大)
「数理計画法に基づくアルゴリズム設計方法論の限界」
・吉田悠一先生(NII)
「劣モジュラ性と線形時間FPTアルゴリズム」
・本多淳也先生(東大)
「多腕バンディット問題と決定的・確率的アルゴリズム」
※なお,自由討論で話題提供できる方を募集しています.
「ご自身または他人の面白い結果」や「未解決問題や研究課題」
などがございましたら,ご一報いただけますと幸いです.
宿泊代等の費用:
宿泊(24日夜,25日夜)と食事(24日夜,25日朝夜,26日朝)の実費
で 25000~30000円程度です.詳細は部屋に応じて異なるので
別途個別にご案内します.
問い合わせ:
畑埜 晃平(九大)
hatano (a)inf.kyushu-u.ac.jp ((a)を@に変えて下さい)
|
9/22
| ELC Seminar (Nir Ailon) |
| Place : 九州大学伊都キャンパスウエスト2号館10階1019号室 |
| 日時:9月22日(月)15:00-16:00
Nir Ailon (Technion)
Lower Bound for Fourier Transform in the Well-Conditioned Linear Model
(Or: If You Want a Faster Fourier Transform You'd Need to Sacrifice Accuracy)
Click to Continue ...
The Fourier Transform is one of the most important linear transformations
used in science and technology. Cooley and Tukey's Fast Fourier Transform
(FFT) from 1964 is a method for computing this transformation in time
O(n log n). In spite of its importance, no nontrivial (super-linear)
lower bounds were known without making very strong assumptions.
Morgenstern's result from 1974 provides an Ω(n log n) lower bound for
the *unnormalized* Fourier Transform (of determinant n^{n/2}),
assuming only numbers with bounded constant modulus are used.
[Ailon 2013] shows an Ω(n log n) bound for the *normalized* Fourier
Transform (of determinant 1) assuming only unitary operations on two
coordinates are allowed. In this work we show that, as long as the
computation is well conditioned, *any scaling* of the Fourier transform
requires Ω((n log n)/R) operations, where R is the condition number.
This means that, on a given machine, a faster Fourier transform is less
accurate. The main new technique is definition of a matrix entropy
function, using "quasi-probabilities" (which can be negative or >1).
I will discuss the result and present some open questions.
問合せ先:瀧本(C03)
|
9/19
| ELC Mini-Workshop (C01) |
| Place : CELC |
| Date & time: September 19, 15:10 - 17:30
Place: Center for ELC Seminar Room (4F, 404)
Spearers: Dr. T. Kawamoto (Tokyo Inst. of Tech.)
Dr. M. Vehekapera (Aalto Univ., Finland)
15:10 - opening
Click to Continue ...
15:15 - 16:15
Speaker: Dr. Tatsuro Kawamoto
(Tokyo Institute of Technology, JSPS Research Fellow)
Title: Detectability limit of a spectral clustering method
Abstract:
A method of spectral clustering is one of the traditional tools for
extracting community structure out of graphs, which makes use of
eigenvectors which correspond to small eigenvalues of a graph
Laplacian. In general, estimating the validity of a community
detection method is an important problem for practical use and has
been gathering significant attention. In order to estimate the
situation where a method of spectral clustering is valid, we consider
a pair of loosely connected random graphs and solve its second
smallest eigenvalue/eigenvector problem using the replica method;
it gives the limit of the coupling strength between clusters,
below which the method correctly detects the clusters.
16:30 - 17:30
Speaker: Dr. Mikko Vehekapera (Aalto University, Finland)
Title: Signal recovery and denoising for sparse linear systems
Abstract:
Several problems in engineering can be thought as an instance of
signal recovery in linear observation systems. The current
state-of-the-art scheme for inference given a sparse source is
so-called approximate message passing (AMP) that can approach the
Bayesian optimal performance with polynomial complexity under certain
conditions. Recently it has been shown, however, that the basic AMP
algorithm is not able to provide optimal performance if the coupling
matrix is not constructed from independent entries. In this talk we
review some of the recent results regarding iterative signal recovery
methods for sparse linear systems - including the case when the
measurement matrix has specific row-orthogonal structure.
END
|
9/17
| ELC Seminar (David Witmer) |
| Place : ELC Center Seminar Room |
| Date and Time: Sept. 17, 4pm-5pm
Place: Center for ELC (Seminar Room, 4th floor)
Speaker: David Witmer (CMU, Doctoral student)
Title: Goldreich's PRG: Evidence for near-optimal polynomial stretch
Abstract:
Goldreich proposed a simple, highly parallelizable pseudorandom generator
Click to Continue ...(PRG) construction whose security is related to the hardness of constraint
satisfaction problems. We give two types of evidence that a particular
instantiation of this generator that stretches n bits to n^1.499 bits is
secure. Specifically, we show that this PRG is secure against linear tests
and attacks based on the Lasserre hierarchy. This amount of stretch is
nearly optimal, as there is an algorithm that distinguishes the output from
random if the stretch is O(n^1.5 log(n)). Previous work had only shown
that Goldreich's generator with stretch up to n^1.249 was secure against
linear tests.
Joint work with Ryan O'Donnell
Host: Osamu Watanabe (watanabe(at)is.titech.ac.jp)
|
9/16
| ELC Workshop on Learning Theory and Complexity (C03) |
| Place : 京都大学 |
9/9 - 12
| ELC暗号理論秋学校 |
| Place : 河口湖クラブセントヴィレッヂ |
| 2014年度ELC暗号理論秋学校
日程: 2014年9月9日(火) 13:00 から 12日(金) 12:00 まで
場所: 河口湖クラブセントビレッヂ (http://www.stvillage.com/)
講師: 松田 隆宏 (産総研),矢内 直人 (阪大),安永 憲司 (金沢大),河内 亮周 (東工大) (敬称略)
<講義内容>
Click to Continue ...講師: 松田隆宏
テーマ: 公開鍵暗号
1. 公開鍵暗号の構成に関するクラシックな結果の紹介 (Naor-Yung、Fujisaki-Okamoto、ハイブリッド暗号、その他もっと最近の成果など)
2. 公開鍵暗号の安全性定義の間の関係 (A安全であればB安全かどうか、その反例を示すにはどうするか、など)
講師: 矢内直人
テーマ: 電子署名
1. 署名に関する代表的な結果(RSA、DSA、BLS 署名、Boneh-Boyen, Waters、Naor 変換)
2. 署名の安全性証明手法(ランダムオラクルのみ、Coron のテクニック、Katz-Wang など)
3. 署名を利用したプロトコル仕様に対する安全性証明(S-BGP、TLS handshake など)
講師: 安永 憲司
テーマ: ゲーム理論と現代暗号
1. ゲーム理論の考え方(ゲーム的状況、戦略型ゲーム、展開型ゲーム、Nash均衡、相関均衡、部
分ゲーム完全均衡など)
2. ゲーム理論と暗号のつながり(秘密分散、安全性とNash均衡の関係)
講師: 河内 亮周
テーマ: 誤り訂正符号と暗号理論の基礎
1. 誤り訂正符号と暗号プリミティブの関係
2. 具体的な符号の暗号理論への応用
連絡先: 河内 亮周(東工大)
|
8/18
| ELC Workshop on Quantum Complexity Theory |
| Place : The University of Tokyo |
| This satellite workshop of AQIS 2014 will be held at the University of Tokyo,
in the center of Tokyo, on August 18, 2014. The AQIS conference itself,
held in Kyoto, will start two days later (tutorials on August 20, main
conference from August 21), leaving plenty of time for participants
to move from Tokyo to Kyoto after the end of the workshop.
This one-day workshop will be devoted to quantum complexity theory,
Click to Continue ...with a scientific program consisting of invited talks and one "rump session"
(one session for very short, and possibly informal, contributed talks).
Invited speakers:
Andr CHAILLOUX (INRIA)
Richard CLEVE (Waterloo University / IQC)
Tomoyuki MORIMAE (Gunma University)
Harumichi NISHIMURA (Nagoya University)
Yasuhiro TAKAHASHI (NTT)
Thomas VIDICK (Caltech)
|
8/6
| ELC Seminar (Dr. Boaz Barak) |
| Place : Center for ELC @ CIC Tamachi |
| Speaker: Dr. Boaz Barak(Microsoft Research)
Time & date: 4:00pm - 5:30pm, Aug 6th
Place: CELC seminar room (404, 4F)
TITLE: Sum of Squares Proofs and the Quest towards Optimal Algorithms
ABSTRACT:
I will survey recent results and questions regarding the Sum-of-quares (SOS) method for
Click to Continue ...solving polynomial equations. This method, which is related to classical mathematical questions,
has been studied in several scientific disciplines, including real algebraic geometry,
proof complexity, control theory, and mathematical programming, and has found applications
in fields as diverse as quantum information theory, formal erification, game theory and many others.
We discuss some new perspectives on the SOS method, giving different interpretations
and applications of it, and raising the question whether it could yield a generic *optimal* algorithm
for broad domains of computational problems.
We will also discuss the fascinating relation between the SOS method and
Khot's Unique Games Conjecture, which is a tantalizing conjecture in computational complexity
that has the potential to shed light on the complexity of a great many problems.
The talk will assume no background on the SOS method or the unique games conjecture.
It is partially based on joint works with Jonathan Kelner and David Steurer.
|
7/26 - 27
| ELC Mini-Workshop (B01, C03) |
| Place : 九州大学伊都キャンパス数理学研究教育棟中セミナー室7 |
| 7/26
13:00 -- 14:00
畑埜晃平:順序にまつわるエトセトラ
14:15 -- 15:15
篠原歩:文字列に含まれる連の最大数と指数和について(仮)
15:30 -- 16:30
加藤直樹:minimax regret sink location problems in dynamic networks
Click to Continue ...16:30 -- 17:00
議論
7/27
10:00 -- 11:00
正代隆義:文脈決定文脈自由グラフ言語の質問学習
11:15 -- 12:15
内澤啓:拡散競争ゲームについて
13:30 -- 14:30
神山直之:計算量理論的視点から生じるマッチングに関する問題
14:30 -- 15:00
議論
多班の方で参加を希望されるかたは神山までメールをお送りください.
|
7/16
| ELC Seminar on Theoretical Computer Science in UEC |
| Place : Room 302 (3F), West-9 BLDG, The University of Electro-Communications(電気通信大学, 西9号館, 3F 302) |
| ELC Seminar on Theoretical Computer Science in UEC
We are going to have a seminar on Theoretical Computer Science,
which consists of a talk by
Professor Wolfgang Bein (University of Nevada, Las Vegas).
We hope you all participate.
Click to Continue ...--
Time and Date: 14:000--15:30, July 16 (Wed), 2014.
Place: Room 302, 3F, West-9 BLDG, The University of Electro-Communications
http://www.uec.ac.jp/eng/about/access/
Speaker: Wolfgang Bein (University of Nevada, Las Vegas)
Title: Knowledge States: A Tool in Randomized Online Algorithms
Abstract:
We introduce the concept of knowledge states; many well-known algorithms can
be viewed as knowledge state algorithms. The knowledge state approach can
be used to to construct competitive randomized online algorithms and study
the tradeoff between competitiveness and memory.
We give new results for the two server problem and the paging problem.
We present a knowledge state algorithm for the two server problem over
Cross Polytope Spaces with a competitive ratio of 19/12, and show that
it is optimal against the oblivious adversary.
Regarding the paging problem, Borodin and El-Yaniv had listed as an
open question whether there exists an H_k-competitive randomized
algorithm which requires O(k) memory for k-paging. We have answered
this question in the affirmative using knowledge state techniques.
Contact to: ITO Hiro (UEC, Japan)
http://www.alg.cei.uec.ac.jp/itohiro/
|
6/9
| Workshop on Extension Complexity: An Update and Future Directions |
| Place : 京都大学百周年記念館 |
| SoCG 2014(http://www.dais.is.tohoku.ac.jp/~socg2014/#home)
のWorkshopとして開催します.
奮ってご参加ください.
Organizers: David Avis and Naoki Katoh
Invited Speakers:
Click to Continue ...Hans Tiwary (Charles University)
Extended formulations: Introduction to lower bounding techniques
Kanstantsin Pashkovich (Université libre de Bruxelles)
Extended formulations: Lower bounds and matching polytope
Yoshio Okamoto (University of Electro-Communications)
Extended formulations for sparsity matroids
David Avis (Kyoto and McGill)
Polynomial size matching polytopes
文責 加藤直樹(京都大学)
|
6/5
| ELC Seminar on Theoretical Computer Science in UEC |
| Place : Room 302 (3F), West-9 BLDG, The University of Electro-Communications(電気通信大学, 西9号館, 3F 302) |
| ELC Seminar on Theoretical Computer Science in UEC
We are going to have a seminar on Theoretical Computer Science,
which consists of a talk by a distinguished researcher
Professor Mike Paterson (Univ. Warwick, UK).
We hope you all participate.
Click to Continue ...--
Time and Date: 14:000--15:00, June 5 (Thur), 2014.
Place: Room 302, 3F, West-9 BLDG, The University of Electro-Communications
http://www.uec.ac.jp/eng/about/access/
Speaker: Mike Paterson (DIMAP and Computer Science, Univ. Warwick, UK)
Title: Geometric dissection problems
Abstract:
I shall introduce several dissection problems, which involve cutting and
rearranging simple geometric shapes. In particular I will concentrate on
recent results which involve packing sectors of a circular disc inside a
smaller circle, and explain in detail some of the constructions and
techniques needed. Some very open problems remain!
Contact to: ITO Hiro (UEC, Japan)
http://www.alg.cei.uec.ac.jp/itohiro/
|
6/4 - 6
| Japanese-Swiss Workshop on Combinatorics and Computational Geometry |
| Place : 東京 |
5/29
| ELC Seminar ( Dr. Periklis Papakonstantinou) |
| Place : CELC |
| Speaker: Periklis A. Papakonstantinou (IIIS Tsinghua University)
Time & date: 4:00pm, May 29
Place: CELC seminar room (404, 4F)
Title: Cryptography with Streaming Algorithms
Abstract: We put forth the question of whether cryptography is feasible using streaming devices. We
give constructions and prove lower bounds. In streaming cryptography (not to be confused
Click to Continue ...with stream-ciphers) everything|the keys, the messages, and the seeds|are huge compared
to the internal memory of the device. These streaming algorithms have small internal memory
size and make a constant number of passes over big data maintained in a constant number of
read/write external tapes. Typically, the internal memory size is O(log n) and we use 2 external
tapes; whereas 1 tape is provably insucient. In this setting we cannot compute instances of
popular intractability assumptions. Nevertheless, we base cryptography on these assumptions
by employing non-black-box techniques, and study its limitations.
We introduce new techniques to obtain unconditional lower bounds showing that no super-
linear stretch pseudorandom generator exists, and no Public Key Encryption (PKE) exists with
private-keys of size sub-linear in the plaintext length.
For possibility results, assuming the existence of one-way functions computable in NC1|e.g.
factoring, lattice assumptions|we obtain streaming algorithms computing one-way functions
and pseudorandom generators. Given the Learning With Errors (LWE) assumption we construct
PKE where both the encryption and decryption are streaming algorithms. The starting point
of our work is the groundbreaking work of Applebaum-Ishai-Kushilevitz on Cryptography in
NC0. In the end, our developments are technically orthogonal to their work; e.g. there is a PKE
where the decryption is a streaming algorithm, whereas no PKE decryption can be in NC0.
|
5/23 - 24
| 平成26年度 第1回領域会議 |
| Place : CELC |
| 2014年度第一回領域会議
場所: 東京工業大学キャンパスイノベーションセンター
http://www.cictokyo.jp/access.html
日時: 5月23日,24日 領域会議: 1階 国際会議室
総括班会議: 4階 404号室
ポスターセッション: 1階 国際会議室
Click to Continue ...
5月23日
13:00-13:10 事務局連絡
13:10-13:40 公募班1
13:40-14:10 公募班2
14:10-14:30 休憩
14:30-15:00 公募班3
15:00-15:30 公募班4
15:30-15:50 休憩
15:50-16:30 本年度の計画について
16:30-18:00 ポスターセッション
5月24日
9:30-11:00 ポスターセッション
11:00-11:30 公募班5
11:30-12:00 公募班6
12:00-13:30 お昼休み 総括班会議
13:30-14:00 公募班7
14:00-14:30 公募班8
14:30-15:00 公募班9
15:00-15:20 休憩
15:20-16:20 中間評価に向けて
16:20-16:30 事務局連絡
公募班1: 形式論理のプロパティー検査と発見による計算限界の解析
Skip Jordan (北海道大学)
公募班2: 離散最適化に対する固定パラメータアルゴリズム設計によるパラメータ化計算複雑さ解明
宇野 裕之 (大阪府立大学)
公募班3: 計算構造制限下での暗号技術の限界解明
安永 憲司 (金沢大学)
公募班4: 分散計算複雑性の理論:最悪時評価を超えて
泉 泰介 (名古屋工業大学)
公募班5: 離散凸解析に基づく劣モジュラ最適化問題の計算限界の解明
塩浦 昭義 (東北大学)
公募班6: 線形相補性問題の計算限界への挑戦
森山 園子 (東北大学)
公募班7: 列挙的なアプローチによる計算限界解明
山中 克久 (岩手大学)
公募班8: 解空間の直径に基づく計算限界解析アプローチの構築
伊藤 健洋 (東北大学)
公募班9: 統計力学的アプローチによる機械学習の計算限界解明アルゴリズム開発
永田 賢二 (東京大学)
|
5/8
| ELC Seminar (Dr. Brendan Juba) |
| Place : CELC |
| Speaker: Dr. Brendan Juba(Harvard Univ.)
Time and date: 4:00pm - 5:30pm, May 8
Place: CELC seminar room (404, 4F)
Title: Knowledge Farming
Abstract: A variety of problems can be cast as "data mining with a
goal." I propose a framework for solving such problems by
Click to Continue ...integrating machine learning into logical reasoning problems.
In machine learning, we may obtain a new formula satisfied by data.
In logical reasoning, we seek a proof that derives a query proposition
from background knowledge, given as additional input propositions. In
the combined approach, we seek a proof that derives a query from the
background knowledge and any propositions that can be learned from
the input data. The crucial advantage of this integrated approach is
that the query and background knowledge serve as context for
learning. This context guides an algorithm to identify the relevant
propositions satisfied by the data. I will show how these algorithms
can possess desirable properties, such as tolerance to adversarial
noise. Moreover, for some applications, such integrated algorithms
provide the first algorithms known to be efficient.
|
3/26
| ELC Seminar (Akimasa Miyake) |
| Place : CELC |
| Speaker: Prof. Akimasa Miyake (Univ. of New Mexico)
Time & Date: 3:00pm, March 26
Place: CELC seminar room (404, 4F)
Title: Quantum computation and simulation, and classical simulation thereof
Abstract: Potential quantum advantage in computation and simulation is of great
interest to scientists, while for now its evidences are rather
Click to Continue ...scattered as quantum algorithms solving specific problems. In this
talk, I would like to advocate such an approach that quantum
entanglement is indeed a way to characterize generally the complexity
of quantum computation and simulation, despite some (old and new)
misconceptions about its roles. I highlight a restricted set of
quantum logical gate operations related to non-interacting fermionic
time evolutions, called quantum matchgates, in order to observe a
subtle difference between quantum computation and classical simulation
thereof in this setting. It is demonstrated that the computational
complexity of quantum matchgate circuits is evaluated by
"concentrating necessary entanglement and compressing optimally the
width of quantum circuits."
Contact: Akinori Kawachi
|
3/19
| COMP-ELC 学生シンポジウム |
| Place : 新潟大学 |
| 電子情報通信学会 総合大会 (3/18-21) での企画です
|
3/15
| ELC Mini-Workshop (B01) |
| Place : 東大本郷キャンパス工学部6号館2階235号室 |
| プログラム:
10:00 -- 11:00 : The matching polytope has exponential extension complexity の解説(神山)
11:00 -- 12:00 : Garph procduct の解説(来嶋)
13:00 -- 15:00 : 議論
15:30 -- 17:00 : 議論
|
3/14
| 新学術領域「計算限界解明」シンポジウム |
| Place : 東京工業大学 田町キャンパス |
2/10
| SODA 2014 参加報告会 |
| Place : 東京工業大学キャンパス・イノベーションセンター 2階 多目的ルーム |
| 日時 2月10日 9:40~18:00
場所 〒108-0023 東京都港区芝浦3-3-6
東京工業大学キャンパス・イノベーションセンター
2階 多目的ルーム
(http://www.cictokyo.jp/index.html)
9:40-10:40:大舘 陽太 (JAIST)
Click to Continue ...担当論文:Large induced subgraphs via triangulations and CMSO
F. Fomin, I. Todinca, Y. Villanger
11:00-12:00:安藤 映 (崇城大学)
担当論文:Smoothed Analysis of Local Search for the Maximum-Cut
Problem
M. Etscheid, H. Roglin
13:00-14:00: 小長谷 松雄 (JAIST)
担当論文: Selection and Sorting in the "Resotre" Model
T. M. Chan, J. I. Munro, V. Raman
14:20-15:20:澄田 範奈 (東京大学)
担当論文: Dantzig's pivoting rule for shortest paths, deterministic MDPs,
and minimum cost to time ratio cycles
T. D. Hansen, H. Kaplan, U. Zwick
15:40-16:40: 木村 慧 (東京大学)
担当論文: Space complexity of list H-coloring: a dichotomy
L. Egri, P. Hell, B. Larose, A. Rafiey
17:00-18:00: 桂 敬史 (東北大学)
担当論文: Bicriteria data compression
A. Farruggia, P. Ferragina, A. Frangioni, R. Venturini
|
1/25 - 26
| ELC Workshop on Inapproximability |
| Place : University of Electro-Communications, Japan |
| Tentative Program
January 25 (Sat)
12:00-13:00 Registration
13:05-13:15 Opening Address
13:15-14:00 Nisheete Vishnoi (Microsoft Research India)
14:15-15:00 Samuel Fiorini (Universite libre de Bruxelles)
Click to Continue ...15:15-16:00 Danupon Nanongkai (Nanyang Technological University)
16:15-17:00 Kenya Ueno (Kyoto University)
January 26 (Sun)
9:30-10:15 Michael Lampis (Kyoto University)
10:30-11:15 Sevag Gharibian (University of California, Berkeley)
11:30-12:15 Kiyohito Nagano (Future University Hakodate)
12:15 Closing
Afternoon: Possible excursion to Jindaiji
and further discussion
Organizers
Satoru Iwata (University of Tokyo)
Naoyuki Kamiyama (Kyushu University)
Naoki Katoh (Kyoto University)
Shuji Kijima (Kyushu University)
Yoshio Okamoto (University of Electro-Communications)
|
2013年 | |
12/23 - 24
| FOCS 報告会 |
| Place : 東京大学本郷キャンパス 工学部6号館3階セミナー室AD |
| キャンパス マップ
http://www.u-tokyo.ac.jp/campusmap/cam01_04_07_j.html
12月23日の夕方に,懇親会を行います.
参加申込は,下記のページからお願いします.
https://www.al.ics.saitama-u.ac.jp/elc/reg/2013_1223_focs_report/
Click to Continue ...
プログラム
12月23日
12:20-13:00 フリーディスカッション
13:00-14:10 山内 由紀子 (九州大学)
担当論文:Tight Bounds for Set Disjointness in the Message Passing Model
M. Braverman, F. Ellen, R. Oshman, T. Pitassi and V. Vaikuntanathan
14:30-15:40 森 立平 (東京工業大学)
担当論文: Approximate Constraint Satisfaction Requires Large LP Relaxations
S.O. Chan, J.R. Lee, P. Raghavendra and D. Steurer
16:00-17:10 斎藤 惇 (群馬大学)
担当論文:A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
R. Impagliazzo, R. Paturi, and S. Schneider
12月24日
10:30-11:40 長尾 篤樹 (京都大学)
担当論文: Average Case Lower Bounds for Monotone Switching Networks
Y. Filmus, T. Pitassi, R. Robere and S.A. Cook
11:40-13:00 フリーディスカッション
13:00-14:10 河瀬 康志 (東京大学)
担当論文: The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant
V. Bilò, M. Flammini and L. Moscardelli
14:30-15:40 山口 裕生 (東京工業大学)
担当論文: Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
A. Marcus, D.A. Spielman and N. Srivastava
16:00-17:10 中川 航太郎 (東京工業大学)
担当論文:Towards a Better Approximation for Sparsest Cut?
S. Arora, R. Ge and A.K. Sinop
#なお,担当論文は変更する可能性があります.
|
12/20
| 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 沖縄産業支援センター |
12/17
| ELC Seminar (Dr. Siu-On Chan) |
| Place : CELC Seminar Room (4F) |
| Date: 2003.12.17, 13:00-14:00
Place: CELC Seminar Room, Tokyo Tech. Tamachi 4F
http://www.al.ics.saitama-u.ac.jp/elc/en/celc/
Title: Approximation Resistance from Pairwise Independent Subgroups
by: Siu-On Chan (MSR New England)
Click to Continue ...Abstract:
We show optimal (up to a constant factor) NP-hardness for maximum
constraint satisfaction problem with k variables per constraint
(Max-k-CSP), whenever k is larger than the domain size. This follows
from our main result concerning CSPs given by a predicate: a CSP is
approximationresistant if its predicate contains a subgroup that is
balanced pairwise independent. Our main result is analogous to Austrin
and Mossel’s, bypassing their Unique-Games Conjecture assumption
whenever the predicate is an abelian subgroup.
Our main ingredient is a new gap-amplification technique inspired by
XOR-lemmas. Using this technique, we also improve the NP-hardness of
approximating Independent-Set on bounded-degree graphs, Almost-Coloring,
Two-Prover-One-Round-Game, and various other problems.
|
12/6
| ELC Mini-Workshop on Sublinear-Time Algorithms (A02) |
| Place : Room 2208 (22th floor), The National Institute of Informatics (国立情報学研究所). |
| 末尾に懇親会情報があります。
Program:
*** Note ***: Eric Blais (Carnegie Mellon University)'s talk was canceled
due to his emergency surgery. (It's not severe. He is recovering favorably.)
10:55-11:00: Opening: Hiro Ito (University of Electro-Communications)
11:00--11:30: Francois Le Gall (University of Tokyo)
- Sublinear Quantum Algorithms for Graph-theoretic Properties
Click to Continue ...(Lunch Break: 90 min.)
13:00--14:00: Invited: Comandur Seshadhri (Princeton University)
- Monotonicity and Lipschitz testing on hypergrids: alternating paths
to the rescue
14:00--14:30: Mitsuru Kusumoto (Kyoto University & ERATO)
- Testing Forest-Isomorphism in the Adjacency List Model
(Break: 20 min.)
14:50--15:20: Skip Jordan (Hokkaido University & ERATO)
- Property Testing, Logic and Complexity
15:20--15:50: Takahiro Ueda (Kyoto University)
- Sublinear-Time Cake-Cutting Algorithms
(Break: 20 min.)
16:10--16:40: Yuichi Yoshida (NII & Preferred Infrastructure)
- A Characterization of Locally Testable Affine-Invariant Properties
via Decomposition Theorems
16:40--17:10: Hiro Ito (University of Electro-Communications)
- A Paradigm Shift Toward The Big-Data Era
Abstracts:
- Eric Blais (Carnegie Mellon University) (Canceled)
Title: The communication complexity method in property testing
Abstract:
Since it’s introduction by Yao in 1979, the communication complexity method has been
spectacularly successful in establishing lower bounds in a wide variety of settings
throughout computer science. In this talk, we will survey recent work that shows how
this method can also be used to prove lower bounds on the complexity of property
testing algorithms. During the talk, we will explore some of the lower bounds that can
be obtained with this method, we will examine connections with the Fourier analysis of
functions, and we will discuss some of the fundamental open problems suggested by the
use of this method.
- Francois Le Gall (University of Tokyo)
Title: Sublinear Quantum Algorithms for Graph-theoretic Properties
Abstract:
Sublinear-time algorithms are omnipresent in the field of quantum algorithms. A typical
example is the well-known quantum search algorithm (discovered by Grover in 1996), which
finds a marked element among n elements in O(n^{1/2}) time, while any classical algorithm
for this task requires linear time. Recently, several new algorithmic techniques have
been developed and used to construct quantum algorithms for testing many graph-theoretic
properties, such as deciding if a given graph contains a triangle of not. In this talk
I will first survey these recent developments, and then present new quantum algorithms
for testing several properties over hypergraphs.
- Comandur Seshadhri (Princeton University)
Title: Monotonicity and Lipschitz testing on hypergrids: alternating paths to the rescue
Abstract:
Monotonicity testing is a classic problem in property testing. The domain [n]^d
is equipped with the natural coordinate-wise partial order. A function f:[n]^d -> R is
called monotone, if for all x < y, f(x) \leq f(y). A function is f is said to be \eps-far
from monotone, if it needs to be changed at at least \eps n^d values to make it monotone.
The problem of monotonicity testing is to decide (in sublinear queries to f) whether f is
monotone or \eps-far from monotone. We prove there exists a tester making O(\eps^{-1} d log n)
queries. This matches all known lower bounds, and completely resolves the problem of
monotonicity testing on hypergrids. (The complexity even for the case of the boolean
hypercube {0,1}^d was open until this result.)
The main technique is a new framework of alternating paths that is used to relate distant
violations of monotonicity to local violations. This framework allows us to get optimal
algorithms for this problem. It also gives optimal results for Lipschitz testing,
a property with known connections to data privacy. Indeed, the alternating paths framework
gets testers for a large class of "derivative-bounded properties" on hypergrids.
Joint work with Deeparnab Chakrabarty
- Mitsuru Kusumoto (Kyoto University & ERATO)
Title: Testing Forest-Isomorphism in the Adjacency List Model
Abstract:
We consider the problem of testing whether two input forests are isomorphic
or far from being so. An algorithm is called an $\epsilon$-tester for forest-isomorphism
if given query access to two forests $G$ and $H$ in the adjacency list model, with high
probability, accepts if $G$ and $H$ are isomorphic and rejects if we must modify at least
$\epsilon n$ edges to make $G$ isomorphic to $H$. We show an $\epsilon$-tester for
forest-isomorphism with query complexity $\poly \log n$ and an almost matching lower bound
of $\Omega(\sqrt{\frac{\log n}{\log \log n}})$. With the aid of the tester, we also show
that every graph property is testable in the adjacency list model with $\poly \log n$
queries if the input graph is a forest.
- Skip Jordan (Hokkaido University & ERATO)
Title: Property Testing, Logic and Complexity
Abstract:
Given a computationally intractable problem, it is natural to consider
approximations and hope to gain efficiency. In property testing, we consider what can
be achieved given only a sublinear or constant sample of the input.
Here, I will introduce various open questions concerning combinations of
property testing and logic. Most are inspired by complexity theory,
and especially by descriptive complexity.
- Takahiro Ueda (Kyoto University)
Title: Sublinear-Time Cake-Cutting Algorithms
Abstract:
In this research, we show sub-linear time algorithms for the cake-cutting problem.
The cake-cutting problem is a problem of dividing a cake into pieces and handing them down
to players who have different measures of the value of the cake, and then they must be
``satisfied.'' Though the definition of ``satisfaction'' are various, e.g. simple-fair,
envy-free and so on, we talk about simple-fair division such that each player has 1/n values
in his/her piece of cake in his/her own value function. It is known that the query complexity
for the cake-cutting problem is \Theta(n logn) for both deterministic and random algorithms.
But no o(n)-time algorithm have been knows for dividing a piece only for the first player.
We construct a framework to solve the cake-cutting problem in sublinear-time, and show
algorithms in this framework. In particular, algorithms with {\eps n}-victims for
dividing a cake for r=o(n) players in O(r/\eps) times. And then the first r players who
are assigned a piece of cake must be satisfied. Furthermore, we extend this algorithm to
general f(n)-victims.
- Yuichi Yoshida (NII & Preferred Infrastructure)
Title: A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems
Abstract:
Let P be a property of functions Fnp → {0, 1} for a fixed prime p. An algorithm is called
a tester for P if, given a query access to the input function f, with high probability,
it accepts when f satisfies P and rejects when f is “far” from satisfying P. In this paper,
we give a characterization of affine-invariant properties that are testable with a constant
number of queries. The characterization is stated in terms of decomposition theorems, which
roughly claim that any function can be decomposed into a structured part that is a function
of a constant number of polynomials, and a pseudo-random part whose Gowers norm is small.
We first show an algorithm that tests whether the structured part of the input function has
a specific form. We then show that an affine-invariant property is testable with a constant
number of queries if and only if it can be reduced to the problem of testing whether the
structured part of the input function is close to one of a constant number of candidates.
- Hiro Ito (University of Electro-Communications)
Title: A Paradigm Shift Toward The Big-Data Era
Abstract:
In this century we are facing the big-data era. For treating big data, traditional
common sense sometimes does not work. Though we thought that polynomial-time algorithms
are fast algorithms in the past century, it is not always true for big data, e.g.,
an O(n^2)-time algorithm may be no longer fast! For such problems, sublinear-time,
especially constant-time algorithms should take important roles.
Yes, we need a new paradigm! In this talk, we try to consider what should be this
paradigm and how does it work.
懇親会:
日時: 2014年 12月 6日 (金) 17:45 〜
場所: しゃぶしゃぶ温野菜 神保町白山通り店
懇親会参加費: 4,000円 (予定) (会場で集めます)
懇親会参加申込(〆切:12月 3日 (火) 19:00)は下記URL:
https://www.al.ics.saitama-u.ac.jp/elc/reg/2013_1206_a02/
(人数確定の必要上、懇親会は事前申し込みが必要です。)
|
11/30 - 12/1
| ELC Mini-Workshop (B01 + C03) |
| 場所:
11/30(土)東北大学情報科学研究科棟 2F 大講義室
12/1(日)パームシティ131ビル 5F Room 5B
仙台市青葉区一番町3丁目1-16
プログラム:
Click to Continue ...11/30(土)16:45~
【チュートリアル】正代 隆義(九大)
グラフパターン言語の正例からの帰納推論と最適化問題
(懇親会)
12/1(日)9:30~
【チュートリアル】来嶋 秀治(九大)
置換多面体上の乱択丸め
【問題提起】
・畑埜 晃平(九大)
オフライン-オンライン変換について
・内澤 啓(山形大)
整数計画問題とCircuit-SAT
(昼食)
13:30~15:30
【問題提起】
・神山 直之(九大)
On the complexity of trial and error (STOC13) の紹介と問題発掘
・篠原 歩(東北大)
連の下界とオートマトンの学習問題(仮)
|
11/29 - 30
| 平成25年度 第2回領域会議 |
| Place : 東北大学 |
| 平成25年度第2回 ELC領域会議
日時 11月 29日,30日
場所:東北大学 青葉山キャンパス 情報科学研究科棟 2階 大講義室
アクセス情報:下記のサイト参照
Click to Continue ... http://www.is.tohoku.ac.jp/access/index.html
仙台駅前(西口)バス停から,710, 713, 715, 719 のいずれかに乗り,
情報科学研究科前バス停にて下車.所要時間は,20~40分です.
時刻表: http://www.donto.co.jp/timetable/citybus/bus_d_result.cgi?SW=90&TG=C&BSC=0050052
プログラム
11月29日
12:45~13:00 事務局連絡
13:00~13:50 講演: Benjamin Rossman (NII)
13:50~14:05 休憩
14:05~14:55 講演: 吉田 悠一 (NII)
14:55~15:10 休憩
15:10~16:00 講演: 畑埜 晃平 (九大)
16:10~17:30 総括班会議 (情報科学研究科棟2階 中講義室)
18:30~ 懇親会 居酒屋赤べこ
http://www.hotpepper.jp/strJ000026165/
11月30日
9:30~11:40 ポスターセッション
A01~C03 班までの各班が1件のポスター発表を**必ず**行う.
ここで,各班には,計画班だけでなく,公募班も含まれる.
13:00~13:50 講演: David Avis (京大)
13:50~14:05 休憩
14:05~14:55 講演: 渋谷 哲朗 (東大)
14:55~15:10 休憩
15:10~16:00 講演: 渡辺 治 (東工大)
16:00~16:15 事務局連絡
Benjamin Rossman (NII)
タイトル: Formulas vs. Circuits for Small Distance Connectivity
アブストラクト: We give the first super-polynomial separation in the power
of bounded-depth (unbounded fan-in) boolean formulas vs.
circuits. We consider the problem STCONN(k(n)) of
determining whether or not an n-vertex graph contains a
path of length <= k(n) between two distinguished vertices.
It is well known that STCONN(k(n)) has *circuits* of size
poly(n) and depth log(k). In contrast, we prove that
*formulas* of depth log(k) require size n^Omega(log(k)) for
all k(n) <= loglog(n). As a corollary, this implies a tight lower
bound of Omega(log(k)) on the depth of polynomial-size
circuits for STCONN(k(n)), improving the previous
Omega(loglog(k)) lower bound of Beame, Impagliazzo and
Pitassi [FOCS 1995].
吉田 悠一 (NII)
タイトル: A Characterization of Locally Testable Affine-Invariant
Properties through Decomposition Theorems
アブストラクト: Let P be a property of functions Fp^n → {0, 1} for a fixed
prime p. An algorithm is called a tester for P if, given a query
access to the input function f, with high probability, it accepts
when f satisfies P and rejects when f is “far” from satisfying
P. In this paper, we give a characterization of affine-invariant
properties that are testable with a constant number of
queries. The characterization is stated in terms of
decomposition theorems, which roughly say that any function
can be decomposed into a structured part that is a function
of a constant number of polynomials, and a pseudo-random
part whose Gowers norm is small. We first show an algorithm
that tests whether the structured part of the input function
has a specific form. We then show that an affine-invariant
property is testable with a constant number of queries if and
only if it can be reduced to the problem of testing whether the
structured part of the input function is close to one of a
constant number of candidates.
畑埜 晃平 (九大)
タイトル: メタラウンディングに基づく離散構造のオンライン予測
アブストラクト: 離散構造のオンライン予測問題は,ルーティングやランキング,ス
ケジューリングなど多くの分野に現れる.離散構造の例としては
s-t パス,集合被覆,順列などが挙げられる.予測者の目標は後
から見て最適な固定の離散構造に匹敵する予測をオンラインで
行うことである.この問題に対する汎用的なアプローチは,対応す
るオフライン(近似)離散最適化アルゴリズムをオラクルとして用
いる事である.これをオフライン-オンライン変換と呼ぶ.しかし,
現在知られ ているオフライン-オンライン変換手法は効率的で
はない.そこで本研究では,オフライン近似アルゴリズムが緩和
に基づく場合において,より効率的なオフライン-オンライン変
換手法を提案する.本研究ではメタラウンディングという特殊な
ウンディングを用いる事により,見通しのよい アルゴリズム設
計・解析が可能となった.
David Avis (京大)
タイトル: Exponential bounds for linear programs
アブストラクト: The first part of talk outlines joint work with Hans Tiwary
on finding exponential bounds for the extension complexity
of various NP-hard problems, including restrictions of
MAX_CUT. The second part outlines joint work with Oliver
Friedmann on finding an exponential lower bound on
Cunninham's pivot selection rule for linear programs and
unique sink orientations of hypercubes. Finally I will
discuss briefly some experimental results on a parallel
implementation of reverse search for vertex and
triangulation enumeration, which is joint work with Gary
Roumanis and Yuji Ishikawa.
渋谷 哲朗 (東大)
タイトル: Indexing Protein 3-D Structures for Faster Similarity Search
アブストラクト: Searching for protein structure-function relationships using
three-dimensional (3D) structural coordinates represents
a fundamental approach for determining the function of
proteins with unknown functions. Since protein structure
databases are rapidly growing in size, the development of
a fast search method to find similar protein substructures
by comparison of protein 3D structures is essential. In this
talk, we introduce a new indexing algorithm for fast protein
3-D structure similarity queries which is designed based
on a statistical model of the target 3-D structures. The new
method runs in O(m + N/m^{0.5}) average-case time, after
O(N log N) preprocessing, where N is the database size
and m is the query length. It is about 2 to 50 times faster
than the previous practically best-known O(N) algorithm,
which was also proposed previously by us, even if we
include the preprocessing time. It is almost 20-1000 times
faster than the naive comparison algorithm, according to
experiments on a huge SCOP database.
渡辺 治 (東工大)
タイトル:平面グラフの到達可能性の省スペース計算可能性
アブストラクト: We show that the reachability problem over directed planar
graphs can be solved simultaneously in polynomial time
and sublinear space, more precisely, O(n^{1/2+eps}) space
by using sublinear space algorithm computing a constant
ratio separator of planar graphs. In this talk we explain the
outline of our approach and report and then we report our
recent improvements on both reachability algorithm and
separator algorithm, which leads us to a new O(n^{1/2})
space and polynomial time algorithm for the planar graph
reachability problem. This is a joint work with T. Asano,
D.G. Kirkpatrick, T. Imai, K. Nakagawa, A. Pavan, and
N.V. Vinodchandran.
|
11/22
| ELC Seminar (Ravi Montenegro) |
| Place : 九州大学 伊都キャンパス |
| 日時:11/22(金)10:30-12:00
場所:九州大学 伊都キャンパス ウェスト2号館 3階 第5・6講義室
講演者:Ravi Montenegro (University of Massachusetts Lowell)
題目:A sharp heuristic for complexity of some Birthday attacks
inspired by Markov Processes
概要:
Click to Continue ...Birthday attacks use probabilistic "paradoxes'' to solve
cryptographic problems. However, the heuristics used to justify such
methods are usually not strong enough to differentiate a more
efficient approach from a less efficient one. We remedy this
shortcoming with a rigorous result for Pollard's Kangaroo method for
discrete logarithm, and extend it with a very precise heuristic that
applies to those attacks which are modeled on a Markov chain. This
precision makes it possible to explain the differing performance
between attacks that are superficially similar, such as Pollard's
Rho for discrete logarithm when compared to Teske's additive
version, and can also be used in optimizing birthday attack design.
問合せ:来嶋(B01)
|
11/18
| ELC Seminar (Ralf Borndrfer) |
| Place : 九州大学 伊都キャンパス |
| 日時:2013年11月18日(月)13:30-16:00
場所:九州大学 伊都キャンパス 数理学研究教育棟/マス・フォア・インダストリ研究所3F 中セミナー室7
講演者:Ralf Borndörfer (Zuse Institute Berlin)
参考URL:
http://www.imi.kyushu-u.ac.jp/seminars/view/1211
http://www.imi.kyushu-u.ac.jp/seminars/view/1212
Click to Continue ...13:30-14:30
Title: Optimization in Traffic and Transport
Speaker: Ralf Borndörfer (Zuse Institute Berlin)
Abstract:
The mathematical treatment of planning problems in public transit,
air, and rail traffic has made enormous advances in the last decade.
Classical problems of vehicle and crew scheduling can nowadays be
solved on a routine basis and for large scenarios using combinatorial
optimization methods. This is not yet the case for problems that
pertain to the design of public transit networks, and for problems of
operations control that address the implementation of a schedule in
the presence of disturbances. The talk surveys the state-of-the-art
and some exciting developments in the area, and it addresses major
challenges for the future.
15:00-16:00
Title: Configuration Models in Transport Optimization
Speaker: Ralf Borndörfer (Zuse Institute Berlin)
Abstract:
Configurations are local solutions of network optimization problems
that can be used to assemble an overall solution. They are used to
express complex requirements, that would be hard to formulate using
constraints, by means of a local and hence manageable enumeration of
``feasible configurations''. This gives rise to an extended
formulation involving additional configuration variables. Usually,
one has to make choices between several possible configurations, such
that configuration models are often of a set packing, partitioning,
or covering type. Such a formulation is combinatorially clean and
lends itself to column generation techniques. If the configurations
capture a core aspect of the problem, such a model will be provably
strong, if the configurations can be computed efficiently, it is
algorithmically tractable. Typical examples of configuration models
come up in transport optimization, where the integrated treatment of
technical etc. constraints or the simultaneous solution of
multi-stage models is a major challenge. Successful applications
include railway track allocation, leading to path packing
configuration models, railway rotation planning, resulting in
hypergraph assignment and flow models, and depot management as well
as line planning, leading to set partitioning type models. All of
these models provide strong LP bounds and can be solved efficiently
for large scale real-world problems. The talk surveys these results.
It is based on joint work with Martin Grötschel, Olga Heismann, Heide
Hoppmann, Marika Karbstein, Torsten Klug, Markus Reuther, Thomas
Schlechte, Elmar Swarat, and Steffen Weider.
問合せ先:来嶋(B01)
|
11/13 - 16
| SSS 2013 |
| 投稿〆切 : 2013/7/15 |
| Place : 大坂 |
11/12
| サイエンスカフェ 「計算の限界って?」 |
| Place : 東京工業大学 大岡山キャンパス 博物館・百年記念館 3階フェライト記念会議室 |
11/7
| ELC Mini-Workshop (C01) |
| Place : CELC seminar room |
| Date: Nov. 7th (Thu)
Time: 14:00 - 17:00 (with some coffee breaks)
Place: CELC Seminar room
(In the order of talks)
Speaker: Haiping Huang (JSPS research fellow, Tokyo Inst. of Tech., Japan)
Title: Entropy landscape analysis of the binary perceptron problem
Click to Continue ...Abstract:
In artificial intelligence, a binary perceptron is a device classifying
patterns with many inputs by assigning individual weights to each input,
and the weights take binary values. Often, these weights have to be
inferred from a set of examples. However, it is difficult to find a
low-complexity algorithm to identify these weights. Statistical
physicists started to study this problem 25 years ago by analyzing
the solution space of binary weights. However, the relation between
the solution space structure and the algorithmic hardness has not yet
been fully understood. Our work demonstrates two interesting effects
in the solution space through the entropy landscape analysis:
(1) clustering refers to the fragmentation of the solution space into
well-separated clusters; (2) freezing refers to the appearance of
isolated solutions instead of clusters of exponentially many close-by
solutions.
Our results explain the observed glassy behavior of stochastic local
search heuristics and are also expected to shed light on other hard
problems in information processing (e.g., channel coding systems).
Speaker: Mikko Vehkapera (Aalto University, Finland and KTH, Sweden)
Title: Compressed sensing with correlated measurement matrices and
application to metagenomics
Abstract:
In the first part of the talk, we review some analytical results
that characterize the performance of convex relaxation
based recovery algorithms used in compressed sensing.
In particular we are interested in the case where the
measurement matrix is of some other type than the standard
Gaussian ensemble. Using replica method, we show that under certain
conditions there are matrix ensembles that offer improved
performance of convex relaxation based recovery when compared
to the standard Gaussian ensemble.
The second part of the talk consists of examining a practical
problem of estimating bacterial community composition from
a high-throughput sequenced sample. Current estimation methods
that provide accurate results are typically computationally complex
and require the use of computing cluster. Using a method inspired by
sparsity enforcing techniques from compressed sensing, we propose a
fast solution to the aforementioned metagenomics problem. The model
solution is obtained both by using convex optimization tools and
through a greedy iterative algorithm and shown to provide good
accuracy-complexity tradeoff for the current problem.
END OF ANNOUNCEMENT
|
10/18
| 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 名古屋工業大学 |
10/17
| ELC Seminar (Andrej Bogdanov) |
| Place : CLEC Seminar Room |
| ELC C01 Seminar Announcement
Date: Oct. 17th (Thu)
Time: 14:00 - (followed by some talk by Osamu Watanabe)
Place: CELC Seminar room
http://www.al.ics.saitama-u.ac.jp/elc/celc/
Title: On the complexity and security of homomorphic encryption
Click to Continue ...Speaker: Andrej Bogdanov (Chinese Univ. of Hong Kong)
An encryption scheme is called homomorphic if given encryptions of
several plaintexts, one can compute an encryption of some function of
them (for example their sum) using public information only. This
feature is useful for applications like electronic voting and secure
outsourcing of computation.
We study homomorphic encryption from a complexity-theoretic
perspective. We show that:
1. For any sufficiently "sensitive" function f, if an encryption
scheme supports homomorphic evaluation of f, then this scheme cannot
be proved NP-hard to break (under widely believed complexity
assumptions).
2. For almost any function f, the ability to homomorphic evaluate f
implies the ability to rerandomize ciphertexts (turn a ciphertext
into another functionally equivalent but statistically independent
one).
3. Certain encryption schemes (both private and public key) can be
implemented by circuits of small depth, but homomorphic evaluation of
any nontrivial functionality requires large circuit depth.
Our results can be viewed as evidence that homomorphic encryption
schemes are inherently more complex and possibly less secure than
ordinary ones.
The talk is based on joint works with Chin Ho Lee.
END OF ANNOUNCEMENT
|
9/24 - 27
| ELC 暗号理論秋学校 |
| Place : 河口湖クラブセントビレッヂ |
| 実行委員: 河内 亮周 (東工大), 田中 圭介 (東工大)
講師: 河内亮周(東工大), 草川 恵太(NTT), 安永 憲司(金沢大), 松田 隆宏(AIST)
プログラム:
1限 9:00-10:15
2限 10:45-12:00
Click to Continue ...3限 13:00-14:15
4限 14:45-16:00
5限 16:30-17:45
9月24日
3限 河内: 擬似乱数性の統一理論(1)
4限 河内: 擬似乱数性の統一理論(2)
5限 河内: 擬似乱数性の統一理論(3)
25日
1限 草川: 完全準同型性暗号(1)
2限 安永: ブラックボックス構成とその限界(1)
3限 草川: 完全準同型性暗号(2)
4限 安永: ブラックボックス構成とその限界(2)
5限 草川: 完全準同型性暗号(3)
26日
1限 草川: 完全準同型性暗号(4)
2限 安永: ブラックボックス構成とその限界(3)
3限 草川: 完全準同型性暗号(5)
4限 松田: 公開鍵暗号の基礎理論(1)
5限 松田: 公開鍵暗号の基礎理論(2)
27日
1限 松田: How to Write a Paper (1)
2限 松田: How to Write a Paper (2)
|
9/24 - 26
| ELC 計算量理論の秋学校 |
| Place : 文化軽井沢山荘 |
| --------------
[日時] 9/24(火)14時〜9/26(木)12時
(初日受付は 13:30〜を予定)
[場所] 文化軽井沢山荘
http://www.bunkakaruizawasansou.com/
Click to Continue ...
軽井沢駅から車で15分(現在,送迎バスの依頼を検討中)
[プログラム]
9月24日(火) 14:00〜 9月26日(木) 12:00
(1時間x2コマ)x4人+自由討論
※ 詳細は決まり次第アナウンス致します
・河村彰星先生(東大)
「連続系の計算量」
・神山直之先生(九大)
「最適化手法と計算限界解析:双対性と整数性」
・津田宏治先生(産総研)
「ZDDに基づくグラフ要素列挙と、配電網最適化への応用」
・森前智行先生(群馬大)
「量子計算の基礎とInstantaneous Quantum Polynomial time」
(*) 自由討論で話題提供できる方を募集しています.
ELC関係者で共有したい話題,例えば
「ご自身または他人の面白い結果」「未解決問題や研究課題」
などがございましたら,ご一報いただけますと幸いです.
[参加費] 無料(宿泊費と懇親会代は現地で実費精算です)
大学院生以上で旅費支援が必要な場合にもご相談ください.」
宿泊費用
一般 27,000円程度
学生 20,000円程度
です.
当日受付にてお支払ください.
お釣りのないようにご準備お願いいたします.
----------------
問い合わせ先:小柴健史(koshiba@mail.saitama-u.ac.jp)
|
9/20
| ELC・岡田新学術領域合同シンポジウム/公募説明会 |
| Place : 九州大学 伊都キャンパス ウエスト2号館3F 325・326号室 |
| 日程:2013年9月20日(金) 10:30 - 16:45
会場:九州大学 伊都キャンパス
ウエスト2号館3F 325・326号室
ホームページ(岡田新学術領域):
http://sparse-modeling.jp/symposium/mini_symposium_Kyushu.html
Click to Continue ...
プログラム
10:30 - 11:30 岡田真人(東京大学/新領域創成科学研究科)
「新学術領域 疎性モデリングの目的・狙い / 公募研究募集についての説明 」
11:30 - 12:00 瀧本英二(九州大学)
「新学術領域 ELCの概要+C03 班の研究概要」
12:00 - 13:30 昼食
13:30 - 14:00 末廣大貴(九州大学)
「1ノルムソフトマージン最適化に基づくランキング学習」
14:00 - 14:30 内澤啓(山形大学)
「Computational Power of Threshold Circuits with Sparse Activity」
14:30 - 15:00 篠原歩(東北大学)
「決定性有限オートマトンの最小無矛盾問題について」
15:00 - 15:15 休憩
15:15 - 15:45 高橋成雄(東京大学)
「微分トポロジーに基づく多次元・多変量データ解析と可視化」
15:45 - 16:15 永田賢二(東京大学)
「スペクトル分解によるデータ駆動科学」
16:15 - 16:45 渡辺澄夫(東京工業大学)
「非正則な統計モデルのベイズ法における評価方法について」
なお,シンポジウム終了後懇親会を予定しています.
参加希望の方は9/17までに九大畑埜(hatano(a)inf.kyushu-u.ac.jp)までお知らせください.
|
9/20
| UEC & ELC Joint Seminar on Theoretical Computer Science |
| Place : AV hall, 3F, West-9 BLDG, The University of Electro-Communications(電気通信大学, 西9号館, 3F AVホール) |
| Speakers: 1. John Iacono (Polytechnic Institute of New York University),
2. Stefan Langerman (Universite Libre de Bruxelles)
3. Erik D. Demaine (MIT)
--
UEC & ELC Joint Seminar on Theoretical Computer Science
We are going to have a seminar on Theoretical Computer Science,
Click to Continue ...which consists of three talks by distinguished researchers.
We hope you all participate.
--
Time and Date: 13:30--16:20, Sept.20, 2013.
Place: AV hall, 3F, West-9 BLDG, The University of Electro-Communications
Program ----
13:30--14:30
John Iacono (Polytechnic Institute of New York University)
Title: In pursuit of the dynamic optimality conjecture
Abstract:
In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting
binary search tree algorithm. Splay trees were conjectured to perform
within a constant factor as any offline rotation-based search tree
algorithm on every sufficiently long sequence---any binary search tree
algorithm that has this property is said to be dynamically optimal.
However, currently neither splay trees nor any other tree algorithm is
known to be dynamically optimal. Here we survey the progress that has
been made in the almost thirty years since the conjecture was first
formulated, and present a binary search tree algorithm that is
dynamically optimal if any binary search tree algorithm is dynamically
optimal.
--
14:30--15:20
Stefan Langerman (Universite Libre de Bruxelles)
Title: Bichromatic compatible matchings
Abstract:
For a set $R$ of $n$ red points and a set $B$ of $n$ blue points, a
$BR$-matching is a non-crossing geometric perfect matching where each
segment has one endpoint in $B$ and one in $R$. Such a matching always
exists. Two $BR$-matchings are compatible if their union is also
non-crossing. We prove that, for any two distinct $BR$-matchings $M$
and $M'$, there exists a sequence of $BR$-matchings $M = M_1, ..., M_k
= M'$ such that $M_{i-1} $ is compatible with $M_i$.
Joint work with Greg Aloupis, Luis Barba, and Diane L. Souvaine
--
15:30--16:20
Erik D. Demaine (MIT)
Title: Geometric Folding Algorithms: Linkages, Origami, Polyhedra
Abstract:
What forms of origami can be designed automatically by algorithms?
How might we build reconfigurable robots like Transformers or Terminator 3,
hinging together a collection of pieces that dynamically reconfigure
into arbitrary shapes? When can a robotic arm of rigid rods be folded into
a desired configuration? What shapes can result by folding a piece of
paper flat and making one complete straight cut? What 3D surfaces can be
manufactured from a single sheet of material? How might proteins fold?
Geometric folding is a branch of discrete and computational geometry
that addresses these and many other intriguing questions.
I will give a taste of the many results that have been proved in the past
several years, as well as the several exciting unsolved problems that remain
open. Many folding problems have applications in areas including
manufacturing, robotics, graphics, and protein folding.
--
Organizer: Hiro Ito (School of Informatics and Engineering, UEC)
|
9/17
| ELC Seminar (C01 and A01) |
| Place : CELC |
| Date: 2013.9.17 (Tue)
Time: 14:00 - 17:00
Place: CELC seminar room (new one! on the 4the floor)
Speakers:
1. Sebastian Muller (ELC Postdoc fellow, C01 and A01)
Polylogarithmic Cuts in Models of Weak Arithmetic
Click to Continue ...
2. Xiaohui Bei (Nanyang Technological Univ., Singpore)
On the Complexity of Trial and Error
3. Ning Chen (Nanyang Technological Univ., Singpore)
Solving Linear Programming with Constraints Unknown
Details (with abstracts):
1. Sebastian Muller (ELC postdoc reseaercher, C01 and A01)
Title: Polylogarithmic Cuts in Models of Weak Arithmetic
Abstract:
Propositional proof systems are polynomial time computable surjective
functions that map strings to propositional tautologies. We call any
preimage of a tautology a proof. Properties of such systems are
closely related to the coNP = NP question; in fact, coNP = NP iff
such a proof system exists with short proofs for every tautology.
In this light it is interesting to compare two proof systems by
their minimal lengths of proofs for any family of tautologies. We say
that one proof system simulates another, if for any proof in the
latter system there is one in the former system that is approximately
of the same length. Two examples of propositional proof systems are
Frege systems and bounded depth Frege systems. These systems are
textbook style proof systems as are depicted in most basic logic
literature. They differ in strength, however, and we do not expect
bounded depth Frege systems to simulate Frege systems.
Models of weak arithmetics are well known to capture the strength of
certain such propositional proof systems. We exploit this property
to explore the relation between Frege and bounded depth Frege systems.
More precisely we will show that a certain initial segment of any
model that relates to bounded depth Frege systems, relates to Frege
systems. An easy argument will then allow us to turn Frege proofs of
any given length into bounded depth Frege proofs such that the proof
length is not increased exponentially. This yields a sub-exponential
simulation of Frege by bounded depth Frege systems.
2. Xiaohui Bei (Nanyang Technological Univ., Singpore)
Title: On the Complexity of Trial and Error
Abstract:
Motivated by certain applications in which the objects
under investigation are unknown or not directly accessible because
of various limitations, we propose a trial-and-error model to examine
search problems in which inputs are unknown.
More specifically, we consider constraint satisfaction problems
$\bigwedge_i C_i$, where the constraints $C_i$ are hidden, and the
goal is to find a solution satisfying all constraints. We can
adaptively propose a candidate solution (i.e., trial), and there is
a verification oracle that either confirms that it is a valid solution,
or returns the index $i$ of a violated constraint (i.e., error), with
the exact content of $C_i$ still hidden.
We studied the time and trial complexities of a number of natural
CSPs, summarized as follows. On one hand, despite the seemingly very
little information provided by the oracle, efficient algorithms do
exist for Nash, Core, Stable Matching, and SAT problems, whose
unknown-input versions are shown to be as hard as the corresponding
known-input versions up to a factor of polynomial. The techniques
employed vary considerably, including, e.g., order theory and the
ellipsoid method with a strong separation oracle.
On the other hand, there are problems whose complexities are
substantially increased in the unknown-input model. In particular,
no time-efficient algorithms exist for Graph Isomorphism and Group
Isomorphism (unless PH collapses or P = NP). The proofs use quite
nonstandard reductions, in which an efficient simulator is carefully
designed to simulate a desirable but computationally unaffordable
oracle.
Our model investigates the value of input information, and our
results demonstrate that the lack of input information can introduce
various levels of extra difficulty. The model accommodates a wide
range of combinatorial and algebraic structures, and exhibits
intimate connections with (and hopefully can also serve as a useful
supplement to) certain existing learning and complexity theories
3. Ning Chen
Title: Solving Linear Programming with Constraints Unknown
Abstract:
What is the value of information in solving linear programming?
The celebrated ellipsoid algorithm tells us that the full
information of input constraints is not necessary; the algorithm
works as long as there exists an oracle that, on a proposed
candidate solution, returns a violation in the format of a
separating hyperplane. Can linear programming still be efficiently
solved if the returned violation is in another format?
We study this question in the aforementioned trial-and-error setting.
We give an algorithm with running time $O(m^{poly(n)} * L)$,
where $m$ and $n$ are the numbers of constraints and variables,
respectively, and $L$ is the input size of the linear program.
The exponential dependence on $n$ is unfortunately unavoidable; we
show a lower bound of $\Omega(m^{[n/2]})$ on the number of queries
needed. Meanwhile, if the oracle provides more violation
information---the index of a "most violated" constraint, measured
by the Euclidean distance of the proposed solution and the
half-spaces defined by the constraints---then we show that the
linear program can be solved in polynomial time.
The proofs of the results employ a variety of geometric techniques,
including McMullen's Upper Bound Theorem, the weighted spherical
Voronoi diagram, and the furthest Voronoi diagram. In addition, we
give an alternative proof to a conjecture of Laszlo Fejes Toth on
bounding the number of disconnected components formed by the
union of $m$ convex bodies in $R^n$. Our proof, inspired by the
Gauss-Bonnet Theorem in global differential geometry, is independent
of the known and clearly reveals more insights into the problem
and bound.
END OF SEMINAR INFO.
|
9/8
| ELC Mini-Workshop (B01) |
| Place : 京都大学桂キャンパスC2棟213号室 |
| プログラム:
10:30 -- 12:00 研究進捗状況の報告
12:00 -- 13:00 昼休み
13:00 -- 14:30 研究進捗状況の報告
14:30 -- 15:00 休憩
15:00 -- 17:00 議論
Click to Continue ...
|
9/6
| FIT2013 イベント企画 (JST ERATO 湊PJ/河原林PJとの共同企画) |
| Place : 鳥取大学 鳥取キャンパス |
| FIT 2013 (第12回情報科学技術フォーラム) でのイベント企画で、
JST ERATO 湊 離散構造処理系プロジェクト、JST ERATO 河原林 巨大グラフプロジェクト
との共同企画です。
|
8/16 - 17
| ELC Mini-Workshop (B03) |
| Place : 奈良 |
| 会場: やまとビル 5F 大会議室B
やまと会議室 http://www.yamatobill.jp/
奈良県奈良市登大路町36番地 (近鉄奈良駅そば)
予定:
8月16日(金) 13:00~16:30 話題提供セッション
8月17日(土) 09:00~12:30 問題解決セッション
Click to Continue ...
|
8/1
| ELC Seminar on Computation and Stat. Physics (C01) |
| Place : CELC seminar room |
| Date: 2013.8.1 (Thu)
Time: 14:00 - 18:00
Place: CELC seminar room
Speakers (only guest speakers, some from C01 will give a talk also)
Erik Aurell (KTH, Stockholm)
Click to Continue ...
Title: The inverse Ising problem and its generalizations have
emerged as a common point of interest
Abstract:
Learning spatial amino acid contacts from many homologous protein sequences
of statistical physics and machine learning. A major success has been
achieved in determining physical proximity of amino acid residues in
families of homologous proteins by learning an appropriate Potts model
where each variable can take 21 states representing the 20 amino acids
and a gap in an alignment (Lapedes et al 2001 (unpub), Weigt et al 2009,
Marcos et al 2011, Hopf et al 2012 and many follow-up papers).
Improving such contact predictions can be achieved by (at least) (i) starting
from better and/or more appropriate protein families and sequence alignments
(ii) learning the Potts model more accurately and (iii) learning other models
which allow for better prediction of the protein structures. I will review
these points with an emphasis on (ii) and (iii) and discuss why it appears
to make sense to learn such relatively simple models as Potts models to
describe in principle a quite complicated trace left in the molecular
record by evolution.
Our work in this direction is presented in Ekeberg et al Phys. Rev. E 87,
012707 (2013) and our codes are available at plmdca.csc.kth.se.
Pinyang Lu (Microsoft, Shanghai)
Title: Approximate Counting via Correlation Decay
Abstract:
In this talk, I will survey some recent development of approximate counting
algorithms based on correlation decay technique. Unlike the previous major
approximate counting approach based on sampling such as Markov Chain Monte
Carlo (MCMC), correlation decay based approach can give deterministic fully
polynomial-time approximation scheme (FPTAS) for a number of counting
problems.
|
7/28 - 30
| ELC International Meeting on ''Inference, Computation, and Spin Glasses'' (ICSG2013) |
| Place : Hokkaido Univ. (Sapporo) |
| 韓国で開かれる統計力学の大きな国際会議のサテライトワークショップとしてC01班で企画
したワークショップです.是非ご参加をご検討ください.
|
7/16
| ELC Seminar on Quantum Query Complexity (C02) |
| Place : CELC |
| 量子ウォークのグラフ問題の適用について議論する。
|
6/26
| NII & ELC Joint Seminar (Saraf & Kopparty) |
| Place : CELC Seminar Room |
| 15:00-17:30
Speaker: Shubhangi Saraf (Rutgers University)
Title: Incidence geometry and applications to theoretical computer
science
The classical theorem of Sylvester-Gallai states the following: given
Click to Continue ...a finite set of points in the Euclidean plane, not all on the same
line, there exists a line passing through exactly two of the points.
This result has a rich and interesting history in mathematics.
Surprisingly in recent years variants of the theorem have been
influential in various diverse areas of theoretical computer science.
In this talk I will describe several extensions to the Sylvester
Gallai theorem - quantitative versions, high dimensional versions,
colorful versions and average case versions. I will also describe
some of the applications and connections in theoretical computer
science to areas such as polynomial identity testing, local
algorithms for error correcting codes as well as lower bounds for
arithmetic computation.
Based on joint works with Albert Ai, Zeev Dvir, Neeraj Kayal and
Avi Wigderson
======================
Speaker: Swastik Kopparty (Rutgers University)
Title: CONSTANT RATE PCPS FOR CIRCUIT-SAT WITH SUBLINEAR QUERY
COMPLEXITY
The PCP theorem says that every NP-proof can be encoded to another
proof, namely, a probabilistically checkable proof (PCP), which can
be tested by a verifier that queries only a small part of the PCP. A
natural question is how large is the blow-up incurred by this
encoding, i.e., how long is the PCP compared to the original NP
proof. The state-of-the-art works of Ben-Sasson, Sudan and Dinur show
that one can encode proofs of length n by PCPs of length
(n polylog n) that can be verified using a constant number of
queries.
I will talk about a recent result, joint with Eli Ben-Sasson, Yohay
Kaplan and Or Meir, showing that one can encode proofs of length n by
PCPs of length O(n), such that the proofs can be checked
with n{epsilon} query complexity (for every epsilon > 0). This is
the first constant-rate PCP construction that achieves constant
soundness with nontrivial query complexity (o(n)).
Our proof replaces the low-degree polynomials codes in traditional
algebraic PCP constructions with algebraic-geometric (AG) codes. We
show that the automorphisms of an AG code can be used to simulate the
role of affine transformations which are crucial in earlier high-rate
algebraic PCP constructions. Using this observation we conclude that
any asymptotically good family of transitive AG codes over a constant
sized alphabet leads to a family of constant-rate PCPs with
polynomially small query complexity. The required family of
transitive AG codes was recently constructed by Henning Stichtenoth,
and appears in the appendix to our paper.
|
6/24
| 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 奈良女子大学 |
6/14 - 19
| ELC Workshop on Polyhedral Approaches: Extension complexity and pivoting lower bounds |
| Place : Kyoto |
| ELC Workshop on Polyhedral Approaches:
Extension complexity and pivoting lower bounds
(organized by ELC B01,B02)
June 14-19 Kyoto
Please register at https://www.al.ics.saitama-u.ac.jp/elc/reg/2013_wpa/
Click to Continue ...Workshop information: http://www.al.ics.saitama-u.ac.jp/elc/en/?event/2013/0614_0619
There have been some exciting new lower bound results related to
LP pivoting and extension complexity for integer programs, which
are of direct relevance to the ELC project. Progress is swift at
the moment and there are many interesting open problems.
The format of the workshop will be a three day meeting June 14-16
"Bellairs style"(see below) at the guest house Community Sagano
in Arashiyama. All participants are expected to stay on-site. The
meeting will then move to the Clock tower at Yoshida campus of Kyoto
university for June 17-19. A detailed schedule will be prepared at the meeting.
By 'Bellairs style' is meant a workshop which is focused on trying
to solve, or at least make progress on, a fairly narrowly defined
set of problems. There are relatively few talks, and certainly no
pressure to give one. The main point is to be present and actively
participate in the discussions. Due to the nature of the meeting,
the number of participants is limited to about 25 people. Confirmed
overseas participants are:
D. Bremner, B. Cook, K. Fukuda, V.Kaibel, S. Polutta and H. Tiwary
David Avis (avis@i.kyoto-u.ac.jp)
Naoki Katoh (naoki@archi.kyoto-u.ac.jp)
|
6/13 - 14
| 平成25年度 第1回領域会議 |
| Place : 京都大学本部キャンパス (部屋は詳細を参照してください) |
| 2013年度第1回 ELC領域会議
日時:6月13日9:00~6月14日11:20
場所 : 京都大学本部キャンパス
6月13日午前: 総合研究4号館 1階 共通2
6月13日午後: 総合研究8号館 3階 Sホール
Click to Continue ... 6月14日: 総合研究7号館 1階 情報2講義室
プログラム
6月13日 午前 (場所:総合研究4号館 1階 共通2)
9:00~9:30 領域の方向性:渡辺領域代表、事務局連絡
9:30~9:45 A01班
9:45~10:00 A02班
10:00~10:15 A03班
10:15~10:30 休憩
10:30~10:45 B01班
10:45~11:00 B02班
11:00~11:15 B03班
11:15~11:30 C01班
11:30~11:45 C02班
11:45~12:00 C03班
昼休み
6月13日 午後 (場所:総合研究8号館 3階 Sホール)
13:00~13:15 公募研究班 Skip Jordan (北海道大学)
13:15~13:30 公募研究班 宇野 裕之 (大阪府立大学)
13:30~13:45 公募研究班 安永 憲司 (金沢大学)
13:45~14:00 公募研究班 泉 泰介 (名古屋工業大学)
14:00~14:15 公募研究班 塩浦 昭義 (東北大学)
14:15~14:30 休憩
14:30~14:45 公募研究班 森山 園子 (東北大学)
14:45~15:00 公募研究班 山中 克久 (岩手大学)
15:00~15:15 公募研究班 伊藤 健洋 (東北大学)
15:15~15:30 公募研究班 永田 賢二 (東京大学)
15:30~16:00 休憩&ポスターセッションの準備
16:00~18:00 ポスターセッション
(注:17:00より総合研究8号館 3階 Nホールにて総括班会議を開催)
懇親会
時間 19:00~
場所: 百万遍 しゃらく
http://r.gnavi.co.jp/k614100/map/
6月14日(場所:総合研究7号館 1階 情報2講義室)
9:00~ 9:40 講演: 脊戸 和寿 (電気通信大学)
9:40~ 9:50 休憩
9:50~10:30 講演: 上野 賢哉 (京都大学)
10:30~10:40 休憩
10:40~11:20 講演: 内澤 啓(山形大学)
脊戸 和寿 (電気通信大学)
タイトル: Circuit Satisfiability
アブストラクト: Circuit Satisfiability (CktSAT)とは与えられた論理
回路の出力が1になる入力割当が存在するかどうかを判定する問題である.これは
有名なNP完全問題の1つであり,入力変数の多項式時間では解けそうにない.
それどころか,一般の多項式サイズの回路が与えられるとその充足可能性判定には,
2^n時間必要であると思われている.2010年,Ryan WilliamsはCktSATが2^n
よりも超多項式的に高速にとけるなら,NEXPが多項式サイズの回路をもたないことを
示した.(NEXP not in P/poly) さらに,ある特定の回路クラスCに制限した
CktSAT (C-SAT)が同じように高速にとけるなら,NEXPが多項式サイズのクラスCの
回路をもたないことも示している.(NEXP not in C) これ以降,CktSATに対する
研究は加速し,様々なC-SATに対するアルゴリズムが開発された.現時点でCktSATの
アルゴリズムの開発によって計算量クラスの分離に成功したのは,Ryan Williamsの
NEXP not in ACC0のみであるが,多くのC-SATの結果に付随して,Average
Case HardnessやCorrelation Boundが示されている.これは一種の計算限界を
示すものである.本発表では,一連のCktSATの結果を紹介し,今後の展開について述べる.
上野 賢哉 (京都大学)
タイトル: 非平衡な再帰関数の計算限界
アブストラクト:再帰的に定義された論理関数に対して,論理式サイズ下界を証明する
方法として量子敵対者法を説明し,再帰が非平衡な場合への適用を考えるとともに,
下界証明に対する一般的な証明限界について議論する.
内澤 啓 (山形大学)
タイトル: 論理回路の出力パターン数とその応用
アブストラクト:論理回路とは,AND素子やOR素子などの論理素子を基本素子とする
組合せ回路である.入力が与えられた時に論理回路が行う計算は,回路を構成する
各素子の出力値の組合せ,即ち,出力パターンとして表現できる.ここで,ある回路に
現れる出力パターンの種類の総数を,その回路の出力パターン数と呼ぶ.本講演で
は,この回路の出力パターン数を解析することによって得られる論理回路の下界や,
その他の応用について述べる.
|
5/25 - 26
| ELC Mini-Workshop (B01, C03) |
| Place : 東北大学大学院情報科学研究科棟 2F 大講義室 |
| 5/25(土)
10:30~12:00 Randomness in Algorithm Design(来嶋)
(昼食)
13:00~14:00 領域会議(6/13,14)に向けた準備,今後の方針について
Click to Continue ...14:15~15:15 B01+C03 班の連携の実績紹介
・瀧本,畑埜+来嶋の事例(畑埜)
・内澤+神山の事例(内澤)
15:30~17:30 話題提供トーク
5/26(日)
10:00~12:00 話題提供トーク
(昼食)
13:00~15:00 話題提供・自由討論
|
5/23
| ELC Seminar (Xavier Dahan) |
| Place : 九州大学伊都キャンパスウェスト2号館 3階 第5・6講義室 |
| 日時:5/23(木)16:00-17:30
場所:九州大学伊都キャンパスウェスト2号館 3階 第5・6講義室
講演者:Xavier Dahan (九州大学)
題目:高girthのエキスパンダーグラフの代数的な構造
概要:
エキスパンダグラフは30年以上前から、
理論情報学において 様々なところで適用できるものである。
Click to Continue ...2000年代から著しく発展し、非常に注目される分野になった。
その上、高girthグラフの構造は難しい問題と考えられ、
現在の記録を1986のRamanujanグラフによって与えられた。
この発表では、エキスパンダーグラフの面白さや高girthグラフの大事さを説明し、
新しい構造や、構造の試行について記述する。
両者は、1986の有名なRamanujanグラフに関係があります。
|
5/21
| ELC & NII Joint Seminar (Rahul Santhanam) |
| Title: Algorithmic Analysis and Complexity Lower Bounds
Speaker: Rahul Santhanam (Univeristy of Edinburgh)
Date & Time: May 21st, 2013, 15:30-16:30
Place: Tokyo Tech. CIC at Tamachi, 2F, Meeting Room #1
Abstract: I will give an overview of recent work on connections between
Click to Continue ...complexity lower bounds and algorithms for Satisfiability beating brute
force search. On the one hand, Williams established a formal connection
from non-trivial SAT algorithms to circuit lower bounds, and used this
connection to prove that NEXP not in ACC_0. On the other hand, new
algorithms for Satisfiability have been found and analyzed recently by
Impagliazzo-Mathews-Paturi, Seto-Tamaki and myself, with the analysis in
each case inspired by complexity lower bound techniques. In addition to
surveying recent work, I will give some high-level arguments why
algorithmic methods are a promising approach to circuit lower bounds,
and indicate some of the main open problems in this area.
host: Osamu Watanabe and Benjamin Rossman
watanabe@is.titech.ac.jp
|
5/20
| ELC Seminar (Bakhadyr Khoussainov) |
| Place : 計算限界解明センター(田町) |
| ELC Seminar
Monday 1 pm, May 20, 2013
Seminar room, ELC Centre, 5th floor of Tokyo Institute of Technology Tamachi office
http://www.al.ics.saitama-u.ac.jp/elc/en/?celc
Algorithmically random infinite structures
Bakhadyr Khoussainov (University of Auckland)
Click to Continue ...
The last two decades have witnessed significant advances in the
investigation of algorithmic randomness of infinite strings.
Monographs by Downey and Hirschfeldt, and by Nies account for the
recent research activities in the area. In spite of much work,
research on randomness of infinite strings has excluded the
investigation of algorithmic randomness for infinite algebraic
structures such graphs, trees, groups or more generally universal
algebras. In this talk, we provide a framework for reasoning about
algorithmic randomness for various classes of infinite structures.
問合せ先:河村(A01班)
|
5/14 - 15
| ELC Workshop on Randomness and Probability Through Computability (A01) |
| 投稿〆切 : 2013/4/19 |
| Place : 東京大学(本郷キャンパス)工学部六号館三階セミナー室AD |
| 問合せ先:河村
|
5/14
| ELC Seminar on Quantum Query Complexity (C02) |
| Place : CELC |
| 量子質問計算量(Quantum Query Complexity)に関する以下の論文2件を報告する予定です.
Nested Quantum Walks with Quantum Data Structures
(Stacey Jeffery, Robin Kothari, Frederic Magniez
http://arxiv.org/abs/1210.1199
Quantum algorithms for search with wildcards and combinatorial group testing
Click to Continue ...(Andris Ambainis, Ashley Montanaro)
http://arxiv.org/abs/1210.1148
日時: 2013年5月14日13:00~
場所: Center for Exploring the Limits of Computation (CELC)
http://www.al.ics.saitama-u.ac.jp/elc/?celc
連絡先: 興味があって参加したいという方はC02班の山下,河内,西村の誰かにメイルいただければ幸いです.
|
5/13
| ELC Seminar (Sanjeev Arora) |
| Place : CELC seminar room |
| ELC seminar
Date and Time: May 13th (Mon.) 14:00 - 15:00
Place: CELC seminar room
*1) polycom access is possible
*2) for using polycom, we decided to have a seminar at the
small seminar room. so if you are coming to the seminar
room, please send a message to Osamu Watanabe
Click to Continue ... watanabe(at)is.titech.ac.jp
Title: Is Machine Learning Tractable? --- Three Vignettes
Speaker: Sanjeev Arora (Princeton University)
Abstract:
Many tasks in machine learning (especially unsupervised learning) are
provably intractable: NP-complete or worse. Nevertheless, researchers
have developed heuristic algorithms to try to solve these tasks in
practice. In most cases, these algorithms are heuristics with no
provable guarantees on their running time or on the quality of
solutions they return. Can we change this state of affairs?
This talk will suggest that the answer is yes, and describe three of our
recent works as illustration. (a) A new algorithm for learning topic
models. (It applies to Linear Dirichlet Allocations of Blei et al. and
also to more general topic models. It provably works under some
reasonable assumptions and in practice is up to 50 times faster than
existing software like Mallet. It relies upon a new procedure for
nonnegative matrix factorization.) (b) What classifiers are worth
learning? (Can theory illuminate the contentious question of what binary
classifier to learn: SVM, Decision tree, etc.?) (c) Provable ICA with
unknown gaussian noise. (An algorithm to provably learn a "manifold"
with small number of parameters but exponentially many "interesting
regions.")
The talk will be self-contained.
(Based upon joint works with Rong Ge, Ravi Kannan, Ankur Moitra, Sushant
Sachdeva.)
|
4/22
| ELC Seminar (Sampath Kannan) |
| Place : 九州大学伊都キャンパス ウエスト2号館3階第7講義室(W2-327) |
| 日時:4月22日(月)15:00 - 16:30
Generalized Sorting
Sampath Kannan (University of Pennsylvania)
The well-known problem of sorting still has some interesting
Click to Continue ...variations that have not been fully explored. In this talk we
consider the problem when we are given a graph that specifies which
pairs of elements we are allowed to compare.
Under the promise that making all the comparisons will reveal a total
order, we show that it is possible to design a randomized algorithm
that makes about n^{3/2} comparisons on any graph and determines the
total order.
This is joint work with Zhiyi Huang and Sanjeev Khanna.
問合せ先:瀧本(C03)
|
4/11
| ELC Seminar (Colin Cooper) |
| Place : 九州大学伊都キャンパスウェスト2号館 3階 第5・6講義室 |
| 日時:4/11(木)10:00-11:30
Coalescing Random Walks and Voting on Graphs
Colin Cooper (Department of Informatics, King's College London)
The standard model of voting on connected graphs is as follows:
Click to Continue ...Initially each neighbour has a distinct opinion. The voting proceeds
in rounds. In each round each vertex contacts a randomly chosen
neighbour and adopts their opinion. We refer to this model as
single-sample voting. In voting, the quantities of interest are the
time for voting to complete, and the probability a particular opinion
wins.
The talk focuses on the following topics:
Single sample voting.
The relationship between single sample voting and coalescing random
walks. These processes are dual and we can use random walks to
analyze the performance of voting. Using this, we give an upper bound
for the expected time for voting to complete on general connected
graphs.
Other models of voting.
In the standard voting model, each vertex checks the opinion of one
neighbour at each step. We consider models of voting where more than
one opinion is sampled at each step. The simplest such model is
two-sample voting where each vertex randomly samples the opinions of
two neighbours at each step. For this model we discuss min-voting and
two-party voting.
Min-voting.
In min-voting, each vertex initially has a distinct numeric opinion
between 1 and n (the graph size). At each step each vertex randomly
samples the opinion of two neighbours, and adopts the minimum opinion.
This process completes in O(log n) expected time on certain classes
of expanders.
Two-party voting.
In two-party voting, each vertex initially holds one of two opinions
(e.g. 0 or 1). We are interested in the time taken for all vertices
to have the same opinion, and the probability that a given opinion
wins. We review the results for two-party voting in the standard
(single-sample) model of voting. We discuss the performance of
two-party voting when more than one opinion is sampled at each step.
We give some results for the outcome of two-party voting on r
regular expanders when we use two-sample voting. Compared to
single-sample voting, the performance of this process is more
consistent and obtained more rapidly.
問合せ先:来嶋(B01)
|
3/19
| Satellite Mini-Workshop, Kyoto |
| Place : RIMS, Kyoto Univ., Kyoto |
| Mar19(Tue) Satellite Mini-Workshp, Kyoto
venue: Room 111, RIMS, Kyoto Univ, Kyoto
http://www.kurims.kyoto-u.ac.jp/en/access-01.html http://goo.gl/aCgSE
registration not necessary; no participation fee; everybody is welcome
organizers: Shin-ichi Tanigawa(RIMS), Suguru Tamaki(Kyoto U), Jun Tarui(UEC)
13:15--14:15 Raghu Meka: Beating the Union Bound via Gaussian Geometry
Click to Continue ...14:15--14:30 break
14:30--15:30 Zeev Dvir: Locally Decodable Codes: recent progress and open problems
15:30--15:45 break
15:45--17:15 Ketan Mulmuley: The GCT chasm
18:00-- impropmtu dinner party around Sanjo-Kawara-machi
(We will move to a dinner place from the workshop venue.
Please note that dinner is not free of charge,
and you are kindly asked to come on time.)
Abstracts:
Raghu Meka: Beating the Union Bound via Gaussian Geometry:
The union bound is one of the mainstays of the probabilistic method and
analysis of randomized algorithms. However, this simplistic approach does
not give the full picture for many important cases, with Lovasz local lemma
being a particularly salient example. In this talk I will discuss two recent
results that go beyond the union bound via geometric techniques:
1) Optimal size, explicit eps-nets for computing Gaussian integrals.
2) A new elementary and constructive proof of Spencer's celebrated
six standard deviations suffice theorem.
For both problems, our methods critically exploit certain geometric and
symmetry properties of the Gaussian space.
Zeev Dvir: Locally Decodable Codes: recent progress and open problems:
Locally Decodable Codes (LDCs) are error correcting codes that allow for
super efficient decoding of a single message symbol using only a small
number of queries to a corrupted codeword. These codes and their variants
have many theoretical applications and are also starting to appear in
practical scenarios. Our understanding of these codes is quite limited
and this talk will attempt to survey the state of the art both in term
of constructions and lower bounds.
Ketan Mulmuley: The GCT chasm:
It is shown that derandomization of Noether's Normalization Lemma (NNL) for explicit varieties
is essentially equivalent to black-box derandomization of Polynomial Identity Testing (PIT). This and
related results reveal that the fundamental problems in Geometry (classification
of algebraic varieties) and Complexity Theory (derandomization and lower bounds) share a common
root difficulty, namely the problem of overcoming the formidable EXPSPACE vs. P gap in the
complexity of NNL for explicit varieties. We call this gap the GCT chasm.
|
3/18
| 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 岐阜大学 |
3/17
| Satellite Mini-Workshop on Geometric Complexity Theory (GCT) |
| Place : Campus Inovation Center Tokyo |
| Mar17(Sun) Satellite Mini-Workshop on Geometric Complexity Theory(GCT)
venue: 2nd floor meeting room, Campus Innovation Center, Tamachi
http://www.cictokyo.jp/access.html http://goo.gl/aCgSE
registration not necessary; no participation fee; everybody is welcome
organizers: Takeshi Tokuyama(Tohoku U), Susumu Ariki(Osaka U), Jun Tarui(UEC), Kazuhisa Seto(UEC)
Click to Continue ...speakers: Ketan Mulmuley and Joshua Grochow
14:00--18:15 (with 3 breaks)
18:30-- impromptu dinner party at Tamachi
(We plan to walk to a dinner place from the workshop
venue. Please note that dinner is not free of charge,
and you are kindly asked to come on time.)
|
3/14 - 17
| 平成24年度 第1回領域会議 & ELC Tokyo Complexity Workshop |
| Place : 品川プリンスホテル |
3/13
| Satellite Mini-Workshop, Shinagawa |
| Place : Kyoto Univ. Shinagawa Office |
| Mar13(Wed) Satellite Mini-Workshop, Shinagawa
venue: Kyoto Univ. Shinagawa Office, Intercity Shinagawa Bldg. A 27F, Shinagawa
http://www.kyoto-u.ac.jp/ja/tokyo-office http://goo.gl/aCgSE
registration not necessary; no participation fee; everybody is welcome
organizers: Yoshio Okamoto(UEC), Suguru Tamaki(Kyoto U), Jun Tarui(UEC)
Click to Continue ...each talk will have a 15-min break in the middle
10:30--12:15 David Zuckerman: Randomness Extraction: A Survey
12:15--13:40 lunch (on your own)
13:40--15:25 Ran Raz: Parallel Repetition of Two Prover Games: A Survey
15:25--15:45 break
15:45--17:30 Noam Nisan: Algorithmic Mechanism Design: Multi-unit Auctions
18:00-- impromptu dinner party at Shinagawa
(We plan to walk to a dinner place from the workshop
venue. Please note that dinner is not free of charge,
and you are kindly asked to come on time.)
|
2/27
| ELC Seminar (Michael Lampis) |
| Place : 東京大学(本郷キャンパス)工学部六号館235室 |
| Date: Wednesday 17:30-18:30, February 27th
Improved inapproximability for TSP: the role of bounded occurrence CSPs
Michail Lampis (KTH Royal Institute of Technology)
The Traveling Salesman problem is one of the most famous problems in
combinatorial optimization and its approximability is a huge open
Click to Continue ...problem. Though there have been recent breakthroughs on the
algorithmic side, until recently the best inapproximability constant
was only 220/219, due to Papadimitriou and Vempala. In this talk we
will sketch a much simpler reduction which achieves a slightly better
inapproximability bound. The main ingredient is inapproximable
constraint satisfaction problems where each variable only appears a
bounded number of times. We will discuss the role of expanders and
amplifier graphs in the inapproximability of such problems and outline
a simple (but hard to analyze) idea which allows us to obtain better
expander graphs using the probabilistic method, improving on a 25-year
old result by Bollobas. Finally, we will discuss whether it is
realistic to hope that further work in this direction might eventually
lead to a strong inapproximability result for TSP (spoiler: probably
not!).
問合せ先:河村(A01)
|
2/21
| ELC Seminar (A01) |
| Place : 東京大学(本郷キャンパス)理学部七号館214室 |
1/17
| ELC Mini-Workshop (C01) |
| Place : CELC |
| Workshop on Randomness and Computation (organized by ELC C01)
This is the first workshop for the C01 project team. Two foreign
collaborators of C01 team are invited and with them we will have
a mini workshop for discussing collaborations between theoretical
computer science and statistical physics.
Click to Continue ...Date: 2013 Jan. 17th
Time: 1:30 - 5:30
Place: Center for ELC at Tokyo Tech CIC, Tamachi
Talks: (the detail schedule will be determined at the workshop)
0. Opening: Brief introduction to C01 project
by Osamu Watanabe (Tokyo Inst. of Tech.)
1. The minimum vertex cover problem in random hypergraphs:
replica-symmetric solution and a leaf removal algorithm
by Koji Hukushima (Univ. of Tokyo)
2. Searching for witness of unsatisfiability for a random
3-SAT formula
by Haijun Zhou
3. Statistical mechanics approach to the sample complexity
of dictionary learning
by Yoshiyuki Kabashima (Tokyo Inst. of Tech.)
4. Where the really hard problems really are?
by Lenka Zdeborova (CNRS and Institut de Physique Theorique, CEA)
We may go somewhere nearby for eating/drinking after the
workshop.
Host: Osamu Watanabe (watanabe@is.titech.ac.jp)
|
2012年 | |
12/28
| ELC Seminar (河内亮周) |
| Place : CELC |
| タイトル: ACC^0回路のNEXPでの超多項式下界の解説
講師: 河内 亮周 (東工大)
場所: 計算限界研究センターセミナー室
http://www.al.ics.saitama-u.ac.jp/elc/?celc
関連論文:
[Wil13] Ryan Williams: Natural Proofs versus Derandomization, manuscript (available at R. Williams' website).
[Wil11] Ryan Williams: Non-uniform ACC Circuit Lower Bounds. IEEE Conference on Computational Complexity 2011: 115-125
Click to Continue ...[Wil10] Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. STOC 2010.
[IKW02] Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. 65(4): 672-694 (2002)
|
12/17 - 18
| ELC Mini-Workshop (C03) |
| Place : JR博多シティ9F第2,3会議室 |
| 会場:
JR博多シティ9F第3会議室(12/17),第2会議室(12/18)
アクセス:
http://www.jrhakatacity-eventspace.jp/access/index.html
また,17日19時より博多駅付近で懇親会を企画しています
Click to Continue ...(参加費4000-5000円程度).
参加希望の方は12月13日(木)までに畑埜
http://www.i.kyushu-u.ac.jp/~hatano/
までご連絡下さい.
※なお発表者の方は特に連絡のないかぎり参加を想定していますので,ご連絡は不要です.ご都合の悪い方はお知らせください.
スケジュール:
Dec 17 (mon) JR Hakata City 9F, Meeting Room 3
10:00 - 10:20
Eiji Takimoto (Kyushu University)
Opening address and some remarks on the mission of Group C03.
10:30 - 12:00 [Tutorial Talk]
Kei Uchizawa (Yamagata University)
Learning Algorithm and Circuit Lower Bounds
14:00 - 15:30
Kohei Hatano (Kyushu University)
Combinatorial Online Prediction using Offline Approximation Algorithms
Marco Cuturi (Kyoto University)
Transportation Distances and their Application in Machine Learning:
New Problems
15:45 - 17:15
Ayumi Shinohara (Tohoku University)
Revisiting minimum consistency problem for DFA, and on the maximum number
of runs in a string.
Ryo Yoshinaka (Kyoto University)
Distributional Learning of Context-Free Grammars
17:30 -
Kei Uchizawa (Yamagata University)
Output Patterns of Logic Circuits
19:00 - drinking session
Dec 18 (tue) JR Hakata City 9F, Meeting Room 2
10:00 - 11:30
Takayoshi Shoudai (Kyushu University)
Learning Unordered Tree Contraction Patterns in Polynomial Time
Koji Tsuda (Aist)
Loss Minimization of Power Distribution Networks with Binary Decision
Diagrams
11:30 - 12:00 (free discussion)
[Tutorial]
Speaker: Kei Uchizawa (Yamagata University)
Title: Learning Algorithm and Circuit Lower Bounds
Abstract:
In this talk, we mainly survey the following two papers concerning a
relationship between learning algorithms and circuit lower bounds:
(1) Efficient Learning Algorithms Yield Circuit Lower Bounds,
Journal of Computer and System Sciences, 75, 27-36, 2009.
(2) Learning DNFs and Circuits using Teaching Assistants,
In Proceedings of COCOON 2004, 188-197, 2004.
We then discuss future work and open problems along a line of research
given by the paper (2).
(1h30min)
Speaker: Kei Uchizawa (Yamagata University)
Title: Output Patterns of Logic Circuits
Abstract:
Consider any combinatorial circuit C of logic gates. We define
an output pattern of C for a circuit input x as a vector of the outputs
of the gates in C for x, and say that C has a number p of output patterns
if different p output patterns arise in C for the circuit inputs.
In this talk, we observe that the number of output patterns are strongly
related to another major complexity measure, size
(i.e., the number of gates), and then present some lower bounds on
the number of output patterns. We also give some dichotomy result on
a problem of counting output patterns of a simple logic circuit.
(45min)
Speaker: Ryo Yoshinaka (Kyoto University)
Title: Distributional Learning of Context-Free Grammars
Abstract:
In Grammatical Inference, intensive research on the learning of
regular languages has achieved a plenty of positive results so far.
It had been thought to be quite a hard task to learn a considerably
rich class of languages that handle context-free structures.
In these years, a new line of research on the learning of context-free
languages, called "distributional learning", has been proposed and has
produced several fruitful results.
Distributional learning algorithms model and exploit the distribution of
substrings in grammatical sentences.
This talk summarizes different approaches of distributional learning
and presents some open problems on the efficiency of the learning
algorithms.
(45min)
Speaker: Takayoshi Shoudai (Kyushu University)
Title: Learning Unordered Tree Contraction Patterns
in Polynomial Time
Abstract:
We present a concept of edge contraction-based tree-structured
patterns as a graph pattern suited to represent tree-structured data.
A tree contraction pattern (TC-pattern) is an unordered tree-structured
pattern common to a given tree-structured data, which is obtained by
merging every uncommon connected substructure into one vertex by
edge contraction. In this talk, in order to establish an algorithmic
foundation for the discovery of knowledge from tree-structured data,
we show that TC patterns are learnable in polynomial time.
(45min)
Speaker: Ayumi Shinohara (Tohoku University)
Title: Revisiting minimum consistency problem for DFA,
and on the maximum number of runs in a string.
Abstract:
We discuss two topics. The first one is motivated by a simple puzzle game
which we own created, and we are interested in the computational
complexity
to solve it. It is NP-hard in general, since it contains the minimum
consistency
problem for deterministic finite automata (MinCons(DFA)) as a special
case.
MinCons(DFA) is well-known to be NP-hard and hard to approximate.
We are trying to analyze the complexity for a special case, which
is also related to the problem of inferring graphs from walks.
The second topic is concerning with the combinatorial properties of
maximal repetitions (runs) in strings. We show a new lower bound of
maximal sum of exponents of runs in a string.
(45min)
Speaker: Kohei Hatano (Kyushu University)
Title: Combinatorial Online Prediction using Offline Approximation
Algorithms
Abstract:
We consider online prediction problems of combinatorial concepts.
Examples of such concepts include shortest pathes, permutations,
assignments, covers, and so on.
The goal of the online prediction algorithm is to compete with the best
fixed combinatorial concept in hindsight.
A generic approach to this problem is to design an "offline-online
converter", i.e.,
an online prediction algorithm using the corresponding offline
(approximation) algorithm as an oracle.
The current state-of-the art converter, however, is not efficient enough.
In this talk, we will discuss approaches to construct more efficient
offline-online converters.
(45min)
Speaker: Marco Cuturi (Kyoto University)
Title: Transportation Distances and their Application in Machine
Learning: New Problems
Abstract:
I will present in this talk two new research topics related to the
optimal transportation distance (also known as Earth Mover's or
Wasserstein) and its application in machine learning to compare
histograms of features.
I discuss first the ground metric learning problem, which is the
problem of tuning automatically the parameters of transportation
distances using labeled histogram data.
After providing some reminders on optimal transportation,
I will argue that learning transportation distances is akin
to learning an L1 distance on the simplex, namely a distance with
polyhedral level sets, and I will draw some parallels with Mahalanobis
distances, the L2 distance and elliptic level sets. I will then introduce
our algorithm (arXiv:1110.2306) and more recent extensions.
In the second part of my talk, I address the fact that transportation
distances are not Hilbertian by showing that they can be cast as
positive definite kernels through the "generating function trick".
We prove that the trick, which uses the generating function of the
transportation polytope to define a similarity - rather than focusing
exclusively on the optimal transport to define a distance - leads to
a positive definite kernel between histograms
(arXiv:1209.2655).
(45min)
Speaker: Koji Tsuda (Aist)
Title: Loss Minimization of Power Distribution Networks with
Binary Decision Diagrams
Abstract:
Determining loss minimum configuration in a distribution network is a
hard discrete optimization problem involving many variables.
Since more and more dispersed generators are installed on the demand side
of power systems and they are reconfigured frequently, developing
automatic approaches is indispensable for effectively managing a
large-scale distribution network. Existing fast methods employ local
updates that gradually improve the loss to solve such an optimization
problem. However, they finally get stuck at local minima, resulting in
arbitrarily poor results. In contrast, this paper presents a novel
optimization method that provides an error bound on the solution quality.
Thus, the obtained solution quality can be evaluated in comparison to
the global optimal solution. Instead of using local updates,
we construct a highly compressed search space using a binary decision
diagram and reduce the optimization problem to a shortest path-finding
problem.
Our method was shown to be not only accurate but also remarkably efficient;
Optimization of a large-scale model network with 468 switches was solved
in three hours with 1.56% relative error bound.
(45min)
|
12/17
| ELC Mini-Workshop (A02) |
| Place : CELC(計算限界研究センター, 田町) |
| 13:00〜17:00(終了時間は予定)
講演者(題目と講演順は仮)
- Skip Jordan(北大) 「Experimental Model Theory and Testing: Recent Directions」
- 吉田悠一(NII) 題目未定
- 脊戸和寿(電通大)「回路計算量と通信複雑さ」
- 玉置卓(京大) 「計算限界証明における障壁と性質検査アルゴリズム」
Click to Continue ...質問・ディスカッション重視で行います。
状況によってはセミナーの途中、あるいは最後にディスカッションを設定するかもしれません。
問合せは伊藤大雄(電通大)まで
|
12/10
| 電子情報通信学会 コンピュテーション研究会 ELCチュートリアル講演 |
| Place : 九州大学 |
12/7
| ELC Seminar (Manabu Hagiwara) |
| Place : Center for ELC |
| 産業技術総合研究所の萩原学氏をお招きして講演会を開催いたします.
線形計画法と符号理論の関係についてお話いただけるということですので
特に関係の深いチームの方々はご参加を検討いただけると幸いです.
よろしくお願いいたします.
日時:12月7日(金)16:00-17:00
※終了後に懇親会を予定しております.
Click to Continue ...場所:計算限界研究センターセミナー室
講演者:萩原学(産業技術総合研究所)
講演タイトル:
コンパクトグラフと線形計画法による置換符号
Compact Graph and Linear Programming for Permutation Codes
講演概要:
置換符号は符号理論の話題の一つである.
これまでこの符号は,電力線搬送通信向きとして研究されてきた.
この符号の特別なケースである,ランク変調と呼ばれる方式は,
近年,フラッシュメモリの誤り訂正に応用できる可能性が指摘され,
注目が高まっている.
本講演では,置換符号やランク変調のコンセプトについて解説する.
また,それらの誤り訂正アルゴリズムとして線形計画法を適用する為の,
置換符号とランク変調の構成法について議論したい.
Permutation codes are error-correcting codes and have been investigated
mainly for study of power line communication.
Rank modulation, which is a class of permutation codes, has recently
attracted since the modulation might be applicable to an
error-correction method for flash memories.
In this talk, basic notion and idea will be introduced and some previous
results on construction of the codes and the modulations suitable for
linear programming method as decoding algorithm will be discussed.
|
12/6
| ELC Mini-Workshop (暗号理論) |
| Place : Center for ELC |
| Program
1:30-2:00
Speaker: Hirotoshi Takebe (Tokyo Inst. Tech.)
Title: Symmetric-Key Encryption Scheme with Multi-Ciphertext Non-malleability
Abstract:
A standard notion of non-malleability
Click to Continue ...is that an adversary cannot forge a ciphertext $c'$
from a single valid ciphertext $c$ for which
a plaintext $m'$ of $c'$ is meaningfully
related to a plaintext $m$ of $c$.
The {\em multi-ciphertext non-malleability} is a
stronger notion; an adversary is allowed to
obtain multiple ciphertexts $c_1,c_2,...$
in order to forge $c'$.
We provide an efficient symmetric-key encryption scheme with
an information-theoretic version of
the multi-ciphertext non-malleability
in this paper by using $\ell$-wise almost independent
permutations of Kaplan, Naor, and Reingold.
2:00-2:30
Speaker: Vorapong Suppakitpaisarn (U. Tokyo)
Title: Generalized Analysis Methods for Efficiency of Representations for Elliptic Curve Scalar Multiplication
Abstract:
In this talk, we introduce the algorithmic analysis approach for
elliptic curve scalar multiplication implemented using various kinds
of number representations. Scalar multiplication is the bottleneck
operation of elliptic curve cryptography, and there are many works
proposed to speed-up the operation including the improvement on how we
represent the scalar. Many number representations, which are designed
to optimize the computation time in a specific type of elliptic curve
implementation, are too complicated to be analyzed using mathematical
approach. We devise the method based on dynamic programming scheme,
automatically-generated Markov chain, and the generic property of most
representations. Our focus in this presentation is the r-radix
representation for r > 2, which is practically used in pairing-based
cryptography. We found an interesting relationship between the memory
usage and the average speed of optimal scalar multiplication.
2:30-2:50
Break
2:50-3:50
Speaker: Takeshi Koshiba (Saitama Univ.)
Title: On Unidirectional Public Discussion in Secure Message Transmission
Abstract:
We consider the possibility and the limitation of secure message
transmission (SMT) in the "unidirectional" public discussion (PD)
model. Let epsilon be the privacy parameter and delta be the
reliability parameter, where smaller values are better.
[K-Sawada 2010] has shown that the privacy and the reliability
are not compatible in the SMT-PD model when only backward public
channel is avaiable.
Roughly speaking, epsilon + delta must be close to 1.
Also, we have shown that delta must be larger than approximately 1/2
when only foreward public channel is avaiable, while we provide an
upper-bound protocol achieving approximately delta < t/n, where
n is the number of channels and t |
11/30
| ERATO河原林巨大グラフプロジェクト & ELC合同講演会 (Arnab Bhattacharyya & Mikkel Thorup) |
| Place : キャンパスイノベーションセンター東京(東工大田町キャンパス) |
| ERATO河原林巨大グラフプロジェクトとELCの合同講演会を以下の要領で開催いたします.奮ってご参加下さい.
日時: 11/30(金) 15:30-17:30
場所: キャンパスイノベーションセンター東京 2階多目的室4
15:30-16:30
Speaker: Arnab Bhattacharyya (DIMACS/Rutgers)
Click to Continue ...Title: Every locally characterized affine-invariant property is testable
Abstract:
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a
property of functions on F^n that is closed under taking affine
transformations of the domain. We prove that all affine-invariant property
having local characterizations are testable. In fact, we show a
proximity-oblivious test for any such property P, meaning that there is a
test that, given an input function f, makes a constant number of queries to
f, always accepts if f satisfies P, and rejects with positive probability
if the distance between f and P is nonzero. More generally, we show that
any affine-invariant property that is closed under taking restrictions to
subspaces and has bounded complexity is testable.
We also prove that any property that can be described as the property of
decomposing into a known structure of low-degree polynomials is locally
characterized and is, hence, testable. For example, whether a function is a
product of two degree-d polynomials, whether a function splits into a
product of d linear polynomials, and whether a function has low rank are
all examples of degree-structural properties and are therefore locally
characterized.
Our results depend on a new Gowers inverse theorem by Tao and Ziegler for
low characteristic fields that decomposes any polynomial with large Gowers
norm into a function of low-degree non-classical polynomials. We establish
a new equidistribution result for high rank non-classical polynomials that
drives the proofs of both the testability results and the local
characterization of degree-structural properties.
Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar
Lovett.
16:30-17:30
Speaker: Mikkel Thorup (AT&T Labs Research)
Title: The Power of Tabulation Hashing
Abstract:
Randomized algorithms are often enjoyed for their simplicity, but the hash functions
used to yield the desired theoretical guarantees are often neither simple nor practical.
Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees.
The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting
of c characters. We initialize c tables T1,…,Tc mapping characters to random hash codes.
A key x=(x1,…,xc) is hashed to T1[x1]⊕⋯⊕Tc[xc], where ⊕ denotes xor. While this scheme is not
even 4-independent, we show that it provides many of the guarantees that are normally obtained
via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating
set intersection, and cuckoo hashing. We shall also discuss a twist to simple tabulation
that leads to extremely robust performance for linear probing with small buffers.
|
11/22
| Center for ELC opening |
| Place : Center for ELC (Tamachi) |
| We are planning to have a small opening event for
the Center for ELC (Tamachi office) as follows. If you are
interested in join us, please give a message to Ms. Kishimoto
(CELC staff) via email by the end of Oct.
Opening Event:
Nov. 22nd, 16:30 -
Click to Continue ... * some small seminar (very informal)
* maybe going out somewhere for dinner
Place: Tokyo Tech CIC 5F, 502
http://www.cictokyo.jp/access.html
Contact: kimiko(at)is.titech.ac.jp
|
11/12 - 13
| ELC Mini-Workshop (C02) |
| Place : 名古屋大学 |
| C02班による年次集会です.
日時: 11月12日~11月13日
場所: 名古屋大学
連絡先: 河内 亮周(http://www.is.titech.ac.jp/~kawachi/index-j.html)
Click to Continue ... |
11/9
| ELC Seminar (Kazuhisa Seto) 11/2との連続開催 |
| Place : 東京工業大学大岡山キャンパス西8号館E棟E1011 |
| Speaker: Kazuhisa Seto (The University of Electro-Communications)
Title: An Introduction to Circuit Complexity and Satisfiability Algorithms on Formulas
Time: 1:30pm -, November 9
Place: Room E1011, W8 building, Tokyo Institute of Technology
Abstract:
In this talk, we give a basic introduction to circuit complexity and
satisfiability algorithms on formulas. At first, we show Subbotovskaya's
Click to Continue ...technique for proving the lower bound of parity function on formulas.
Next, we introduce Santhanam's satisfiability algorithm for de morgan
formulas by using Subbotovskaya's technique. Finally, we give our
satisifiablity algorithm for formulas over the full binary basis by
extension of Santhanam's algorithm.
|
11/2
| ELC Seminar (Laszlo Egri, Yuichi Yoshida) 11/9 との連続開催 |
| Place : 東京工業大学大岡山キャンパス西8号館E棟E1011 |
| Time: 1:30pm -, November 2
Place: Room E1011, W8 building, Tokyo Institute of Technology
Speaker: Laszlo Egri (McGill Univ.)
Title: The Complexity of the List Homomorphism Problem for Graphs
Abstract:
We completely classify the computational complexity of the list
Click to Continue ...H-colouring problem for graphs (with possible loops) in combinatorial
and algebraic terms: for every graph H, the problem is either
NP-complete, NL-complete, L-complete or is first-order definable;
descriptive complexity equivalents are given as well via Datalog and
its fragments. Our algebraic characterisations match important
conjectures in the study of constraint satisfaction problems.
Speaker: Yuichi Yoshida (NII & PFI)
Title: An Algebraic Characterization of Testable Boolean CSPs
Abstract:
Given an instance I of a CSP, a tester for I distinguishes assignments satisfying I
from those which are far from any assignment satisfying I.
The efficiency of a tester is measured by its query complexity,
the number of variable assignments queried by the algorithm.
In this paper, we characterize the hardness of testing Boolean CSPs
in terms of the algebra generated by the relations used to form constraints.
In terms of computational complexity, we show that if a non-trivial Boolean CSP
is sublinear-query testable (resp., not sublinear-query testable), then the CSP is in NL
(resp., P-complete, ⊕L-complete or NP-complete) and that if a sublinear-query testable
Boolean CSP is constant-query testable (resp., not constant-query testable),
then counting the number of so- lutions of the CSP is in P (resp., #P-complete).
Also, we conjecture that a CSP instance is testable in sublinear time
if its Gaifman graph has bounded treewidth.
We confirm the conjecture when a near-unanimity operation is a polymorphism of the CSP.
Contact: Akinori Kawachi (Tokyo Institute of Technology)
|
10/28 - 29
| ELC Mini-Workshop (B02, B03) |
| Place : 秋保温泉 |
| 場所: 秋保温泉 ホテル瑞鳳
予定:
10月28日 13時~17時 話題提供セッション(9時から自由形式のDiscussion)
10月29日 9時~11時半 問題解決セッション
交通:
Click to Continue ...仙台駅からバスがあります。
ホテルの無料送迎バスはありますが、9時と15時(予約制)です。
宮城交通バス(仙台駅から55分、780円)をつかうか、
希望者多数の場合は(割り勘で)送迎バスを有料で出してもらいます。
参加希望の方は、下記情報を徳山豪まで9月10日までにご連絡ください。
氏名
所属
学生の場合は学年
到着予定時間
有料送迎バス(12時仙台駅発予定)を使いたいかどうか。
話題提供があれば、そのテーマ。 特になくてもOK
(話題は計算理論に関係すれば、COMPLEXITYに限定しませんが、
成果発表ではなく、問題提起が望ましいです。)
|
10/2
| ELC Seminar (Lance Fortnow) |
| Lance Fortnow 氏の短期間来日の機会に,氏の講演を中心に何人かの方に発表して頂くWSを企画しました.ぜひ,おいでください.
場所:東工大大岡山キャンパス 西8号館W棟10Fコラボレーションルーム
※道順は渡辺研のウェブのアクセスから
http://www.is.titech.ac.jp/~watanabe/lab/pukiwiki4lab/index.php?howtoget-jp
日時:10月2日(火)13時30分~18時頃
※終了後懇親会も予定しています.こちらは予約もあるので参加希望者は連絡して下さい
Click to Continue ...
ホスト:河内亮周 kawachi(at)is.titech.ac.jp
|
9/24 - 27
| 暗号理論秋学校 |
| Place : 河口湖セントビレッヂ |
9/24 - 26
| 計算量理論の秋学校 |
| Place : かんぽの宿 熱海 |
9/5 - 7
| ELC Mini-Workshop (B01) |
| Place : 京都大学 |
9/3
| 電子情報通信学会 コンピュテーション研究会 ELC招待講演 |
| Place : 法政大学 |
7/9
| ELC 発足準備会 |
| Place : 東京工業大学 |
| 詳細は、ELC ウェブサイトをご覧ください
|