Problem Set 2

tags: pset

Instructions

• $LATEX$ your solutions and submit them on Moodle.
• You are welcome to discuss the ideas involved in solving the problems amongst yourselves, but the solutions that you write must be your own. If you have doubts regarding what this means, please talk to me.
• Always cite sources that gave you the idea for solving a problem, including external sources. If you discussed with a friend, please mention his/her name. This will not affect your grades.
• Try to write brief answers. Only write what is necessary and sufficient.
• If you don't know an answer, just write what you know and leave the rest. Better still, discuss with me if you are stuck.

Problem 1 (

$N{C}^1$ and poly-sized formulas)

A Boolean formula is a Boolean circuit, where each gate has fan-out at most

$1$ except for the input variables. In this problem, you will prove that functions computed by polynomial-size formulas are precisely the class

$N{C}^1$.

1. [5 marks] Show that every function
   $f\in N{C}^1$ can be computed by a polynomial-size Boolean formula by duplicating the gates as necessary.

To show that every polynomial-size Boolean formula can be represented by an equivalent

$N{C}^1$ circuit, first show the following property of binary trees.

2. [5 marks] Let

   $T$ be a binary tree with
   $n$ nodes. Show that there exists a subtree
   $T^{\prime }$ of
   $T$ with
   $n^{\prime }$ nodes such that
   
   $$\frac{n}{3}\le n^{\prime }\le \frac{2n}{3}$$

3. [5 marks] Let

   $f$ be computed by a Boolean formula
   $T$ of polynomial size. Use Problem 1.2 to obtain a subformula
   $T^{\prime }$ satisfying the conditions in that problem, and let
   $f^{\prime }$ be the function computed by
   $T^{\prime }$. Express
   $f$ using
   $f^{\prime }$, and then recursively apply Problem 1.2 to show that
   $f$ can be computed in
   $N{C}^1$.

Problem 2 (

$NC$ hierarchy) [5 marks]

Show that if

$N{C}^i=N{C}^{i+1}$, then

$N{C}^j=N{C}^i$ for every

$j\ge i$.

Problem 3 [5 marks]

Show that there is a circuit of depth

$d$ and size

$2^{O(n^{1/d-1})}$ with unbounded fan-in gates that computes

${\oplus }_n$.

Problem 4 [5 marks]

Show that if

$f$ is representable as a

$k$-CNF and a

$t$-DNF, then

$f$ can be represented by a decision tree of depth

$kt$.

Problem 5 [10 marks]

The majority function is defined as

$MAJ(x_1,x_2,\dots ,x_n)=1$ iff

$\sum x_i>n/2$. Show that any depth

$d$ unbounded fan-in Boolean circuit computing majority has size

$2^{\mathrm{\Omega }(n^{1/(d-1)})}$ using the switching lemma.