トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS

Hakata Workshop;Summer Meeting 2018 の履歴(No.1)


九州大学 組合せ数学セミナー

Hakata Workshop; Summer Meeting 2018

~Discrete Mathematics and its Applications~

 

Our purpose of this meeting is giving an opportunity to make a speech and to communicate with researchers who study various fields not only Combinatorics.

Further information is available from the organizers below.

Organizers

Supported by

Date

June 16, 2018

Location

Seminar Room P (4F) in Reference Eki Higashi Building. 1-16-14 Hakata-Eki-Higashi, Hakata-Ku, Fukuoka City, 812-0013 (see http://www.re-rental.com/ , Google maps )

Program

SpeakerTitle
13:27--13:30Opening (Tetsuji Taniguchi)
13:30-14:10Yota Otachi (TKumamoto University) Space-efficient algorithms for longest increasing subsequence
14:20-15:00Yuta Watanabe (National Institute of Technology, Ube college) Association schemes on the Schubert cells of a Grassmannian
15:10-15:50Hajime Tanaka(Tohoku University)The Terwilliger algebra with respect to an edge of a bipartite 2-homogeneous distance-regular graph
16:00-16:40Akihiro Munemasa (Tohoku University) TBA
16:50-17:30Kenichi Arai(Nagasaki University) Computer-based Evaluation of Cryptographic Protocol Security
17:30--17:35Closing(Yoshihiro Mizoguchi)

Abstract

Yota Otachi

  • Title: Space-efficient algorithms for longest increasing subsequence
  • Abstract: Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(n log n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For sqrt(n) <= s <= n, we present algorithms that use O(s log n) bits and O(1/s n^2 log n) time for computing the length of a longest increasing subsequence, and O(1/s n^2 log^2 n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

Yuta Watanabe

  • Title: Association schemes on the Schubert cells of a Grassmannian
  • Abstract: Let $\mathbb{F}$ be any field. The Grassmannian $\mathrm{Gr}(m,n)$ is the set of $m$-dimensional subspaces in $\mathbb{F}^n$, and the general linear group $\mathrm{GL}_n(\mathbb{F})$ acts transitively on it. The Schubert cells of $\mathrm{Gr}(m,n)$ are the orbits of the Borel subgroup $B \subset \mathrm{GL}_n(\mathbb{F})$ on $\mathrm{Gr}(m,n)$. We consider the association scheme on each Schubert cell defined by the $B$-action and show it is symmetric and it is the generalized wreath product of one-class association schemes, which was introduced by R.~A.~Bailey in European Journal of Combinatorics 27 (2006) 428--435.

Hajime Tanaka

  • Title: The Terwilliger algebra with respect to an edge of a bipartite 2-homogeneous distance-regular graph
  • Abstract: For a bipartite Q-polynomial distance-regular graph, it follows that the Terwilliger algebra with respect to an edge behaves in a way very similar to the ordinary Terwilliger algebra with respect to a vertex. In particular, we show that the structure of the Terwilliger algebra with respect to an edge of a bipartite 2-homogeneous distance-regular graph is completely determined from the intersection array.

Akihiro Munemasa

  • Title: TBA
  • Abstract: TBA

Kenichi Arai

  • Title: Computer-based Evaluation of Cryptographic Protocol Security
  • Abstract: The complexity of cryptographic protocols has increased in recent years in response to various requirements. This increase in complexity makes the evaluation of cryptographic protocol security difficult and increases the likelihood of human error. For this reason, the problem has arisen that many studies contain evaluation errors. This study focuses on the effectiveness of computer-based evaluation of cryptographic protocol security and aims to realize a method for rigorously conducting such evaluations. In this talk, we will introduce our recent study results.