Academic
Publications
Applications of matrix methods to the theory of lower bounds in computational complexity

Applications of matrix methods to the theory of lower bounds in computational complexity,10.1007/BF02122698,Combinatorica,Alexander A. Razborov

Applications of matrix methods to the theory of lower bounds in computational complexity   (Citations: 48)
BibTex | RIS | RefWorks Download
We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundnΩ(logn) for the function “MINIMUM COVER” using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.
Journal: Combinatorica , vol. 10, no. 1, pp. 81-93, 1990
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: