Week 8

Question 1

What is a basis?

Answer 1

A basis is a set Ω = {fi }i<k of Boolean functions (‘connectives’).

We say that Ω is complete if every Boolean function is computed by an expression/formula formed from variables and elements of Ω.

Question 2

What is the change-of-basis theorem?

Answer 2

Let Ω1, Ω2 (with Ω2 complete).
Then for any Ω1-circuit C1 there is an Ω2 circuit C2 computing the same Boolean function with:
▶ |C2| = O(|C1|)
▶ depth(C2) = O(depth(C1))

ONLY applies to circuits, not formulas.

Question 3

What is the Spira Balancing Theorem?

Answer 3

∆ = {0, 1, δ}

Let Ω be a complete basis. For every Ω-formula A of size n there is a logically equivalent ∆-formula A′ s.t. |A′| = n^O(1) and depth(A′) = O(log n).

Question 4

What is the combinatorial lemma?

Answer 4

Let T be a binary tree. Then there is a subtree S of T s.t.
1/3 |T| < |S| ≤ 2/3 |T|.