Lecture 5.Formula complexity I A Boolean function can be computed by different models,and an important one is the class of formulas.Roughly speaking,formulasare circuits with fanout 1.To be more specific,a formula is a rooted tree s.t. ● each internal node is associated with a gate which is either AND or OR, ● each leaf is associated with a variable xi,the negation ofa variable or a constant 0 or 1. (Note that we have used DeMorgan rule to push all negations to the leaf level.)The formula computes a function f on input x by evaluating the gates in a bottom-up manner,and the root outputs f(x). Different measures of formula are studied,among which depth,size(number of gates)and leaf size (number of leaves)are the most important ones.The leaf size L(F)ofa formula F is simply the number of leaves.The leaf size L(f)ofa function f is the minimum leaf size L(F)of any formula F that computes f. A function f:{0,1}n→{0,1 is monotone if f(x)≤fy)whenever xi≤y,∀i∈[n]In other words,it requiresthat changing an input variable from 0 to I doesn't decrease the function value.For monotone functions,we can require the formula contain only variables and constants in leaves,but no negation of variables.(Convince yourself.)These are called monotone formulas.So for monotone functions,we can define the monotone leafsize L(f)as the minimal number of leaves ofany monotone formula that computes f. While circuit lower bounds are too hard to prove---the best unconditional lower bound is only cn for some constant c,people stepped back and tried to prove fomula lower bounds.In this and the next lectures,we will learn various methods to prove lower bounds for formula complexity. 1.(Random)Restriction The idea of restriction is as follows.We will pick some variables and fix their values to be some constants,resulting in a"subfunction"f.The variables are picked and fixed in such a ways that the complexity ofthis subfunction is considerably smaller than that off.But if we keep doing so,we'll go to a very small scale function with complexity 0.But this small scale function is still not a constant function,thus has a positive complexity---contradiction.This idea went all the way back to Subbotovskaya [Sub61].Lecture 5. Formula complexity I A Boolean function can be computed by different models, and an important one is the class of formulas. Roughly speaking, formulas are circuits with fanout 1. To be more specific, a formula is a rooted tree s.t. ⚫ each internal node is associated with a gate which is either AND or OR, ⚫ each leaf is associated with a variable xi , the negation of a variable 𝑥̅𝑖 , or a constant 0 or 1. (Note that we have used DeMorgan rule to push all negations to the leaf level.) The formula computes a function f on input x by evaluating the gates in a bottom-up manner, and the root outputs f(x). Different measures of formula are studied, among which depth, size (number of gates) and leaf size (number of leaves) are the most important ones. The leaf size L(F) of a formula F is simply the number of leaves. The leaf size L(f) of a function f is the minimum leaf size L(F) of any formula F that computes f. A function 𝑓:{0,1} 𝑛 → {0,1} is monotone if 𝑓(𝑥) ≤ 𝑓(𝑦) whenever 𝑥𝑖 ≤ 𝑦i ,∀𝑖 ∈ [𝑛]. In other words, it requires that changing an input variable from 0 to 1 doesn’t decrease the function value. For monotone functions, we can require the formula contain only variables and constants in leaves, but no negation of variables. (Convince yourself.) These are called monotone formulas. So for monotone functions, we can define the monotone leaf size 𝐿+(𝑓) as the minimal number of leaves of any monotone formula that computesf. While circuit lower bounds are too hard to prove---the best unconditional lower bound is only cn for some constant c, people stepped back and tried to prove formula lower bounds. In this and the next lectures, we will learn various methods to prove lower bounds for formula complexity. 1. (Random) Restriction The idea of restriction is as follows. We will pick some variables and fix their values to be some constants, resulting in a “subfunction” f’. The variables are picked and fixed in such a ways that the complexity of this subfunction is considerably smaller than that of f. But if we keep doing so, we’ll go to a very small scale function with complexity 0. But this small scale function is still not a constant function, thus has a positive complexity---contradiction. This idea went all the way back to Subbotovskaya [Sub61]