JUN TARUI
| Department of Computer and Network Engineering | Associate Professor |
| Cluster I (Informatics and Computer Engineering) | Associate Professor |
Researcher Information
Degree
Career
Research Activity Information
Paper
- 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, Mar. 2018, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Aug. 2011, Peer-reviwed, 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.
Scientific journal, English - 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, Apr. 2011, Peer-reviwed, 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.
Scientific journal, English - 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, Jun. 2010, Peer-reviwed, 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.
Scientific journal, English - Negation-Limited Complexity of Parity and Inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMICA, SPRINGER, 54, 2, 256-267, Jun. 2009, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - On the minimum number of completely 3-scrambling permutations
Jun Tarui
DISCRETE MATHEMATICS, ELSEVIER SCIENCE BV, 308, 8, 1350-1354, Apr. 2008, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Smallest formulas for parity of 2(k) variables are essentially unique
Jun Tarui
COMPUTING AND COMBINATORICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5092, 92-99, 2008, Peer-reviwed, 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.
International conference proceedings, English - Reductions for Monotone Boolean Circuits
K. Iwama; H. Morizumi; J. Tarui
Theoretical Computer Science., 408, 208-212, 2008, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed, 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?
International conference proceedings, English - 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.
International conference proceedings, English - Negation-limited complexity of parity and inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4288, 223-+, 2006, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, May 2004, Peer-reviwed, 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.
Scientific journal, English - 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.
Scientific journal, English - On the negation-limited circuit complexity of merging
K Amano; A Maruoka; J Tarui
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 126, 1, 3-8, Mar. 2003, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, May 1999, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
Scientific journal, English - The asymptotic complexity of merging networks
PB Miltersen; M Paterson; J Tarui
JOURNAL OF THE ACM, ASSOC COMPUTING MACHINERY, 43, 1, 147-165, Jan. 1996, Peer-reviwed, 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.
Scientific journal, English - On ACC
Richard Beigel; Jun Tarui
Computational Complexity, Birkhäuser-Verlag, 4, 4, 350-366, Dec. 1994, Peer-reviwed, 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.
Scientific journal, English - PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIAL-TIME HIERARCHY
J TARUI
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 113, 1, 167-183, May 1993, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - RANDOMIZED POLYNOMIALS, THRESHOLD CIRCUITS, AND THE POLYNOMIAL HIERARCHY
J TARUI
LECTURE NOTES IN COMPUTER SCIENCE, SPRINGER, 480, 238-250, 1991, Peer-reviwed, 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.
Scientific journal, English
MISC
- ［京都賞業績紹介］A.C.ヤオ／通信計算量理論：ヤオの卓越した独創の産物
垂井淳
Jan. 2022, 数学セミナー2022年１月号 https://amzn.to/3v13ibP, 20-25, Japanese, Invited, Introduction commerce magazine - Google Scholar Profile: http://scholar.google.co.jp/citations?user=7hrsV9cAAAAJ
Jun Tarui
2018, 0-0, English, Others - P≠NP予想，代数的計算量
垂井淳
日本評論社, Dec. 2013, 数学セミナー2013年12月号：P≠NP予想特集号, 52, 12, 18-22, Japanese, Introduction other, 0386-4960, 40019861947, AN10333470 - Theory and Applications of Models of Computation 2011 Preface
Mitusnori Ogihara; Jun Tarui
ELSEVIER SCIENCE BV, Sep. 2013, THEORETICAL COMPUTER SCIENCE, 505, 1-1, English, Others, 0304-3975, 1879-2294, WOS:000325905200001 - エキスパンダーとランダムネスの節約・除去
垂井淳
サイエンス社, 2006, 数理科学2006年9月号：特集「ランダムネス」，2006., 44, 9, 31-36, Japanese, Introduction other, 0386-2240, 40007375217, AN00125207 - Recent Progress on Min-Wise Independent Permutations
T. Itoh; Y. Takei; J. Tarui
The notion of "a family of min-wise independent permutations" was introduced by Broder, et al. It is a basic tool to estimate resemblance between documents and has applications of detecting almost identical documents on the Web and of reducing the amount of randomness used by algorithms. In this paper, we focus on min-wise independent permutations and the related notions, e. g., ε-approximate min-wise independent permutations, k-restricted min-wise independent permutatios, etc., and overview the recen tresults on (1) how to estimate resemblance between documents by min-wise independent permutations ; (2) upper and lower bounds for the size of min-wise independent permutations ; (3) upper and lower bounds for the size of ε-approximate min-wise independent permutations ; (4) upper and loer obunds for the size of k-restricted min-wise independent permutations., The Institute of Electronics, Information and Communication Engineers, 2003, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-49, 2003., 103, 394, 41-50, English, Introduction other, 0913-5685, 110003178798, AN10013152
Books and other publications
Lectures, oral presentations, etc.
- Expanders and Computational Complexity Theory
Jun TARUI
Invited oral presentation, エクスパンダーグラフの新しい構成手法の確立とその応用2
05 Sep. 2023
04 Sep. 2023- 08 Sep. 2023 - ブログは研究に役立つか？どのように？
垂井淳
Invited oral presentation, Japanese, 国際学術情報流通基盤整備事業(SPARC Japan)2015年第3回セミナー招待講演（会場：国立情報学研究所）, Invited, 国際学術情報流通基盤整備事業(SPARC Japan), 国立情報学研究所（NII), Domestic conference
19 Jan. 2016 - 計算量理論のいろんな話題
垂井淳
Invited oral presentation, Japanese, 計算量理論秋学校講演(熱海, 9月24日--26日, 2012), 計算量理論秋学校講演(熱海, 9月24日--26日, 2012)
Sep. 2012 - 計算の複雑さと証明の複雑さ
垂井淳
Invited oral presentation, Japanese, 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012), 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012)
Sep. 2012 - Complexity of Finding a Duplicate in a Stream
Jun Tarui
Invited oral presentation, English, NII Shonan Meeting: "Large-Scale Distributed Computation", NII Shonan Meeting: "Large-Scale Distributed Computation", (Zushi, Japan, Jan 12--15, 2012), International conference
Jan. 2012 - DeolalikarのP≠NP論文をめぐって
垂井淳
Invited oral presentation, Japanese, 電子情報通信学会，コンピュテーション研究会，p.47，信学技報COMP2010-38, 2010.
2010 - Negation-Limited Complexity of Parity and Inverters
森住大樹; 垂井淳; 岩間一雄
Oral presentation, Japanese, 2007冬のLAシンポジウム，京都大学数理解析研究所講究録 no. 1554, 131--138, 2007.
2007 - 回路計算量の5nの下界に対する5nの上界
天野一幸; 垂井淳
Oral presentation, Japanese, 2007年夏のLAシンポジウム，2007.
2007 - Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic 0/1 Sequences
H. Morizumi; J. Tarui
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報COMP2006-49, 57--60, 2006.
2006 - Explicit Construction of k-Wise Nearly Random Permutations by Iterated Feistel Transform
T. Itoh; T. Nagatani; J. Tarui
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報COMP2004-7, 2004.
2004 - あるノイズモデルにおけるブール関数学習について
宮田明信; 垂井淳; 富田悦次
Oral presentation, Japanese, 電子情報通信学会コンピュテーション研究会，信学技報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
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報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
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報COMP2002-33, pp. 25-32, 2002.
2002 - ブール関数のsensitivity, block sensitivity, certificate complexityについて
天羽健策; 垂井淳
Oral presentation, Japanese, 電子情報通信学会コンピュテーション研究会，信学技報COMP97-118, 1998.
1998
Courses
- 情報数理工学実験第二Ａ・Ｂ
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 - 計算理論
The University of Electro-Communications - Computational Complexity
電気通信大学 - 離散数学
The University of Electro-Communications - 離散数学
電気通信大学 - 理論計算機科学特論
The University of Electro-Communications - 理論計算機科学特論
電気通信大学 - 計算理論
The University of Electro-Communications - 計算理論
電気通信大学 - Computational Complexity
The University of Electro-Communications - Computational Complexity
The University of Electro-Communications
Research Themes
- Exploring the Limits of Computation in the Scenario of Constrained Work Space
Asano Tetsuo; Guenter Rote; Wolfgang Mulzer; Ovidiu Daescu
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Japan Advanced Institute of Science and Technology, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), In this research we have developed powerful techniques for analysis toward establishment of nontrivial lower and upper bounds on the constrained work space. The most fundamental problem is to seek for each entry in a given array of real numbers one of nearest greater values. Using linear size of work space we can design a linear time algorithm for solving the problem. Our problem is whether we can solve the problem in an efficient way using less work space. In this research we showed that we have an efficient algorithm using only constant amount of work space. We also had results on time and space tradeoffs on the problem. We obtained other many results in basic problems in computational geometry and graph theory., 24106004
28 Jun. 2012 - 31 Mar. 2017 - Study of Circuit Complexity Using Polynomial Representations of Boolean Functions
Tarui Jun
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), We have shown that for an undirected graph with n vertices and m edges, Depth-First Search (DFS) is possible using n+o(n) bits of memory. For a directed acyclic graph, DFS is possible using n/[exp(Omega(root(log n))) ] bits of memory. We have also obtained similar results for several other graph problems. Recently, researchers are finding more and more interesting connections between Exponential-Time Hypothesis (ETH) and the time complexity of polynomial-time solvable problems. For example, it is now known that ETH implies that a truly sub-cubic algorithm does *not* exist for a certain graph problem. Our results above seem to suggest that we should investigate space-complexity analogues of this phenomena: What are the consequences of the conjecture "Problem A requires linear space" ?, 25330010
01 Apr. 2013 - 31 Mar. 2016 - Propositional Proof Complexity: Analysis fromComputational Complexity Perspectives
TARUI Jun
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), We have obtained a new result about proof complexity of the pigeonhole principle by analyzing the space complexity and the communication complexity of findig a duplicate in a stream. Our new proof method is interesting in its own. For circuit complexity, which is closely related to proof complexity, we have (1) extended a noise-tolerant learning algorithm for AC0 functions, (2) have identified a concrete barrier for provindg a circuit-size lower bound bigger than 5n, and (3) have shown that, for n a power of 2, a smallest DeMorgan formula computing Parity of n Boolean variables is essentially unique., 22500012
2010 - 2012 - Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications
TOMITA Etsuji; TAKAHASHI Haruhisa; NISHINO Tetsuro; WAKATSUKI Mitsuo; TARUI Jun
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (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 - Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems
TOMITA Etsuji; WAKATSUKI Mitsuo; TARUI Jun; TAKAHASHI Haruhisa
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for General Scientific Research (C), We have developed a simple and branch and bound algorithm for finding a maximum clique of a graph. Our approach successively applies a pruning method based on greedy coloring followed by suitable arrangements for the vertices in consideration. The algorithm reduces the number of search tree nodes very effectively and hence runs fast. It is experimentally confirmed to run faster for a number of random graphs with up to 600 vertices and other graphs than several algorithms which have been appeared in the literature. This algorithm has been further improved by combining several methods. We have also developed a simple branch and bound algorithm for finding a maximum weight clique in a weighted graph. Its bounding rule is principally based upon a sequentail approximate coloring which has been applied in the above algorithms. Based upon Boltzmann machines, a new algorithm is given for approximately coloring a graph. Besides, the above algorithm for finding a maximum weight clique is applied for an RNA secondary structure prediction problem., 06680311
1994 - 1995
