BOOLEAN CIRCUIT COMPLEXITY

TAKE-HOME EXAM

given: February 12, 1994 due: February 15, 1994

Answer all questions, as clearly and as concisely as possible.

Question 1

In this question you are guided in the construction of an O(log n) depth circuit for computing the product ∏_{i=1}^{n} x_{i}, where each x_{i} is an n-bit integer.

1. Let p be a fixed number. Construct an O(log n) depth circuit that receives an n-bit binary representation of a number x and return the binary representation of x mod p.

2. Let p be a O(log n)-bit prime number and let a be a primitive element modulo p. Construct an O(log n) depth circuit that receives a n-bit number x and computes its discrete logarithm modulo p, i.e., a number y such that x ≡ a^{y} (mod p). Note that the discrete logarithm is not defined when p | x.

3. Let p be a O(log n)-bit prime number and let a be a primitive element modulo p. Construct an O(log n) depth circuit for exponentiation modulo p, i.e., a circuit that given an n-bit number x, computes a^{x} mod p.

4. Construct an O(log n) depth circuit for computing ∏_{i=1}^{n} x_{i}, where each x_{i} is an n-bit integer. (Hint: Evaluate the product modulo sufficiently many small prime numbers and then use the chinese remainder theorem.)

Question 2

The element distinctness function ED_{n} receives n input bits arranged in n/(2 log n) blocks of 2 log n bits each. The function outputs 1 if and only if all the input blocks are distinct.

1. Construct a circuit that computes ED_{n}. The size of your circuit should be as small as possible.

2. What is the formula complexity of ED_{n} over the basis U_{2}?

Question 3

Obtain an almost tight lower bound on the monotone complexity of CLIQUE_{4} (n).

Question 4

1. Show that the multiplication of two n-bit numbers is not in AC^{0}.

2. Show that MOD_{4}(x_{1}, …, x_{n}), i.e., the function that outputs 1 if and only if the number of 1’s in the input is not divisible by 4, can be computed by a constant depth polynomial size circuit that uses unbounded fan-in AND, XOR and NOT gates.

3. Show that any symmetric function can be computed by a constant depth polynomial size circuit that uses unbounded fan-in threshold gates. What is the minimum depth required?

Question 5

Let BM_{n} be a function of n^{2} variables that corresponds to the possible edges of a bipartite graph with two sides of n vertices each. The function BM_{n} outputs 1 if and only if the graph that corresponds to the n^{2} input bits contains a perfect matching.

1. Describe the communication problem that captures to the monotone depth of the function BM_{n}.

2. Describe a protocol for the solution of this communication problem. Your protocol should be as efficient as possible.