Some Lower Bounds of Cyclic Shift on Boolean Circuits

Tatsuie TSUKIJI

Some Lower Bounds of Cyclic Shift on Boolean Circuits

Tatsuie TSUKIJI

Full Text Views

0

Cite this

Summary :

We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: ・ for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. ・ A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.4 pp.520-523

Publication Date: 1996/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Tatsuie TSUKIJI, "Some Lower Bounds of Cyclic Shift on Boolean Circuits" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 4, pp. 520-523, April 1996, doi: .
Abstract: We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: ・ for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. ・ A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_4_520/_p

Copy

@ARTICLE{e79-a_4_520,
author={Tatsuie TSUKIJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Some Lower Bounds of Cyclic Shift on Boolean Circuits},
year={1996},
volume={E79-A},
number={4},
pages={520-523},
abstract={We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: ・ for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. ・ A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Some Lower Bounds of Cyclic Shift on Boolean Circuits
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 520
EP - 523
AU - Tatsuie TSUKIJI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1996
AB - We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: ・ for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. ・ A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.
ER -