Complexity of the realization of a linear function in the class of \(\Pi\)-circuits

DOI10.1007/BF01405045zbMath0222.94044MaRDI QIDQ2547883

V. M. Khrapchenko

Publication date: 1971

Published in: Mathematical Notes (Search for Journal in Brave)

Mathematics Subject Classification ID

Related Items (16)

New bounds on the half-duplex communication complexity ⋮ On almost bad Boolean bases ⋮ The average sensitivity of bounded-depth formulas ⋮ On the shrinkage exponent for read-once formulae ⋮ Unnamed Item ⋮ On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube ⋮ Unnamed Item ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO ⋮ Interpolants, cut elimination and flow graphs for the propositional calculus ⋮ Solution of Rota's problem on the order of series-parallel networks ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ An extension of Khrapchenko's theorem ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority

Cites Work

• Unnamed Item

This page was built for publication: Complexity of the realization of a linear function in the class of \(\Pi\)-circuits