Applications of matrix methods to the theory of lower bounds in computational complexity (Q2638784): Difference between revisions

One of the hardest tasks of the complexity theory is to discover some combinatorial or algebraic properties of Boolean functions which would imply high complexity in interesting computing models. A contribution in this direction is made here by proving nonpolynomial lower bound on the monotone formula size for the function ``minimum cover''. Nonpolynomial lower bounds for monotone complexity were already known, and so the main contribution of this paper is in the presentation of new, essential simpler methods than the previous ones for this task. Some connections between this method on one side, and communication complexity for VLSI and graph complexity on other side are also shown.