Abstract:
For a set $A$ of $n$ people and a set $B$ of $m$ items, with each person having a preference list that ranks all items from most wanted to least wanted, we consider the problem of matching every person with a unique item. A matching $M$ is called $\epsilon$-popular if for any other matching $M'$, the number of people who prefer $M'$ to $M$ is at most $\epsilon n$ plus the number of those who prefer $M$ to $M'$. In 2006, Mahdian showed that when randomly generating people's preference lists, if $m/n > 1.42$, then a 0-popular matching exists with $1-o(1)$ probability; and if $m/n < 1.42$, then a 0-popular matching exists with $o(1)$ probability. The ratio 1.42 can be viewed as a transition point, at which the probability rises from asymptotically zero to asymptotically one, for the case $\epsilon=0$. In this paper, we introduce an upper bound and a lower bound of the transition point in more general cases. In particular, we show that when randomly generating each person's preference list, if $\alpha(1-e^{-1/\alpha}) > 1-\epsilon$, then an $\epsilon$-popular matching exists with $1-o(1)$ probability (upper bound); and if $\alpha(1-e^{-(1+e^{1/\alpha})/\alpha}) < 1-2\epsilon$, then an $\epsilon$-popular matching exists with $o(1)$ probability (lower bound).

Abstract:
We propose an algorithm of generating hard instances for the Satisfying Assignment Search Problem (in short, SAT). The algorithm transforms instances of the integer factorization problem into SAT instances efficiently by using the Chinese Remainder Theorem. For example, it is possible to construct SAT instances with about 5,600 variables that is as hard as factorizing 100 bit integers.

Abstract:
When we try to solve a system of linear equations, we can consider a simple iterative algorithm in which an equation including only one variable is chosen at each step, and the variable is fixed to the value satisfying the equation. The dynamics of this algorithm is captured by the peeling algorithm. Analyses of the peeling algorithm on random hypergraphs are required for many problems, e.g., the decoding threshold of low-density parity check codes, the inverting threshold of Goldreich's pseudorandom generator, the load threshold of cuckoo hashing, etc. In this work, we deal with random hypergraphs including superlinear number of hyperedges, and derive the tight threshold for the succeeding of the peeling algorithm. For the analysis, Wormald's method of differential equations, which is commonly used for analyses of the peeling algorithm on random hypergraph with linear number of hyperedges, cannot be used due to the superlinear number of hyperedges. A new method called the evolution of the moment generating function is proposed in this work.

Abstract:
For a set A of n applicants and a set I of m items, we consider a problem of computing a matching of applicants to items, i.e., a function M mapping A to I; here we assume that each applicant $x \in A$ provides a preference list on items in I. We say that an applicant $x \in A$ prefers an item p than an item q if p is located at a higher position than q in its preference list, and we say that x prefers a matching M over a matching M' if x prefers M(x) over M'(x). For a given matching problem A, I, and preference lists, we say that M is more popular than M' if the number of applicants preferring M over M' is larger than that of applicants preferring M' over M, and M is called a popular matching if there is no other matching that is more popular than M. Here we consider the situation that A is partitioned into $A_{1},A_{2},...,A_{k}$, and that each $A_{i}$ is assigned a weight $w_{i}>0$ such that w_{1}>w_{2}>...>w_{k}>0$. For such a matching problem, we say that M is more popular than M' if the total weight of applicants preferring M over M' is larger than that of applicants preferring M' over M, and we call M an k-weighted popular matching if there is no other matching that is more popular than M. In this paper, we analyze the 2-weighted matching problem, and we show that (lower bound) if $m/n^{4/3}=o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} \geq 2w_{2}$ has a 2-weighted popular matching with probability o(1); and (upper bound) if $n^{4/3}/m = o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} \geq 2w_{2}$ has a 2-weighted popular matching with probability 1-o(1).

