Formula size complexity

Presented at AAAC 2011

Parity vs majority

Construct a formula with literals and AND and OR to represent the function

Size of smallest formula for parity is at most n^2

Khrapchenko’s method to get a lower bound.