Method of determining lower bounds for the complexity of \(\Pi\)-circuits
From MaRDI portal
Publication:2550627
DOI10.1007/BF01747074zbMath0231.68023MaRDI QIDQ2550627
Publication date: 1972
Published in: Mathematical Notes (Search for Journal in Brave)
Related Items
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity, The average sensitivity of bounded-depth circuits, On the limits of gate elimination, Better lower bounds for monotone threshold formulas, On the shrinkage exponent for read-once formulae, Super-logarithmic depth lower bounds via the direct sum in communication complexity, Upper bounds for the size and the depth of formulae for MOD-functions, ERCW PRAMs and optical communication, Unnamed Item, Improving \(3N\) circuit complexity lower bounds, Unnamed Item, Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation, Using amplification to compute majority with small majority gates, Improvements on Khrapchenko's theorem, On convex complexity measures, The computational complexity of universal hashing, Unnamed Item, Formula complexity of a linear function in a \(k\)-ary basis, Optimal Lower Bounds on Regular Expression Size Using Communication Complexity, Regular expression length via arithmetic formula complexity, An extension of Khrapchenko's theorem, Prediction from partial information and hindsight, with application to circuit lower bounds, On covering graphs by complete bipartite subgraphs, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, On the computational complexity of qualitative coalitional games
Cites Work
