| A new rank technique for formula size lower bounds (2007) | |||||||||||||||
Abstract | |||||||||||||||
| We introduce a new technique for proving formula size lower bounds based on matrix rank. A simple form of this technique gives bounds at least as large as those given by the method of Khrapchenko, originally used to prove an��lower bound on the parity function. Applying our method to the parity function, we are able to give an exact expression for the formula size of parity: if������, where������, then the formula size of parity on �bits is exactly��������������� � ��. Such a bound cannot be proven by any of the lower bound techniques of Khrapchenko, Nečiporuk, Koutsoupias, or the quantum adversary method, which are limited by��. 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||