Abstract:
We performed corrosion case study and corrosion tests to assess the corrosion resistance of stainless steel type 304 pipes in tap water and hot water facilities. Circulating test equipment used for corrosion tests and two types of sample, plates and straight pipe specimens, were examined under different conditions of residual chlorine concentration in the test water. The results of case study analysis indicated that high degrees of pitting corrosion occurred on straight pipes with inner diameter < 50 mm. The results of corrosion tests showed that the residual chlorine concentration around the pitting corrosion of stainless steel type 304 was greater than 0.3 mg/L in the plate, regardless of the remaining chlorine concentration in the straight pipe specimens. These results suggest that straight pipes have higher corrosion susceptibility because of bending during production.

Abstract:
For a rigorous quantum simulation of nonadiabatic dynamics of electrons and nuclei, knowledge of not only first-order but also second-order nonadiabatic couplings (NAC), is required. Here we propose a method to efficiently calculate second-order NAC from time-dependent density functional theory (TDDFT), on the basis of the Casida ansatz adapted for the computation of first-order NAC, which has been justified in our previous work and can be shown to be valid for calculating second-order NAC between ground state and singly excited states within the Tamm-Dancoff approximation. Test calculations of second-order NAC in the immediate vicinity of Jahn-Teller and Renner-Teller intersections show that calculation results from TDDFT, combined with modified linear response theory, agree well with the prediction from the Jahn-Teller / Renner-Teller models. Contrary to the diverging behavior of first-order NAC near all types of intersection points, the Cartesian components of second-order NAC are shown to be negligibly small near Renner-Teller glancing intersections, while they are significantly large near the Jahn-Teller conical intersections. Nevertheless, the components of second-order NAC can cancel each other to a large extent in Jahn-Teller systems, indicating the background of neglecting second-order NAC in practical dynamics simulations. On the other hand, it is shown that such a cancellation becomes less effective in an elliptic Jahn-Teller system and thus the role of second-order NAC needs to be evaluated in the rigorous framework. Our study shows that TDDFT is promising to provide accurate data of NAC for full quantum mechanical simulation of nonadiabatic processes.

Abstract:
A methodology to analyze the properties of the first (largest) eigenvalue and its eigenvector is developed for large symmetric random sparse matrices utilizing the cavity method of statistical mechanics. Under a tree approximation, which is plausible for infinitely large systems, in conjunction with the introduction of a Lagrange multiplier for constraining the length of the eigenvector, the eigenvalue problem is reduced to a bunch of optimization problems of a quadratic function of a single variable, and the coefficients of the first and the second order terms of the functions act as cavity fields that are handled in cavity analysis. We show that the first eigenvalue is determined in such a way that the distribution of the cavity fields has a finite value for the second order moment with respect to the cavity fields of the first order coefficient. The validity and utility of the developed methodology are examined by applying it to two analytically solvable and one simple but non-trivial examples in conjunction with numerical justification.

Abstract:
A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely oriented digraphs), and it has been known for more than half a century that all tournaments have at least one king [Lan53]. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of the semifeasible sets [HNP98,HT05] and in the study of the complexity of reachability problems [Tan01,NT02]. In this paper, we study the complexity of recognizing kings. For each succinctly specified family of tournaments, the king problem is known to belong to $\Pi_2^p$ [HOZZ]. We prove that this bound is optimal: We construct a succinctly specified tournament family whose king problem is $\Pi_2^p$-complete. It follows easily from our proof approach that the problem of testing kingship in succinctly specified graphs (which need not be tournaments) is $\Pi_2^p$-complete. We also obtain $\Pi_2^p$-completeness results for k-kings in succinctly specified j-partite tournaments, $k,j \geq 2$, and we generalize our main construction to show that $\Pi_2^p$-completeness holds for testing k-kingship in succinctly specified families of tournaments for all $k \geq 2$.

Abstract:
We consider the problem of classifying graphs using graph kernels. We define a new graph kernel, called the generalized shortest path kernel, based on the number and length of shortest paths between nodes. For our example classification problem, we consider the task of classifying random graphs from two well-known families, by the number of clusters they contain. We verify empirically that the generalized shortest path kernel outperforms the original shortest path kernel on a number of datasets. We give a theoretical analysis for explaining our experimental results. In particular, we estimate distributions of the expected feature vectors for the shortest path kernel and the generalized shortest path kernel, and we show some evidence explaining why our graph kernel outperforms the shortest path kernel for our graph classification problem.