## Impagliazzo’s Hardcore Lemma and Computational Hardness

We wish to compute boolean functions by circuits, or more generally, compositions of simple boolean functions (gates). Suppose we are given a function which is hard to approximate by any small-size circuit. That is, any small-size circuit fails to compute

Tagged with: ,
Posted in Theory

## Sperner Theorem on Maximal Antichains

Let $$S$$ be a family of subsets of $$\{1,\ldots,n\}$$ such that no set in $$S$$ contains another. This is often called an antichain. Theorem. [Sperner’s Theorem] $|S| \leq {n \choose \lfloor n/2 \rfloor}.$ The proof of Sperner’s Theorem

Tagged with: , ,
Posted in Theory

## Kolmogorov Complexity

Kolmogorov complexity measures the complexity of describing an object, such as a binary string. The description is considered as a program which can be run on a computer. By Church’s thesis, all non-trivial computational models are equivalent; thus, one can

Tagged with: ,
Posted in Probability, Theory

## Decision Tree Complexity

Decision trees are a simple computation model. One can compute a boolean function using a decision tree by examining the input bits in specific orders. The complexity is characterized by the number of input bits examined, or simply, the depth

Tagged with: ,
Posted in Theory