IEICE TRANSACTIONS on Fundamentals
Some Lower Bounds of Cyclic Shift on Boolean Circuits
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(
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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(
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(
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(
ER -
English
