###### Research Reports (Series C: Computer Science) †

Dept. of Math. and Comp. Sciences

#### Linguistic Regularities from Multiple Samples †

ID: C-283 (February,2016)

Author: Aleksandr Drozd and Satoshi Matsuoka

Email: alex@smg.is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/C/C-283.pdf

Abstract:

We present a simple method for better retrieval of analogical relations from word embeddings by learning from the multiple related pairs of words. We provide performance evaluation of the proposed method in comparison with the state-of-the-art approaches based on vector offset.

#### Intuitionistic fragment of the lambda mu calculus †

ID: C-282 (March, 2015)

Author: Naosuke Matsuda

Email: matsuda. naosuke (at) gmail. com

Document: http://www.is.titech.ac.jp/research/research-report/C/C-282.pdf

Abstract:

Parigot gave an elegant proof system "the lambda mu calculus" for
classical
logic,
and gave a correspondence between classical logic and some kind of program structures which the lambda calculus cannot capture.
Although the correspondence is due to the power of inference rules of the lambda mu calculus, some of those rules are admissible in some intuitionistic proof systems.
It therefore must be natural to ask whether it is possible to extend the correspondence between intuitionistic logic and program structures.
In this paper, we give a partial answer to this question by giving a natural subsystem of the lambda mu calculus which corresponds to intuitionistic logic and investigating it.

#### A PROOF THEORETIC STUDY ON INTUITIONISTIC TREE SEQUENT CALCULUS †

ID: C-281 (November, 2014)

Author: Naosuke Matsuda

Email: matsuda. naosuke (at) gmail. com

Document: http://www.is.titech.ac.jp/research/research-report/C/C-281.pdf

Abstract:

TLJ is a proof system for intuitionistic logic which has connections to
many other areas of computer science and mathematics.
In this paper, to make the base of those studies, we give a proof theoretic study on this system.

#### The First Eigenvalue of (c, d)-Regular Graph †

ID: C-280 (July, 2012)

Author: Kotaro Nakagawa and Hiroki Yamaguchi

Email: watanabe(at)is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/C/C-280.pdf

Abstract:

We show a phase transition of the first eigenvalue
of random (c,d)-regular graphs, whose instance of them consists of one vertex with degree c and the other vertices with degree d for c > d.
We investigate a reduction from the first eigenvalue analysis of a general (c,d)-regular graph to that of a tree, and prove that, for any fixed c and d, and for a graph G chosen from the set of all (c,d)-regular graphs with n vertices uniformly at random, the first eigenvalue of G is approximately max(d, c/sqrt{c-d+1}) with high probability.

#### Completeness of Hilbert-style axiomatization for the extended computation tree logic ECTL †

ID: C-279 (March, 2012)

Author: Ryo Kashima

Email: kashima(at)is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/C/C-279.pdf

Abstract:

We give a complete Hilbert-style axiomatization for ECTL,
which is an extension of the Computation Tree Logic (CTL) with a modal operator ``infinitely often along some path''.

#### A Projection-Based Method for Interactive Visual Exploration of Complex Graphs in A Three-Dimensional Space †

ID: C-278 (February, 2012)

Author: Masanori Takami, Hiroshi Hosobe, Ken Wakita

Email: wakita(at)is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/C/C-278.pdf

Abstract:

Complex networks can be hard for us human beings to conceptually grasp. We propose a new graph visualization method, which projects the static high-dimensional layout of a complex graph onto a two-, three-, or higher-dimensional space and allows viewers to explore the graph by interactively altering the way the layout is projected. The viewer could visually ``untangle'' what initially appeared to be a tight knot --- a simply impossible operation in conventional methods, with which you could just either zoom in or rotate. This is made possible by interpreting the user's action as a rotation command of the original graph in its original space and then re-projecting it onto the target space. This work extends Hosobe's previous work, whose target space could only be two dimensional, not three dimensional. The theoretical foundation of our technique and the lessons acquired from our early prototype are presented.

#### Applying DominoJ to GoF Design Patterns †

ID: C-277 (December, 2011)

Author: YungYu Zhuang and Shigeru Chiba

Email: Zhuang(at)csg.is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/C/C-277.pdf

Abstract:

In this report we study practical effectiveness of method slot, which is
a new language construct integrating events and methods. We use its language
implementation, DominoJ, to implement design patterns in the GoF book, and
found that 16 out of 23 patterns can benefit from it. Here we list down the
sample code in Java and DominoJ for the 16 patterns, and discuss the benefits.

#### Message Passing Algorithms for MLS-3LIN Problem †

ID: C-276 (October, 2011)

Author: Osamu Watanabe

Email: watanabe(at)is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/C/C-276.pdf

Abstract:

MLS-3LIN problem is
a problem of finding a most likely solution for a given system of perturbed 3LIN-equations under a certain planted solution model.
This problem is essentially the same as MAX-3XORSAT problem.
We investigate
the average-case performance of message passing algorithms for this problem, where input instances are generated under the planted
solution model with equation probability p and perturbation probability q.
For some variant of a typical message passing algorithm, we prove that p=Theta(1/(nln n)) is the threshold for the algorithm to work
w.h.p.for any fixed constant q<1/2.

#### Fourier Approximation under Non-uniform Distribution †

ID: C-275 (September, 2011)

Author: Hiroki Yamaguchi

Email: yamaguc6(at)is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/C/C-275.pdf

Abstract:

We propose a generalization of a PAC-learning algorithm known as the Low Degree Learning Algorithm for non-uniform distributions.
We show that our algorithm works under a non-uniform distribution D if the smallest eigenvalue of the Fourier coefficient matrix of
the distribution is not too small. We also show that this condition is guaranteed if there are few examples which appear with very
small probability under the distribution D.