垂井 淳
| 情報・ネットワーク工学専攻 | 准教授 |
| Ⅰ類（情報系） | 准教授 |
研究者情報
学位
経歴
研究活動情報
論文
- Space-Efficient Algorithms for Longest Increasing Subsequence
M. Kiyomi; H. Ono; Y. Otachi; P. Schweitzer; J. Tarui
Proceedings of STACS2018: 35th International Symposium on Theoretical Aspects of Computer Science, 掲載ページ 44:1-44:15, 出版日 2018年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Depth-First Search Using O(n) Bits
Tetsuo Asano; Taisuke Izumi; Masashi Kiyomi; Matsuo Konagaya; Hirotaka Ono; Yota Otachi; Pascal Schweitzer; Jun Tarui; Ryuhei Uehara
ALGORITHMS AND COMPUTATION, ISAAC 2014, SPRINGER-VERLAG BERLIN, 8889巻, 掲載ページ 553-564, 出版日 2014年, 査読付, We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space.
研究論文（国際会議プロシーディングス）, 英語 - Learning Boolean functions in AC(0) on attribute and classification noise-Estimating an upper bound on attribute and classification noise
Akinobu Miyata; Jun Tarui; Etsuji Tomita
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 412巻, 35号, 掲載ページ 4650-4660, 出版日 2011年08月, 査読付, We study a procedure for estimating an upper bound of an unknown noise factor in the frequency domain. A learning algorithm using a Fourier transformation method was originally given by Linial, Mansour and Nisan. While Linial, Mansour and Nisan assumed that the learning algorithm estimates Fourier coefficients from noiseless data, Bshouty, Jackson, and Tamon, and also Ohtsuki and Tomita extended the algorithm to ones that are robust for noisy data. The noise process that we consider is as follows: for an example < x, f (x)>, where x is an element of {0, 1}(n), f(x) is an element of {-1, 1}, each bit of x and f (x) gets flipped independently with probability eta during a learning process. The previous learning algorithms for noisy data all assume that the noise factor eta or an upper bound of eta is known in advance. The learning algorithm proposed in this paper works without this assumption. We estimate an upper bound of the noise factor by evaluating a noisy power spectrum in the frequency domain and by using a sampling trick. Combining this procedure with Ohtsuki and Tomita's algorithm, we obtain a quasi-polynomial-time learning algorithm that can cope with noise without knowing any information about the noise in advance. (C) 2011 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds
Kazuyuki Amano; Jun Tarui
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 412巻, 18号, 掲載ページ 1646-1651, 出版日 2011年04月, 査読付, A Boolean function on n variables is k-mixed if any two distinct restrictions fixing the same set of k variables induce distinct functions on the remaining n - k variables. We give an explicit construction of an (n - o(n))-mixed Boolean function whose circuit complexity over the basis U(2) is 5n + o(n). This shows that a lower bound method for the size of a U2 circuit that applies to arbitrary well-mixed functions, which yields the largest known lower bound of 5n - o(n) for the U(2)-circuit size (Mama, Lachish, Morizumi and Raz [STOC01, MFCS02]), has reached the limit. (C) 2010 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Smallest formulas for the parity of 2(k) variables are essentially unique
Jun Tarui
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 411巻, 26-28号, 掲載ページ 2623-2627, 出版日 2010年06月, 査読付, For n = 2(k), we know that the size of a smallest AND/OR/NOT formula computing the Boolean function Parity(x(1), ..., x(n)) = Odd(x(1), ... , x(n)) is exactly n(2): For any n, it is at least n(2) by the classical Khrapchenko bound, and for n = 2(k) we easily obtain a formula of size n(2) by writing and recursively expanding
Odd(x(1), ..., x(n)) = [Odd(x(1), ..., x(n/2)) boolean AND Even(x(n/2+1), ..., x(n))]
boolean OR [Even(x(1), ..., x(n/2)) boolean AND Odd(x(n/2+1), ... , x(n))].
We show that for n = 2(k) the formula obtained above is an essentially unique one that computes Parity(x(1), ... , x(n)) with size n(2). In the equivalent framework of the Karchmer-Wigderson communication game, our result means that an optimal protocol for the parity of 2(k) variables is essentially unique. (C) 2010 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Negation-Limited Complexity of Parity and Inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMICA, SPRINGER, 54巻, 2号, 掲載ページ 256-267, 出版日 2009年06月, 査読付, In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. We give improved lower bounds for the size (the number of AND/OR/NOT) of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x(1),..., x(n) and outputs (sic)x(1),..., (sic)x(n). We show that: (a) for n = 2(r) - 1, circuits computing Parity with r - 1 NOT gates have size at least 6n - log(2)(n + 1) - O(1), and (b) for n = 2(r) - 1, inverters with r NOT gates have size at least 8n - log(2)(n + 1) - O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x(1) >= ... >= x(n). For an arbitrary r, we completely determine the minimum size. It is 2n - r - 2 for odd n and 2n - r - 1 for even n for inverted right perpendicularlog(2)(n+ 1)inverted left perpendicular - 1 <= r <= n/2, and it is left perpendicular3n/2right perpendicular - 1 for r >= n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n - 3r for inverted right perpendicularlog(2)(n+ 1)inverted left perpendicular <= r <= n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments in a somewhat novel way.
研究論文（学術雑誌）, 英語 - Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences
H. Morizumi; J. Tarui
Theoretical Computer Science. DOI:10.1016/j.tcs.2008.10.030, 410巻, 11号, 掲載ページ 1054-1060, 出版日 2009年, 査読付
研究論文（学術雑誌）, 英語 - On the minimum number of completely 3-scrambling permutations
Jun Tarui
DISCRETE MATHEMATICS, ELSEVIER SCIENCE BV, 308巻, 8号, 掲載ページ 1350-1354, 出版日 2008年04月, 査読付, A family P = {pi(1),.....pi(q)} of permutations of [n]= {1,.....n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Furedi, Random Struct Algor 96] if for any distinct k points x(1),.....x(k) epsilon [n], permutations pi(i)'s in P produce all k! possible orders on pi(i)(x(1)),....pi(i)(x(k)). Let N*(n, k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Furedi for comparison.
2/log(2)(e) n <= N* (n, 3) <= 2 log(2)n + (1 + o(1)) log(2) log(2) n.
We also prove the existence of lim(n ->infinity) N* (n, 3)/log(2) n = c(3). Determining the value c(3) and proving the existence of lim(n ->infinity) N* (n, k)/log(2) n = c(k) for k >= 4 remain open. (C) 2007 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - A well-mixed function with circuit complexity 5n +/- o(n): Tightness of the Lachish-Raz-type bounds
Kazuyuki Amano; Jun Tarui
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4978巻, 掲載ページ 342-+, 出版日 2008年, 査読付, A Boolean function on n variables is called k-mixed if for any two different restrictions fixing the same set of k variables must induce different functions on the remaining n - k variables. In this paper, we give an explicit construction of an n - o(n)-mixed Boolean function whose circuit complexity over the basis U-2 is 5n + o(n). This shows that a lower bound method on the size of a U-2-circuit that uses the property of k-mixed, which gives the current best lower bound of 5n - o(n) on a U2-circuit size (Iwama, Lachish, Morizurni and Raz [STOC '01, MFCS '02]), has reached the limit.
研究論文（国際会議プロシーディングス）, 英語 - Smallest formulas for parity of 2(k) variables are essentially unique
Jun Tarui
COMPUTING AND COMBINATORICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5092巻, 掲載ページ 92-99, 出版日 2008年, 査読付, For n = 2(k), we know that the size of a smallest AND/OR/ NOT formula computing the Boolean function Parity(x(1),...,x(n)) = Odd(x(1),...,x(n)) is exactly n(2) : For any n, it is at least n(2) by classical Khrapchenko's bound, and for n = 2(k) we easily obtain a formula of size n(2) by writing and recursively expanding
Odd(x(1),....,x(n)) = [Odd(x(1),...,x(n/2)) boolean AND Even(x(n/2+1),...,x(n))] boolean OR [Even(x(1),...,x(n/2)) boolean AND Odd(x(n/2+1),...,x(n))].
w We show that for n = 2(k) the formula obtained above is an essentially unique one that computes Parity(x(1),...,x(n)) with size n(2). In the equivalent framework of the Karchmer-Wigderson communication game, our result means that an optimal protocol for Parity of 2(k) variables is essentially unique.
研究論文（国際会議プロシーディングス）, 英語 - Reductions for Monotone Boolean Circuits
K. Iwama; H. Morizumi; J. Tarui
Theoretical Computer Science., 408巻, 掲載ページ 208-212, 出版日 2008年, 査読付
研究論文（学術雑誌）, 英語 - Linear-size log-depth negation-limited inverter for k-tonic binary sequences
Hiroki Morizumi; Jun Tarui
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4484巻, 掲載ページ 605-+, 出版日 2007年, 査読付, A zero-one sequence x(1) ,..., x(n) is k-tonic if the number of i's such that x(i) not equal x(i+i) is at most k. The notion generalizes well-known bitonic sequences. In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. In this context, the study of inverters, i.e., circuits with inputs x(1),..., x(n) and outputs -x(1),...,-x(n) is fundamental since an inverter with r NOTs can be used to convert a general circuit to one with only r NOTs. In particular, if linear-size log-depth inverter with r NOTs exists, we do not lose generality by only considering circuits with at most r NOTs when we seek superlinear size lower bounds or superlogarithmic depth lower bounds. Markov [JACM1958] showed that the minimum number of NOT gates necessary in an n-inverter is [log(2)(n + 1)]. Beals, Nishino, and Tanaka [SICOMP98-STOC95] gave a construction of an n-inverter with size O(n log n), depth O(log n), and [log(2)(n + 1)] NOTs. We give a construction of circuits inverting k-tonic sequences with size O ((log k) n) and depth O (log k log log n + log n) using log(2) n+log(2) log(2) log(2) n+O (1) NOTs. In particular, for the case where k = O(1), our k-tonic inverter achieves asymptotically optimal linear size and logarithmic depth. Our construction improves all the parameters of the k-tonic inverter by Sato, Amano, and Maruoka [COCOON06] with size O(kn), depth O(k log(2) n), and O(k log n) NOTs. We also give a construction of k-tonic sorters achieving linear size and logarithmic depth with log(2) log(2) n+log(2) log(2) log(2) n+O(1) NOT gates for the case where k = O(1). The following question by Turin remains open: Is the size of any depth-O(log n) inverter with O(log n) NOT gates superlinear?
研究論文（国際会議プロシーディングス）, 英語 - Finding a duplicate and a missing item in a stream
Jun Tarui
Theory and Applications of Models of Computation, Proceedings, SPRINGER-VERLAG BERLIN, 4484巻, 掲載ページ 128-135, 出版日 2007年, We consider the following problem in a stream model: Given a sequence a = < a(1), a(2),..., a(m)> wich each a(i) is an element of [n] = {1,..., n} and m > n, find a duplicate in the sequence, i.e., find some d = a(i) = a, with i not equal l by using limited s bits of memory and r passes over the input sequence. In one pass an algorithm reads the input sequence a in the order a(1), a(2,)..., a(m). Since m > n, a duplicate exists by the pigeonhole principle. Muthukrishnan [Mu05a], [Mu05b] has posed the following question for the case where m = n + 1: For s = 0 (log n), is there a solution with a constant number of passes? We have described the problem generalizing Muthukrishnan's question by taking the sequence length m as a parameter. We give a negative answer to the original question by showing the following: Assume that m = n + 1. A streaming algorithm with O (log n) space requires Omega (log n / log log n) passes; a k-pass streaming algorithm requires Omega(n(1/(2k-1))) space. We also consider the following problem of finding a missing item: Assuming that n < m, find x is an element of [m] such that x not equal a(j) for 1 <= j <= n. The same lower bound applies for the missing-item finding problem. The proof is a simple reduction to the communication complexity of a relation. We also consider one-pass algorithms and exactly determine the minimum space required. Interesting open questions such as the following remain. For the number of passes of algorithms using O(log n) space, show an w(1) lower bound (or an O(1) upper bound) for: (1) duplicate finding for m = 2n, (2) missing-item finding for m = 2n, and (3) the case where we allow Las-Vegas type randomization for m = n + 1.
研究論文（国際会議プロシーディングス）, 英語 - Negation-limited complexity of parity and inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4288巻, 掲載ページ 223-+, 出版日 2006年, 査読付, We give improved lower bounds for the size of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x(1),...,x(n) and outputs -x(1),...,-x(n). We show that (1) For n = 2(r) - 1, circuits computing Parity with r - 1 NOT gates have size at least 6n - log(2)(n + 1) - O(1) and (2) For n = 2(r) - 1, inverters with r NOT gates have size at least 8n - log(2)(n + 1) - O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x(1) >= ... >= x(n). For an arbitrary r, we completely determine the minimum size. For odd n, it is 2n - r - 2 for [log(2)(n + 1)] - 1 <= r <= n/2, and it is [3/2 n] - 1 for r >= n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n - 3r for [log(2)(n + 1)] <= r <= n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negat ion-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments.
研究論文（国際会議プロシーディングス）, 英語 - On the Minimum Number of Completely 3-Scrambling Permutations
J. Tarui
Proc. of EuroComb05: European Conference on Combinatorics, Graph Theory and Applications, Discrete Mathematics & Theoretical Computer Science Conference Volume AE., 掲載ページ 351-356, 出版日 2005年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Monotone Boolean Functions with s Zeros Farthest from Threshold Functions
K. Amano; J. Tarui
Proc. of EuroComb05: European Conference on Combinatorics, Graph Theory and Applications, Discrete Mathematics & Theoretical Computer Science Conference Volume AE., 掲載ページ 11-16, 出版日 2005年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Constructing families of epsilon-approximate k-wise independent permutations
T Itoh; Y Takei; J Tarui
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E87A巻, 5号, 掲載ページ 993-1003, 出版日 2004年05月, 査読付, The notion of k-wise independent permutations has several applications. From the practical point of view, it often suffices to consider almost (i.e., epsilon-approximate) k-wise independent permutation families rather than k-wise independent permutation families, however, we know little about how to construct families of epsilon-approximate k-wise independent permutations of small size. For any n > 0, let S-n be the set of all permutations on {0, 1,...,n - 1}. In this paper, we investigate the size of families of E-approximate k-wise independent permutations and show that (1) for any constant epsilon greater than or equal to 0, if a family F subset of or equal to S-n of permutations is epsilon-approximate k-wise independent, then \F\ greater than or equal to n(n - 1)(...)(n - k + 1) if epsilon < 1; \F\ greater than or equal to {n(n - 1) (. . .) (n - k + 1)}/(1 + epsilon) otherwise; (2) for any constant 0 < \F\ less than or equal to 1, there exists a family F subset of or equal to S-n of epsilon-approximate k-wise independent permutations such that \F\ = O((kln n)/(epsilon2) (n - 1) (. . .) (n - k + 1)); (3) for any constant epsilon > 0 and any n = p(m) with p prime, it is possible to construct a polynomial time samplable family F subset of or equal to S-n of epsilon-approximate pairwise independent permutations such that \F\ = O(n(n - 1)/epsilon): (4) for any constant epsilon > 0 and any n = p(m) with p prime, it is possible to construct a polynoinial time samplable family \F\ subset of or equal to S-n of epsilon-approxiniate 3-wise independent permutations such that \F\ = O(n(n- 1)(n - 2)/epsilon). Our results are derived by combinatorial arguments, i.e., probabilistic methods and linear algebra methods.
研究論文（学術雑誌）, 英語 - Learning Boolean functions in AC(0) on attribute and classification noise
A Miyata; J Tarui; E Tomita
ALGORITHMIC LEARNING THEORY, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 3244巻, 掲載ページ 142-155, 出版日 2004年, Linial, Mansour and Nisan introduced a learning algorithm of Boolean functions in AC(0) under the uniform distribution. Following their work, Bshouty, Jackson and Tamon, also Ohtsuki and Tomita extended the algorithm to one that is robust for noisy data. The noise process we are concerned here is as follows: for an example <x, f(x)>(x is an element of {0, 1}(n), f(x) is an element of {-1, 1}), each bit of the vector x and the f(x) are obliged to change independently with probability eta during a learning process. Before our present paper, we were on the assumption that the correct noise rate 77 or its upper bound is known in advance. In this paper, we eliminate the assumption. We estimate an upper bound of the noise rate by evaluating noisy power spectrum on the frequency domain by using a sampling trick. Thereby, by combining this procedure with Ohtsuki et al.'s algorithm, we obtain a quasipolynomial time learning algorithm that can cope with noise without knowing any information about noise in advance.
研究論文（学術雑誌）, 英語 - On the negation-limited circuit complexity of merging
K Amano; A Maruoka; J Tarui
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 126巻, 1号, 掲載ページ 3-8, 出版日 2003年03月, 査読付, A negation-limited circuit is a combinational circuit that consists of AND, OR gates and a limited number of NOT gates. In this paper, we investigate the complexity of negation-limited circuits. The (n,n) merging function is a function that merges two presorted binary sequences x(1) less than or equal to (. . .) less than or equal to x(n) and y(1) less than or equal to (. . .) less than or equal to y(n) into a sequence z(1) less than or equal to . . . less than or equal to z(2n). We prove that the size complexity of the (n, n) merging function with t = (log(2)log(2) n - a) NOT gates is Theta(2(a)n). (C) 2002 Elsevier Science B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - On the Sample Size of k-restricted Min-Wise Independent Permutations and Other k-Wise Distributions
T. Itoh; Y. Takei; J. Tarui
STOC03: Proc. of the 35th Annual ACM Symposium on Theory of Computing, ACM Press. DOI: 10.1145/780542.780645, Network Operation Center,Tokyo Institute of Technology, 3巻, 1号, 掲載ページ 710-719, 出版日 2003年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - A nearly linear size 4-min-wise independent permutation family by finite geometries
J Tarui; T Itoh; Y Takei
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION, SPRINGER-VERLAG BERLIN, 2764巻, 掲載ページ 396-408, 出版日 2003年, Informally, a family F subset of or equal to S-n of permutations is k-restricted in-wise independent if for any X subset of or equal to [0, n-1] with \X\ less than or equal to k, each x is an element of X is mapped to the minimum among pi(X) equally likely, and a family F subset of or equal to S-n of permutations is k-rankwise independent if for any X subset of or equal to [0, n - 1] with \X\ less than or equal to k, all elements in X are mapped in any possible order equally likely. It has been shown that if a family F subset of or equal to S-n of permutations is k-restricted min-wise (resp. k-rankwise) independent, then \F\ = Omega(n([ (k- 1)/2])) (resp. \F\ = Omega(n([k/2]))). In this paper, we construct families F subset of or equal to S-n of permutations of which size are close to those lower bounds for k = 3, 4, i.e., we construct a family F subset of or equal to S-n of 3-restricted (resp. 4-restricted) min-wise independent permutations such that \F\ = O(n lg(2) n) (resp. \F\ = O(n lg(3) n)) by applying the affine plane AG(2, q), and a family F subset of or equal to S-n of 4-rankwise independent permutations such that \F\ = O(n(3) lg(6) n) by applying the projective plane PG(2, q). Note that if a family F subset of or equal to S-n of permutations is 4-rankwise independent, then \F\ = Omega(n(2)). Since a family F subset of or equal to S-n of 4-rank-wise independent permutations is 4-restricted min-wise independent, our family F subset of or equal to S-n of 4-restricted min-wise independent permutations is the witness that properly separates the notion of 4-rankwise independence and that of 4-restricted min-wise independence.
研究論文（学術雑誌）, 英語 - On permutations with limited independence
T Itoh; Y Takei; J Tarui
PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SIAM, 掲載ページ 137-146, 出版日 2000年, 査読付, Informally, a permutation family is k-wise independent if any k distinct points are mapped to any k distinct points equally likely; a permutation family is k-rankwise independent if any Ic distinct points are mapped to any order equally likely; a permutation family is k-restricted min-wise independent if any element in at most k distinct points is mapped to be the minimum among those images equally likely (note that n-restricted min-wise independence is referred to simply as min-wise independence). These permutation families have theoretical applications, e.g., derandomization, universal hashing, search engines, etc. In this paper, we precisely investigate the size of those permutation families and show that (1) for lower bounds, \\ C \\ greater than or equal to n-1 and \\ C \\ greater than or equal to (n/2)([k/4]) for families C of k-restricted min-wise and k-rankwise independent permutations on {0, 1,..., n-1}, respectively; (2) for upper bounds, \\ C \\ less than or equal to n((1+(2/) (lgn))k) and \\ C \\ = n(O(k2)/ (ln) (k)) for families C of Ic-restricted min-wise and k-rankwise independent permutations on {0,1,..., n-1}, respectively; (3) for optimal upper bounds, \\ C \\ = lcm(n, n - 1,...,1) = e(n-o(n)) for families C of min-wise independent permutations on {0, 1,..., n-1}, which achieves the known lower bound.
研究論文（国際会議プロシーディングス）, 英語 - On complexity of computing the permanent of a rectangular matrix
T Kawabata; J Tarui
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E82A巻, 5号, 掲載ページ 741-744, 出版日 1999年05月, 査読付, lWe show that the permanent of an m x n rectangular matrix can be computed with O(n2(m) + 3(m)) multiplications and additions. Asymptotically, this is better than straightforward extensions of the best known algorithms for the permanent of a square matrix when m/n < log(3) 2 and n --> infinity.
研究論文（学術雑誌）, 英語 - Learning DNF by approximating inclusion-exclusion formulae
J Tarui; T Tsukiji
FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, IEEE COMPUTER SOC, 掲載ページ 215-220, 出版日 1999年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - On the Negation-Limited Circuit Complexity of Merging
K. Amano; A. Maruoka; J. Tarui
Lecture Notes in Computer Science vol. 1627: Proc. of COCOON99: The 5th Annual International Computing and Combinatorics Conference, Springer., 掲載ページ 204-209, 出版日 1999年
研究論文（国際会議プロシーディングス）, 英語 - Some observations on the computational complexity of graph accessibility problem
Jun Tarui; Seinosuke Toda
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 1627巻, 掲載ページ 18-30, 出版日 1999年, 査読付, We investigate the space complexity of the (undirected) graph accessibility problem (UGAP for short). We first observe that for a given graph G, the problem can be solved deterministically in space O(sw(G)2 log2 n), where n denotes the number of nodes and sw(G) de- notes the separation-width of G that is an invariant of graphs introduced in this paper. We next observe that for the class of all graphs consisting of only two paths, the problem still remains to be hard for determin- istic log-space under the NC1-reducibility. This result tells us that the problem is essentially hard for deterministic log-space.
研究論文（国際会議プロシーディングス）, 英語 - Finding relevant variables in PAC model with membership queries
D Guijarro; J Tarui; T Tsukiji
ALGORITHMIC LEARNING THEORY, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 1720巻, 掲載ページ 313-322, 出版日 1999年, 査読付, A new research frontier in AI and data mining seeks to develop methods to automatically discover relevant variables among many irrelevant ones. In this paper, we present four algorithms that output such crucial variables in PAC model with membership queries. The first algorithm executes the task under any unknown distribution by measuring the distance between virtual and real targets. The second algorithm; space under an arbitrary distribution. The third exhausts virtual version algorithm exhausts universal set under the uniform distribution. The fourth algorithm measures influence of variables under the uniform distribution. Knowing the number r of relevant variables, the first algorithm runs in almost linear time for r. The second and the third ones use less membership queries than the first one, but runs in time exponential for r. The fourth one enumerates highly influential variables in quadratic time for r.
研究論文（学術雑誌）, 英語 - The asymptotic complexity of merging networks
PB Miltersen; M Paterson; J Tarui
JOURNAL OF THE ACM, ASSOC COMPUTING MACHINERY, 43巻, 1号, 掲載ページ 147-165, 出版日 1996年01月, 査読付, Let M(m, n) be the minimum number of comparators needed in a comparator network that merges m elements x(1) less than or equal to x(2) less than or equal to ... less than or equal to x(m) and n elements y(1) less than or equal to y(2) less than or equal to ... less than or equal to y(n), where n greater than or equal to m. Batcher's odd-even merge yields the following upper bound:
M(m,n) less than or equal to 1/2(m + n)log(2)m + O(n);
in particular,
M(n,n) less than or equal to n log(2)n + O(n).
We prove the following lower bound that matches the upper bound above asymptotically as n greater than or equal to m --> infinity:
M(m,n) greater than or equal to 1/2(m + n)log(2)m - O(m);
in particular,
M(n,n) greater than or equal to 1/2 n log(2)n - O(n).
Our proof technique extends to give similarly tight Lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.
研究論文（学術雑誌）, 英語 - On ACC
Richard Beigel; Jun Tarui
Computational Complexity, Birkhäuser-Verlag, 4巻, 4号, 掲載ページ 350-366, 出版日 1994年12月, 査読付, We show that every language L in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and {Mathematical expression} AND gates of fan-in logO(1)n at the leaves, or equivalently, there exist polynomials pn(x1,..., xn) over Z of degree logO(1)n and with coefficients of magnitude {Mathematical expression} and functions hn:Z→{0,1} such that for each n and each x∈{0,1}n, XL(x)=hn(pn(x1,...,xn)). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985). © 1994 Birkhäuser Verlag.
研究論文（学術雑誌）, 英語 - PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIAL-TIME HIERARCHY
J TARUI
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 113巻, 1号, 掲載ページ 167-183, 出版日 1993年05月, 査読付, We show that, for every Boolean function f (x1, ..., x(n)) in the class AC0 and an arbitrary constant k greater-than-or-equal-to 0, there is a size-0 (n(k + 1)) collection OMEGA of degree-log(O(1)) n polynomials over Z in x 1, ..., x(n) such that, for each x is-an-element-of {0, 1}n, when p is-an-element-of OMEGA is randomly chosen, f(x) = p(x) with probability at least 1 - 1/(3n(k)), and, furthermore, if f (x) = 0 (f(x) = 1), then p(x) = 1 (p(x) = 0) with probability 0. Ap-plying this result, we prove the following: (a) Every Boolean function in the class AC0 can be computed with one-sided error at most 1/(3n(k)) by some depth-two probabilistic circuits with a threshold gate at the root, n(log(O(1)n) AND gates of fan-in log(O(1))n at the next level, and (k + 1)log2 n + O(1) random bits; it can also be computed, for an arbitrary constant l greater-than-or-equal-to 0, by some depth-three deterministic circuits with an OR gate at the root, at most n/(log2 n)1 Threshold gates at the second level, and n(log(O(1)n) AND gates of fan-in log(O(1))n at the third level. (b) For C = PP, C = P, and MOD(m)P, every language L in the polynomial-time hierarchy is C-easy under a randomized many-one polynomial-time reduction; in fact, for C = PP and C = P, L is C-easy under such a reduction with one-sided error.
研究論文（学術雑誌）, 英語 - Computing Symmetric Functions with AND/OR Circuits and a Single Majority Gate
Z. Zhang; D. Barrington; J. Tarui
Lecture Notes in Computer Science vol. 665: Proc. of STACS93: The 10th Annual Symposium on Theoretical Aspects of Computer Science, Springer. DOI: 10.1007/3-540-56503_53, 掲載ページ 535-554, 出版日 1993年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - ON PROBABILISTIC ACC CIRCUITS WITH AN EXACT-THRESHOLD OUTPUT GATE
R BEIGEL; J TARUI; S TODA
ALGORITHMS AND COMPUTATION, SPRINGER-VERLAG BERLIN, 650巻, 掲載ページ 420-429, 出版日 1992年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - ON PROBABILISTIC ACC CIRCUITS WITH AN EXACT-THRESHOLD OUTPUT GATE
R BEIGEL; J TARUI; S TODA
LECTURE NOTES IN COMPUTER SCIENCE, SPRINGER, 650巻, 掲載ページ 420-429, 出版日 1992年, 査読付, Let SYM+ denote the class of Boolean functions computable by depth-two size-n(logO(1)n) circuits with a symmetric-function gate at the root and AND gates of fan-in log(o(1)n) at the next level, or equivalently, the class of Boolean functions f such that f(x1,...,x(n)) can be expressed as f(x1,...,x(n)) = h(n)(p(n)(x1,..., x(n))) for some polynomial p. over Z of degree log(O(1)n) and norm (the sum of the absolute values of its coefficients) n(logO(1)n) and some function h(n) : Z --> {0, 1}. Building on work of Yao [Yao90], Beigel and Tarui [BT91] showed that ACC subset-or-equal-to SYM+, where ACC is the class of Boolean functions computable by constant-depth polynomial-size circuits with NOT, AND, OR, and MOD(m) gates for some fixed m.
In this paper, we consider augmenting the power of ACC circuits by allowing randomness and allowing an exact-threshold gate as the output gate (an exact-threshold gate outputs 1 if exactly k of its inputs are 1, where k is a parameter; it outputs 0 otherwise), and show that every Boolean function computed by this kind of augmented ACC circuits is still in SYM+.
Showing that some 'natural' function f docs not belong to the class ACC remains an open problem in circuit complexity, and the result that ACC subset-or-equal-to SYM+ has raised the hope that we may be able to solve this problem by exploiting the characterization of SYM+ iii terms of polynomials, which are perhaps easier to analyze than circuits, and showing that f is-not-an-element-of SYM+. Our new result and proof techniques suggest that the possibility that SYM+ contains even more Boolean functions than we currently know should also be kept iu mind and explored.
By a well-known connection [FSS84], we also obtain new results about some classes related to the polynomial-time hierarchy.
研究論文（学術雑誌）, 英語 - THE ASYMPTOTIC COMPLEXITY OF MERGING NETWORKS
PB MILTERSEN; M PATERSON; TR JUN
33RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE : PROCEEDINGS, I E E E, COMPUTER SOC PRESS, 掲載ページ 236-246, 出版日 1992年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - DEGREE COMPLEXITY OF BOOLEAN FUNCTIONS AND ITS APPLICATIONS TO RELATIVIZED SEPARATIONS
J TARUI
PROCEEDINGS OF THE SIXTH ANNUAL STRUCTURE IN COMPLEXITY THEORY CONFERENCE, I E E E, COMPUTER SOC PRESS, 掲載ページ 382-390, 出版日 1991年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - ON ACC
R BEIGEL; J TARUI
PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, I E E E, COMPUTER SOC PRESS, 掲載ページ 783-792, 出版日 1991年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - RANDOMIZED POLYNOMIALS, THRESHOLD CIRCUITS, AND THE POLYNOMIAL HIERARCHY
J TARUI
LECTURE NOTES IN COMPUTER SCIENCE, SPRINGER, 480巻, 掲載ページ 238-250, 出版日 1991年, 査読付, A randomized polynomial over the integers is a multivariate polynomial whose coefficients are integer-valued random variables. A randomized polynomial uses m random bits if its coefficients jointly depend on m independently and uniformly distributed random bits. We show that every Boolean function family in AC0 can be computed with small error by randomized polynomials over the integers that have degree (log n)omicron(1) and use (log n)omicron(1) random bits. Applying this result, we further show the following: (a) Every Boolean function family in AC0 is computable by depth-two probabilistic threshold circuits of size n(log n)omicron(1) with one-sided error and is also computable by depth-three deterministic threshold circuits with linear number of threshold gates and n(log n)omicron(1) AND gates. (b) Every language in the polynomial hierarchy is reducible to some language in the class PP (in fact, to some language in the class C = P) by a randomized polynomial-time reduction with one-sided error.
研究論文（学術雑誌）, 英語
MISC
- ［京都賞業績紹介］A.C.ヤオ／通信計算量理論：ヤオの卓越した独創の産物
垂井淳
出版日 2022年01月, 数学セミナー2022年１月号 https://amzn.to/3v13ibP, 掲載ページ 20-25, 日本語, 招待, 記事・総説・解説・論説等（商業誌、新聞、ウェブメディア） - Google Scholar Profile: http://scholar.google.co.jp/citations?user=7hrsV9cAAAAJ
Jun Tarui
出版日 2018年, 掲載ページ 0-0, 英語, その他 - P≠NP予想，代数的計算量
垂井淳
日本評論社, 出版日 2013年12月, 数学セミナー2013年12月号：P≠NP予想特集号, 52巻, 12号, 掲載ページ 18-22, 日本語, 記事・総説・解説・論説等（その他）, 0386-4960, 40019861947, AN10333470 - Theory and Applications of Models of Computation 2011 Preface
Mitusnori Ogihara; Jun Tarui
ELSEVIER SCIENCE BV, 出版日 2013年09月, THEORETICAL COMPUTER SCIENCE, 505巻, 掲載ページ 1-1, 英語, その他, 0304-3975, 1879-2294, WOS:000325905200001 - エキスパンダーとランダムネスの節約・除去
垂井淳
サイエンス社, 出版日 2006年, 数理科学2006年9月号：特集「ランダムネス」，2006., 44巻, 9号, 掲載ページ 31-36, 日本語, 記事・総説・解説・論説等（その他）, 0386-2240, 40007375217, AN00125207 - Recent Progress on Min-Wise Independent Permutations
T. Itoh; Y. Takei; J. Tarui
Broderらによって提案された"最小値独立置換族"は,電子文書の類似度を効率的に判定する際の基本的な概念であり,WEB上の類似文書の検出・確率的アルゴリズムの効率化などの応用を持つことが知られている.本稿では,最小値独立置換族(及びその拡張概念であるε-近似的最小中国財務局長独立置換族・k-制限最小値独立置換族など)に関する最近の成果-(1)最小値独立置換族を用いた電子文書の類似性判定法 : (2)最小値独立置換族のサイズに関する上界と下界 ; (3)ε-近似的最初値独立置換族のサイズに関する上界と下界 ; (4)k-制限最小値独立置換族のサイズに関する上界と下界-について述べ,最小値独立置換族(及びその拡張概念)の構成方法の現状を概観する., 一般社団法人電子情報通信学会, 出版日 2003年, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-49, 2003., 103巻, 394号, 掲載ページ 41-50, 英語, 記事・総説・解説・論説等（その他）, 0913-5685, 110003178798, AN10013152
書籍等出版物
講演・口頭発表等
- エクスパンダーと計算量理論
Jun TARUI
口頭発表（招待・特別）, エクスパンダーグラフの新しい構成手法の確立とその応用2
発表日 2023年09月05日
開催期間 2023年09月04日- 2023年09月08日 - ブログは研究に役立つか？どのように？
垂井淳
口頭発表（招待・特別）, 日本語, 国際学術情報流通基盤整備事業(SPARC Japan)2015年第3回セミナー招待講演（会場：国立情報学研究所）, 招待, 国際学術情報流通基盤整備事業(SPARC Japan), 国立情報学研究所（NII), 国内会議
発表日 2016年01月19日 - 計算量理論のいろんな話題
垂井淳
口頭発表（招待・特別）, 日本語, 計算量理論秋学校講演(熱海, 9月24日--26日, 2012), 計算量理論秋学校講演(熱海, 9月24日--26日, 2012)
発表日 2012年09月 - 計算の複雑さと証明の複雑さ
垂井淳
口頭発表（招待・特別）, 日本語, 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012), 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012)
発表日 2012年09月 - Complexity of Finding a Duplicate in a Stream
Jun Tarui
口頭発表（招待・特別）, 英語, NII Shonan Meeting: "Large-Scale Distributed Computation", NII Shonan Meeting: "Large-Scale Distributed Computation", (Zushi, Japan, Jan 12--15, 2012), 国際会議
発表日 2012年01月 - DeolalikarのP≠NP論文をめぐって
垂井淳
口頭発表（招待・特別）, 日本語, 電子情報通信学会，コンピュテーション研究会，p.47，信学技報COMP2010-38, 2010.
発表日 2010年 - Negation-Limited Complexity of Parity and Inverters
森住大樹; 垂井淳; 岩間一雄
口頭発表（一般）, 日本語, 2007冬のLAシンポジウム，京都大学数理解析研究所講究録 no. 1554, 131--138, 2007.
発表日 2007年 - 回路計算量の5nの下界に対する5nの上界
天野一幸; 垂井淳
口頭発表（一般）, 日本語, 2007年夏のLAシンポジウム，2007.
発表日 2007年 - Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic 0/1 Sequences
H. Morizumi; J. Tarui
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2006-49, 57--60, 2006.
発表日 2006年 - Explicit Construction of k-Wise Nearly Random Permutations by Iterated Feistel Transform
T. Itoh; T. Nagatani; J. Tarui
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2004-7, 2004.
発表日 2004年 - あるノイズモデルにおけるブール関数学習について
宮田明信; 垂井淳; 富田悦次
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-70, pp. 9--16, 2003.
発表日 2003年 - A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries
J. Tarui; T. Itoh; Y. Takei
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-21, pp. 35-42, 2003.
発表日 2003年 - On the Sample Size of k-Min-Wise Independent Permutations and Other k-Wise Distributions
T. Itoh; Y. Takei; J. Tarui
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2002-33, pp. 25-32, 2002.
発表日 2002年 - ブール関数のsensitivity, block sensitivity, certificate complexityについて
天羽健策; 垂井淳
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会，信学技報COMP97-118, 1998.
発表日 1998年
担当経験のある科目_授業
- 情報数理工学実験第二Ａ・Ｂ
The University of Electro-Communications - 情報数理工学実験第二Ａ・Ｂ
電気通信大学 - Advanced Communication Engineering and Informatics IV (Computational Complexity)
The University of Electro-Communications - Advanced Communication Engineering and Informatics IV (Computational Complexity)
電気通信大学 - Mathematical Information Science Laboratory ⅡB
The University of Electro-Communications - 情報数理工学実験第二B
電気通信大学 - Advanced Study for Theoretical Computer Science
The University of Electro-Communications - Theory of Computing
The University of Electro-Communications - Advanced Communication Engineering and Informatics Ⅲ（Computational Complexity）
The University of Electro-Communications - Advanced Communication Engineering and Informatics Ⅲ（Computational Complexity）（学域）
電気通信大学 - 理論計算機科学特論
電気通信大学 - 計算理論
The University of Electro-Communications - Computational Complexity
電気通信大学 - 離散数学
電気通信大学 - 離散数学
電気通信大学 - 理論計算機科学特論
The University of Electro-Communications - 理論計算機科学特論
電気通信大学 - 計算理論
電気通信大学 - 計算理論
電気通信大学 - Computational Complexity
The University of Electro-Communications - Computational Complexity
電気通信大学
共同研究・競争的資金等の研究課題
- 記憶領域制限シナリオにおける計算限界の解明
浅野 哲夫; 上原 隆平; 垂井 淳; 小野 廣隆; 清見 礼; 大舘 陽太
日本学術振興会, 科学研究費助成事業, 北陸先端科学技術大学院大学, 新学術領域研究(研究領域提案型), 本研究では，対数領域計算モデルでの非自明な下界と上界の確立に向けて強力な解析技法の開発を行った．与えられた実数値配列上で，各要素の対して，より大きな値をもつ要素の中で直近のものを見つける直近上位要素発見問題を基本問題として考えた．線形の作業領域を許すと線形時間ですべての直近上位要素を求めることができるが，少ない作業領域でどの程度の高速化が達成できるかが問題である．本研究では，定数個のメモリを用いるだけで十分に高速なアルゴリズムを開発することに成功し，その計算時間とメモリ量との間のトレードオフについても成果を得た．同様の研究結果を計算幾何学やグラフ理論の基本的な問題についても得ることができた．, 24106004
研究期間 2012年06月28日 - 2017年03月31日 - ブール関数の多項式表現を用いた回路計算量の解析
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), n個の頂点とm本の辺をもつ無向グラフに対して，n+o(n)ビットの記憶領域だけを用いて深さ優先探索が可能であり，有向非巡回グラフの場合は，n/[exp(Omega(root(log n)))]ビットの記憶容量だけを用いて深さ優先探索が可能であることがわかった．深さ優先探索以外の複数の問題についても同様の結果を得た．指数時間予想と「この問題をnの3乗より早くは解けない」といった予想の関連性が最近明らかになりつつあるが，我々の結果は，「記憶領域量がnの(1-epsilon)乗しかない場合は計算は不可能」といった予想と他の問題の領域計算量との関係解明の重要性を示唆している点が特に興味深い．, 25330010
研究期間 2013年04月01日 - 2016年03月31日 - 命題論理の証明の複雑さに関する計算量理論からの解析
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 鳩ノ巣原理の証明複雑さに関して,ストリーム計算における重複要素発見問題の領域計算量および通信計算量の解析を応用して新結果を得ることに成功した。開発し用いた手法はさらなる応用が期待できる。証明の複雑さと密接に関連する回路計算量に関して,ノイズ下でのAC0関数の学習アルゴリズムの拡張,5nより大きい回路サイズ下界の証明に立ちふさがる障害の解析,パリティを計算するサイズn^2フォーミュラの本質的一意性などの結果を与えることができた。, 22500012
研究期間 2010年 - 2012年 - 最大クリーク抽出アルゴリズムの効率化・拡張と計算量評価および応用
富田 悦次; 高橋 治久; 西野 哲朗; 若月 光夫; 垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリークを抽出する新しいアルゴリズムMCSを開発し,格段に高速であることを明らかにした.これにより,従来では100日以上かかっても解けなかった幾つかの問題を100秒以内で解くことに成功した.最大クリーク問題が多項式時間的に可解となる基本的結果も確立した.また,最大クリーク抽出アルゴリズムがハイパーグラフにおいても効率的に稼働する様に拡張した.更に,これらのアルゴリズムをデータマイニングなどの実問題に応用して有効な結果を得た., 19500010
研究期間 2007年 - 2009年 - 量子論理回路の最適化に関する研究
西野 哲朗; 垂井 淳; 太田 和夫; 國廣 昇
日本学術振興会, 科学研究費助成事業, 電気通信大学, 特定領域研究, 量子コンピュータの物理的実現には、多くの困難が存在する。例えば、量子もつれ合いを保つことができる時間が短いことや、複雑な量子操作を行なうことが難しいこと等が挙げられる。これらの問題の解決において、量子回路のサイズは非常に重要である。本研究では、量子回路サイズの新たな評価方法について検討する。特に、C-NOTゲートに着目し、量子回路計算量とC-NOTゲート数の関係について、幾つかの定理を示した。 現在、量子コンピュータの物理的実現について盛んに研究が行われているが、その実現には多くの困難が伴う。そのうちの一つとして、量子コンピュータは量子重ね合わせ状態という量子力学的にデリケートな状態を取ることが挙げられる。そのため、サイズの大きな量子コンピュータの複雑な量子重ね合わせ状態を長時間維持することは非常に困難となる それに加えて、量子コンピュータは扱えるビット数が大きくなるほど実現が困難となる。すなわち、同じアルゴリズムを実行する場合、量子コンピュータにおいては、特に、時間計算量および領域計算量を縮小することが本質的に重要な問題となる。そこで、本研究では、量子回路のゲート数とビット数の関係についても考察した。具体的には、あるアルゴリズムを実行する量子回路に対して、それに補助量子ビットを付加し、回路を再構成することで、ゲートの総数をさらに縮小できるかどうかを検証した。 我々は古典コンピュータを用いてアルゴリズムを実行するときに、計算時間の短縮のために、計算の途中で、その計算結果の一部をメモリの別の場所に一時的に保管することをよく行う。量子コンピュータの回路設計においても、補助量子ビットはそのようなワークビットとしてたびたび用いられるが、そこで使われる補助量子ビットは厳密に定義されているわけではない。本研究では、どのような種類の補助量子ビットにゲート数縮小の効果があるのかを検証するために、補助量子ビットの分類と定式化を行った。, 16092208
研究期間 2004年 - 2007年 - 計算量の理論-下界の証明・計算量の正確な決定・最適アルゴリズムの一意性の問題
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 今年度得られた結果のいくつかを以下の簡潔に述べる。 1. 否定数限定回路でのmergingのcomplexityをかなり正確に決定することに成功した:2つの長さnのソートされた0,1列をマージするa個のNOT gateとAND,OR gateよりなる最小の回路のサイズは、a【less than or equal】log_2nのときΘ(nlog_2n/2^a)であることを示すことができた。 2. DNF式にたいして効率的PAC(Probably Approximately Correct)学習が可能かどうかという問題は、計算論学習理論における最重要な未解決問題のひとつである。この問題についてのあるアプローチの可能性と限界にてついての結果を得た:長さがmのmonomialで、ターゲットであるDNF式との相関があるものを弱学習することとboostingよってDNF式の学習を達成しようとするとき、mがn^<1/2>より小さい場合は、弱学習が不可能であり、n^<1/2>くらいまで大きくとると可能であることを示した。 3. Broder他がSTOC98で発表したMIn-wise independent permutation familyについて、その仕事で未解決問題として残されていたもののいくつかにたいしてそのようなfamily sizeにたいして上界・下界を示すことができた。 4. m by n rectangular matrix(m【less than or equal】n)のPermanentをO(n2^m+3^m)arithmetic operationsによって計算するアルゴリズムを与えた。, 09780257
研究期間 1997年 - 1998年 - 組合せ論的計算量の理論-特に下界の証明と最適アルゴリズムの-意性の問題
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 本研究では、いくつかの組合せ論的計算モデルについて、計算能力の解析と“自然な"計算問題を解くのに必要な計算資源の量の分析を行なった。以下では、今年度論文としてまとめるに至ったものについてより詳しく述べる。 1.constant-depth polynomial-sizeの組合せ論理回路によって定義される計算量のクラスACCについて、以前よりRichard Beigel(Yale大学)と共同研究を行なっていたが、今年度 この結果をJ.of Comp.Complexityに発表した。この論文では、クラスACCに属する任意のブール関数は、深さ2のある形の回路で計算可能であること等が示されている。 2.整列されている2つのリストをcomparator(比較器)によって併合するmergng networkに必要なcomparatorの数について、Batcherのodd-even mergeに基づくものが、漸近的に最適であるという結果を含む論文のjournal versionを今年度まとめた。これは、以前よりの共同研究を発展させたもので、論文は現在審査中である。, 06780246
研究期間 1994年 - 1995年 - 組合せ最適化問題の高効率アルゴリズムの開発と評価
富田 悦次; 若月 光夫; 垂井 淳; 高橋 治久
日本学術振興会, 科学研究費助成事業, 電気通信大学, 一般研究(C), 組合せ最適化問題のうちで、先ず、基本的で主要な問題の一つである、グラフ中の最大クリークを厳密に求める問題に対し、単純で高効率な分枝限定アルゴリズムを確立した。そこでは、いかにして分枝の限定を強力に働かせて解の探索領域を小さくするかが高効率化の重要な指標となるが、本研究においては、巧妙な逐次近似彩色-整列法の考案適用により、探索の各段階に於て見出し得る最大クリークの上界を得て分枝制限を効果的に実現し、かつ総実行時間も小さく抑えることに成功した。続いて、更に分枝限定のための種々の方法を考案し、各々の方法の特長が発揮できるようにそれらを組み合せることにより、先の単純なアルゴリズムよりも一層幅広い対象範囲のグラフに対してより効率のよいアルゴリズムを開発した。その高効率性は、ランダムグラフを主とした数多くのグラフに対して実験的比較評価を行うことにより確認した。 更に本手法を、重み付きグラフに対する最大重みクリーク抽出問題に発展させて、新しいアルゴリズムを得、基本的手法に対する有効性を実験的に確認した。 次に、ボルツマンマシンの概念を基にした近似最大クリーク抽出アルゴリズムを基礎として、近似彩色の新しい確率アルゴリズムを開発し、大規模のグラフに対しても効率的にかなり精度よく彩色可能とする手法を提唱し、実験的評価を与えた。 また、組合せ最適化問題の具体例として、RNAの二次構造予測問題を重み付きグラフの最大重みクリーク抽出問題に形式化し、同抽出アルゴリズムによって、基本的なRNAの二次構造予測が可能であることを実験的に確認した。, 06680311
研究期間 1994年 - 1995年
