Arrow Research search

Author name cluster

Akira Maruoka

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers
2 author rows

Possible papers

14

MFCS Conference 2005 Conference Paper

On the Complexity of Depth-2 Circuits with Threshold Gates

  • Kazuyuki Amano
  • Akira Maruoka

Abstract The paper investigates the complexity of depth-two circuits with threshold gates and consisting of two parts. First, we develop a method for deriving a lower bound on the size of depth two circuits with a threshold gate at the top and a certain type of gates at the bottom. We apply the method for circuits with symmetric gates at the bottom that compute the “inner product mod 2”, and obtain a lower bound of 1. 3638 n. Although our lower bound is slightly weaker than the best known lower bound of Ω(2 n /2 / n ), which was recently proved by Forster et al. [5, 6], our method has unique features: A lower bound is obtained by solving a certain linear program, and solving larger linear programs yield higher lower bounds. We also discuss the generalization of the proposed method. Second, we develop a simplified simulation of a depth-one threshold circuit with unbounded weights by a depth-two threshold circuit with small weights. Precisely, we give an explicit construction of depth-two circuits with small weights consist of Õ n 5 gates that compute an arbitrary threshold function. We also give the construction of such circuits with O ( n 3 /log n ) gates computing the COMPARISON and CARRY functions, and that with O ( n 4 /log n ) gates computing the ADDITION function. These improve the previously known constructions on its size and simplicity.

Details

MFCS Conference 2003 Conference Paper

On Optimal Merging Networks

  • Kazuyuki Amano
  • Akira Maruoka

Abstract We prove that Batcher’s odd-even ( m, n )-merging networks are exactly optimal for ( m, n )=(3, 4 k +2) and (4, 4 k +2) for k ≥ 0 in terms of the number of comparators used. For other cases where m ≤ 4, the optimality of Batcher’s ( m, n )-merging networks has been proved. So we can conclude that Batcher’s odd-even merge yields optimal ( m, n )-merging networks for every m ≤ 4 and for every n. The crucial part of the proof is characterizing the structure of optimal (2, n )-merging networks.

Details

MFCS Conference 2001 Conference Paper

The Computational Power of a Family of Decision Forests

  • Kazuyuki Amano
  • Tsukuru Hirosawa
  • Yusuke Watanabe
  • Akira Maruoka

Abstract In this paper, we consider the help bit problem in the decision tree model proposed by Nisan, Rudich and Saks (FOCS ’94). When computing k instances of a Boolean function f, Beigel and Hirst (STOC ’98) showed that⌊log 2 k ⌋+ 1 help bits are necessary to reduce the complexity of f, for any function f, and exhibit the functions for which ⌊log 2 k ⌋+ 1 help bits reduce the complexity. Their functions must satisfy the condition that their complexity is greater than or equal to k -1. In this paper, we show new functions satisfying the above conditions whose complexity are only 2√k. We also investigate the help bit problem when we are only allowed to use decision trees of depth 1. Moreover, we exhibit the close relationship between the help bit problem and the complexity for circuits with a majority gate at the top.

Details

MFCS Conference 1998 Conference Paper

A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with At Most (1/6) log log n Negation Gates

  • Kazuyuki Amano
  • Akira Maruoka

Abstract We investigate about a lower bound on the size of a Boolean circuit that computes the clique function with a limited number of negation gates. To derive strong lower bounds on the size of such a circuit we develop a new approach by combining the three approaches: the restriction applied for constant depth circuits[Has], the approximation method applied for monotone circuits[Raz2] and boundary covering developed in the present paper. Based on the approach the following statement is established: If a circuit C with at most ⌈(1/6) log log m ⌋ negation gates detects cliques of size \((\log m)^{3(\log {\mathbf{ }}m)^{{\raise0. 5ex\hbox{$\scriptstyle 1$}\kern-0. 1em/\kern-0. 15em\lower0. 25ex\hbox{$\scriptstyle 2$}}} }\) in a graph with m vertices, then C contains at least \(2^{({\raise0. 5ex\hbox{$\scriptstyle 1$}\kern-0. 1em/\kern-0. 15em\lower0. 25ex\hbox{$\scriptstyle 5$}})(\log {\mathbf{ }}m)^{(\log {\mathbf{ }}m)^{{\raise0. 5ex\hbox{$\scriptstyle 1$}\kern-0. 1em/\kern-0. 15em\lower0. 25ex\hbox{$\scriptstyle 2$}}} } }\) gates. In addition, we present a general relationship between negation-limited circuit size and monotone circuit size of an arbitrary monotone function.

Details

FOCS Conference 1996 Conference Paper

Potential of the Approximation Method (extended abstract)

  • Kazuyuki Amano
  • Akira Maruoka

Developing some techniques for the approximation method, we establish precise versions of the following statements concerning lower bounds for circuits that detect cliques of size s in a graph with m vertices. For 5/spl les/s/spl les/m/4, a monotone circuit computing CLIQUE(m, s) contains at least (1/2) 1. 8/sup min(/spl radic/s-1/2, m/(4s))/ gates. If a non-monotone circuit computes CLIQUE using a "small" amount of negation, then the circuit contains an exponential number of gates. The former is proved very simply using so called bottleneck counting argument within the framework of approximation, whereas the latter is verified introducing a notion of restricting negation and generalizing the sunflower contraction.

Details