Some Lower Bounds of Cyclic Shift on Boolean Circuits (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 a directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.

• 社団法人電子情報通信学会の論文
• 1996-04-25

著者

• Tsukiji Tatsuie

  Department Of Computer Science Tokyo Institute Of Technology

関連論文

• Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
• Approximated Vertex Cover for Graphs with Perfect Matchings(Invited Papers from New Horizons in Computing)
• ^^-Coloring Problem(Graphs and Networks)
• Some Lower Bounds of Cyclic Shift on Boolean Circuits (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク