Time  Details 

9:309:55  Reception 
9:5510:00  Opening 
10:0010:45 (45min) 
WingKin Sung (National University of Singapore)
Issues on Aligning Short Reads Generated by Next Generation Sequencing
Due to the advance in next generation sequencing, our genome can be sequenced using approximately US$1000. The cost is going to be reduced in the near future. It gives hope to have a cheap solution for personalize medicine. However, it is not an easy task to reconstruct a correct individual genome from such a big sequencing dataset. The main issue is the repeat regions in human genome, which make it difficult to position the sequencing reads on the human reference genome. In this talk, we will discuss issues and partial solutions to solve such a problem. 
10:4511:15 (30min) 
Keisuke Goto (FUJITSU LABORATORIES LTD.)
InPlace Initializable Arrays
Initializing all elements of a given array to a specified value is basic operation
that frequently appears in numerous algorithms and programs.
Initializable arrays are abstract arrays that support initialization
as well as reading and writing of any element of the array in constant worst case time.
On the word RAM model, we propose an inplace algorithm which implements an initializable array of length \(N\) with only 1 extra bit,
where \(w\) is the word size, and each element of the array can store an individual value of \(\ell \in \mathrm{O}(w)\) bits.
Our algorithm significantly improves upon the previous best algorithm [Navarro, CSUR 2014] using \(N+\ell+\mathrm{o}(N)\) extra bits.

11:1511:40 (25min) 
Kazuki Ishiyama (The University of Tokyo)
Practical Spaceefficient Data Structures for Highdimensional Orthogonal Range Searching
We consider the orthogonal range search problem.
In this problem, we are given a point set \(P\) in \(d\)dimensional space
and an orthogonal query region \(Q\), and return some information on \(P \cap Q\).
We focus on the counting query: count the number of points of \(P\) contained in \(Q\),
and the reporting query: report all points of \(P\) in \(Q\).
For \(2\)dimensional case, Bose et al. proposed a spaceefficient data structure
supporting the counting query in \(\mathrm{O}(\lg n / \lg \lg n)\) time
and the reporting query in \(\mathrm{O}(k \lg n / \lg \lg n)\) time,
where \(n\) is the number of points of \(P\) and \(k\) is the number of points
which are contained in \(Q\).
For highdimensional cases, the KDWtree [Okajima, Maruyama, ALENEX 2015]
and the data structure of [Ishiyama, Sadakane, DCC 2017] have been proposed.
However, they are not efficient for very large \(d\), the number of dimensions.
In our research, we propose practical spaceefficient data structures
for the problem.
They run fast when \(d'\), the number of dimensions used in queries, is
smaller than the data dimension \(d\).
This kind of queries are typical in database queries.

11:4013:00  Lunch 
13:0013:45 (45min) 
Ilan Newman (The University of Haifa)
Testing for Forbidden Order Patterns in an Array
We study testing of sequence properties that are defined by forbidden order patterns. An Order pattern of length \(k\) is defined by a permutation \(\pi = (\pi(1), \ldots ,\pi(k))\) of \(k\) elements. A sequence \(f: \{1,\ldots,n\} \rightarrow R\) of length \(n\) contains a pattern \(\pi\) if there is a subsequence of \(f\) in which the order of the elements in it is identical to the order defined by \(\pi\). Namely, there are indices \(i_1 < i_2 < \dots < i_k\), such that \(f(i_x) > f(i_y)\) whenever \(\pi(x) > \pi(y)\). If \(f\) does not contain \(\pi\), we say that \(f\) is \(\pi\)free. For example, for \(\pi = (2,1)\), the property of being \(\pi\)free is equivalent to being nondecreasing, i.e. monotone. For a fixed order pattern \(\pi\), of constant length \(k\), and input sequence \(f\) stored in an array, we consider the property testing problem of distinguishing the case that \(f\) is \(\pi\)free from the case that \(f\) differs in more than \(\epsilon n\) places from any \(\pi\)free sequence. We show the following results:
For all algorithms presented here, the running times are linear in their query complexity. This is a joint work with Deepak Rajendraprasad, Christian Sohler and Yuri Rabinovich. 
13:4514:15 (30min) 
Takeaki Uno (National Institute of Informatics)
Data Polishing for Data Abstraction
Data mining, particularly pattern mining and cluster mining, aims to
find interesting and characteristic local structures. In other
words,they are "abstracting" properties of the data. A difficulty of
the abstraction is on the modeling of abstracted structures; it is
hard to describe "what is abstracted" and "how to abstract". In simple
models, it is hard to avoid huge number of solutions that are quite
similar to each other. In this talk, we propose a new approach called
"data polishing" that takes an approach totally different from
existing approaches. The idea is to modify the data by feasible
hypothesis, so that ambiguities will be distinguished. The result is
fine, and even for graph visualization we can see many clusters
clearly, in SNS networks.

14:1514:40 (25min) 
Munehiko Sasajima (Kwansei Gakuin University)
Towards Development of Practically Efficient Property Testing  Experimental Study on
Practical Effectiveness of a Graph Partitioning Algorithm
In a constanttime property testing algorithm for big graphs, an appropriate partitioning method
for dividing the target graphs is required as its subroutine.
The authors implemented a graph partitioning algorithm based on an existing property testing algorithm
which assumes boundeddegree and minorfree graphs as its input,
and computational experiments were carried out for the graphs representing real networks such as powergrids,
social network services (SNS), and so on.
It is observed that our algorithm works well for planar graphs and those "close to" planar graphs.
For the scalefree graphs which contain vertices of high degree,
although our algorithm can divide target graph into intended size of subgraphs,
issues remain on controlling the number of edges bridging them.

14:4014:55  Break 
14:5515:40 (45min) 
Moritz Mühlenthaler (TU Dortmund University)
Solution Graphs of Combinatorial Problems
We consider solution graphs of combinatorial problems with respect to certain natural adjacency relations.
These graphs are typically too large to be stored explicitly.
We will give a brief overview of what is known about the complexity of the (st)connectivity problem on such graphs.
Furthermore, we will showcase some recent results on the stconnectivity problem in a particular class of solution graphs,
namely graphs on common independent sets of matroids.

15:4016:05 (25min) 
Takehiro Ito (Tohoku University)
Reachability on the Solution Space of Graph Colorings
It has been studied intensively from the algorithmic viewpoint to analyze the solution space of (vertex)colorings on a graph.
In this talk, we consider the problem of asking the reachability (stconnectivity) on the solution space,
that is, we wish to transform a given coloring into another given one by recoloring only a single vertex at a time,
while maintaining always proper coloring.

16:0516:10  Closing 
17:0019:00  Banquet 