Junichi Teruyama

A branching program is a well-studied model of computation and a representation for Boolean functions. It is a directed acyclic graph with a unique root node, some accepting nodes, and some rejecting nodes. Except for the accepting and rejecting nodes, each node has a label with a variable and each outgoing edge of the node has a label with a 0/1 assignment of the variable. The satisfiability problem for branching programs is, given a branching program with n variables and m nodes, to determine if there exists some assignment that activates a consistent path from the root to an accepting node. The width of a branching program is the maximum number of nodes at any level. The satisfiability problem for width-2 branching programs is known to be NP-complete. In this paper, we present a satisfiability algorithm for width-2 branching programs with n variables and cn nodes, and show that its running time is poly(n)·2^(1-µ(c))n, where µ(c)=1/2^{O(c log c)}. Our algorithm consists of two phases. First, we transform a given width-2 branching program to a set of some structured formulas that consist of AND and Exclusive-OR gates. Then, we check the satisfiability of these formulas by a greedy restriction method depending on the frequency of the occurrence of variables.

We present improved exponential time exact algorithms for Max SAT. Our algorithms run in time of the form 0 (2((1-mu(c))n)) for instances with n variables and m = cn clauses. In this setting, there are three incomparable currently best algorithms: a deterministic exponential space algorithm with mu(c) = 1/o(clog c) due to Dantsin and Wolpert (2006) [9], a randomized l3c) polynomial space algorithm with mu(c) =1/o(clog(3) c) and a deterministic polynomial space algorithm with it mu(c) = 1/(c(2) log(2) c) due to Sakai, Seto and Tamaki (2015) [30]. Our first result is a deterministic polynomial space algorithm with mu(c) = 1/o(clog c) that achieves the previous best time complexity without exponential space or randomization. Furthermore, this algorithm can handle instances with exponentially large weights and hard constraints. The previous algorithms and our deterministic polynomial space algorithm run super-polynomially faster than 2(n) only if m = O(n(2)). Our second results are deterministic exponential space algorithms for Max SAT with mu(c) =1/o((c log c)(2/3)) and for Max 3-SAT with mu(c) = 1/o(c(1/2)) that run super-polynomially faster than 2n when m = o(n(5/2)/log(5/2) n) and m = o(n(3)/ log(2) n) respectively. Our third result is a randomized exponential space algorithm for Max SAT with mu(c) = 1/o(c(1/2) log(3/2) c) that run super-polynomially faster than 2n when m = o(n(3)/ log(5) n). (C) 2017 Elsevier B.V. All rights reserved.

This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg n − 1.4427n + O(log n). For many efficient algorithms, the first n lg n term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is −1.3999 for the MergeInsertion sort. Our new value is −1.4106, narrowing the gap by some 25%. An important building block of our algorithm is “twoelement insertion,” which inserts two numbers A and B, A &lt B, into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach with the binary insertion.

We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in 2(1-Omega(1/log c))n time for instances with n variables and cn nodes.

We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with k+1/4 n(2) + O(k + n) swaps and provide a detailed analysis for k = 3. In addition, we give a more efficient recursive algorithm using 15/16 n(2) + O(n) swaps for k = 3.

We give efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows: We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n - i + 1. We can only swap balls between adjacent bins. How many swaps are needed to move all balls to the same numbered bins. For this problem, we design an efficient greedy algorithm with k+1/4n(2) + O(kn) swaps. As k and n increase, this approaches the lower bound of inverted right perpendicular((kn)(2))/(2k-1)inverted left perpendicular. In addition, we design a more efficient recursive algorithm using 15/16n(2) + O(n) swaps for the k = 3 case.

The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only "balanced" or "tilted" information and that we know the number k of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). In this paper, we study the quantum query complexity for this problem. Let Q(k, N) be the quantum query complexity of finding all k false coins from the N given coins. We show that for any k and N such that k < N/2, Q(k, N) = O(k(1/4)), contrasting with the classical query complexity, Omega (k log(N/k)), that depends on N. So our quantum algorithm achieves a quartic speed-up for this problem. We do not have a matching lower bound, but we show some evidence that the upper bound is tight: any algorithm, including our algorithm, that satisfies certain properties needs Omega(k(1/4)) queries. (C) 2012 Elsevier B.V. All rights reserved.

We investigate the following sorting problem: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n + 1 - i. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this problem the best known solution requires almost 4/5 n 2 swaps. In this paper, we show an algorithm which solves this problem using less than 2n 2/3 swaps. Since it is known that the lower bound of the number of swaps is ⌈(2n/2)/3⌉ = ⌈2n 2/3 - n/3⌉, our result is almost tight. Furthermore, we show that for n = 2 m + 1 (m ≥ 0) the algorithm is optimal. © 2012 National Institute of Informatics.

This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string S with at most queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove two lower bounds. The first one is a general lower bound of , which means we cannot achieve a query complexity of O(N 1∈-∈ε ) for any constant ε. The other one claims that if we cannot use queries of length roughly between logN and 3 logN, then we cannot achieve a query complexity of any sublinear function in N. © 2012 Springer-Verlag.

The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only "balanced" or "tilted" information and that we know the number k of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). In this paper, we study the quantum query complexity for this problem. Let Q(k, N) be the quantum query complexity of finding all k false coins from the N given coins. We show that for any k and N such that k < N/2, Q(k, N) = O(k(1/4)), contrasting with the classical query complexity, Omega(k log(N/k)), that depends on N. So our quantum algorithm achieves a quartic speed-up for this problem. We do not have a matching lower bound, but we show some evidence that the upper bound is tight: any algorithm, including our algorithm, that satisfies certain properties needs Omega(k(1/4)) queries.