Tcs.tifr.res.in

• If you submit handwritten solutions, start each problem on a fresh page.
• Collaboration is encouraged, but all writeups must be done individually and must include names of all • Referring sources other than the lectures is strongly discouraged. But if you do use an outside source (eg., other text books, lecture notes, any material available online), ACKNOWLEDGE it in yourwriteup.
• The points for each problem are indicated on the side.
• If you don’t know the answer to a problem, then just don’t answer it. Do not try to convince yourself or others into believing a false proof.
The universal relation Un is defined as follows.
Un = {(x, y, i) ∈ {0, 1}n × {0, 1}n × [n] : xi = yi}.
Alice is given x ∈ {0, 1}n and Bob y ∈ {0, 1}n such that x = y. They have to determine an i such that(x, y, i) ∈ Un.
In this problem, we will show that there is a randomized public coins protocol, where • Alice sends one message of O((log n)2) bits; • Bob determines an i such that (x, y, i) ∈ Un; (a) [Identify] Give an O(log n) bit protocol that makes error at most 1/3 under the promise that x and y differ in only one position. (There is a deterministic protocol but a randomized protocolwould suffice.) (b) [Isolate] Now for the general case, when x and y may differ in more than one position. Using shared randomness, devise a distribution for sets S1, S2, ., S ⊆ [n] ( = O(log n)), such that withconstant probability there is an i such that x|S and y| (c) [Verify] Suppose Alice has x and Bob has (y, i). Give a constant protocol in which Alice sends O(1) bits and Bob verifies with probability at least 2/3 that x and y differ only at i.
(d) Combine the above parts to obtain the one-round randomized protocol for the universal relation.
In the second part of this problem, we will show that any public coins randomized protocol (errorat most 1 ) for the universal relation where Alice sends just one message, requires Ω((log n)2) bits of Use the following augmented index function problem.
u1, ., ui−1; Alice sends one message and Bob determines ui. (Later we will set L to be about log n.) (e) Any randomized (public coins) protocol for this augmented index function problem requires Ω(L2) (f) [Reduction] Suppose Alice needs to send a number z ∈ [L] to Bob. Show how you will do this using a protocol for the universal relation on L bit inputs. That is, Alice transforms her input ito f (i) ∈ {0, 1}L and Bob produces an input v ∈ {0, 1}L; they run the protocol for the universalrelation, and from the output Bob determines z.
(g) Use the reduction in part (f) appropriately to u1, ., uL, thereby producing inputs to the universal function problem of size n = L2. In other words, give a reduction such that Alice transforms herinput u[1,L] = (u1, . . . , uL) to an input in {0, 1}L2 and Bob transforms his input (u[1,i−1], i) to aninput in {0, 1}L2 such that when they run the universal relation protocol on these transformedinputs, Bob recovers one of ui, ui+1, ., uL.
(h) Use public randomness and increase the input length to 2O(L) to ensure that with high probability the protocol actually helps Bob recover ui itself.
Suppose Alice and Bob are given k-sized subsets of [n] each and they have to determine if the setsare disjoint. Call this problem DISJn,k. Show that the randomized public coins (error at most 1 ) complexity of DISJn,k is O(k). (Observe that an O(k log n) protocol is easy to obtain.) The followinghints might help you in constructing the protocol • [Small sets] Suppose k is constant. Hash into some O(k2) bits using public randomness, and determine the answer with O(k2) bits of communication.
• [Shrinking the bigger set]. Proceed as in the protocol for product distributions. Suppose the sets have sizes s, t (s ≤ t ≤ k). Alice picks a random superset of her input and sends it to Bob withO(s) bits of communication (use shared randomness). Bob restricts his input to inside this set. Ifthis does not result in significant decrease in the size of Bob’s set, then the sets probably intersectheavily (by Chernoff). Repeat, keeping the total error in control until the sets become small andapply the base case above.
[Kushilevitz-Nisan, Exercise 5.21] Let FORK be the relations consisting of triples (x, y, i) such thatx, y ∈ Σ , and is is such that xi = yi and xi+1 = yi+1 or xi−1 = yi−1. Prove that D(FORK ) =Ω(log , log w).
4. [s-t connectivity: asymmetry in KW result] Karchmer and Wigderson showed that any monotone circuits for s-t connectivity on n-vertex graphs, where ANDs have fanin at most 2n1/5 and ORs have fanin at most n1/5, must have depth Ω(log n).
Observe that there exist shallow circuits in which that AND and OR fanins are reversed.
Now, consider the s-t cut function, which is true on an n vertex directed graph if its complement hasno s-t path. Like the s-t connectivity problem, this is a monotone function defined on n × n adjacencymatrices (no self-loops, parallel edges).
A monotone projection from s-t connectivity (on n vertex graphs) to s-t cut (on N vertex graphs) is afunction from f : [N ] × [N ] → [n] × [n], such that the n × n adjacency matrix A = (ai,j) is s-t connectediff the N × N matrix B = (bk, ) where bk,l = af(k,l) is s-t cut. Show that no such projection exists ifN is polynomially bounded in n.
(a) Let f (x1, . . . , x2k+1) = maj(x1, . . . , x2k+1). Let Alice be given the first k+1 bits, i.e., x1, . . . , x2k+1 and Bob the next k bits. Show that there exists an O(1)-randomized protocol with error at most 1 − O 1 that computes f . Conclude that maj has discrepancy at least Ω(1/k) with respect to (b) Now, consider a function f on 2k variables defined as a depth 2 AC0 circuit as follows: f (x1, . . . , x2k) = T1 ∨ T2 ∨ · · · ∨ Tl where the Ti’s are conjunction of literals. Let Alice be giventhe first k bits of x1, . . . , x2k and Bob the next k bits. Show that there exists an O(1)-randomizedprotocol with error at most 1 − O 1 that computes f . Conclude that any depth 2 AC0 circuit with top fan-in s has discrepancy at least Ω(1/s) with respect to every distribution.
6. [communication complexity of GT and LTF] (a) Given two n bit integers 0 ≤ x, y < 2n, “greater than” function GT(x, y) = 1 iff x > y.
Using one of the theorems proved/stated in lecture, show that Rε(GT) = O log n + log 1 (b) Let a1, . . . , an, b1, . . . , bn, θ ∈ R. Then, the linear threshold function corresponding to (a, b, θ) where a = (a1, . . . , an) and b = (b1, . . . , bn) is defined as follows Show using part (a) or otherwise that Rε(LTFa,b,θ) = O log n + log 1 [Hint: Try to bound the size of the “possible” numbers ai, bi, θ.] In a simultaneous message protocol (SMP), Alice and Bob send a message each (based on their respec-tive inputs) to a referee, who must then announce the result.
(a) Show that there is a private coins simultaneous messages protocol for EQn where Alice and Bob (b) Suppose there is a simultaneous messages private coins randomized protocol for a function f , where Alice sends messages of length a and Bob sends messages of length b. Show that then thereis a deterministic one-way communication protocol for f with communication O(ab). Conclude that the private coins simultaneous message complexity of EQn is at least Ω( n).
[Hint: View the referee’s actions as a matrix with rows indexed by messages of Alice (∈ {0, 1}a)and columns by message of Bob (∈ {0, 1}b). Show that for each input x, Alice can send Bob a(multi-)set Sx ⊆ {0, 1}a of O(b) row indices (use Chernoff bounds to show the existence of suchSx); Bob can then restrict himself to these rows, and based on the distribution of his messagesin the simultaneous protocol, simulate the referee’s actions faithfully.] 8. [A direct sum result for simultaneous message protocols.] Consider the direct sum problem for m copies of EQn in the SMP model: so, Alice gets x1, x2, . . . , xm ∈{0, 1}n and Bob gets y1, y2, . . . , ym ∈ {0, 1}n, and they need to determine the answers for all minstances.
Complete the following argument to show that the simultaneous messages randomized private coins communication complexity of this problem is Ω(m n).
(a) Consider a distribution on Alice’s inputs, where each coordinate is chosen independently. Show that if Alice sends a bits and Bob sends b bits, then there is a coordinate for which they sendonly O(a/m) bits and O(b/m) bits of information to the referee.
(b) Show that Alice’s message can be compressed to O(a/m) bits for most of her inputs. Let X be the input of Alice and let M be her message. Suppose I[X : M ] ≤ α. Let P be the distributionof M . Let Px be the distribution of M conditioned on X = x.
x P ). Observe that for most (define ‘most’ appropri- ately) values x, S(Px P ) = O(α); call such x good.
ii. Prove the following. There are constants A and B, such if S(Px P ) ≤ s, then for all ε > 0, iii. Assume that Alice and the referee share independent samples of M (generated according to P ). Show that Alice, on receiving a good x may then send O(S(Px P )/ε) bits to the refereeand help him select a sample whose distribution is close (how close?) to Px.
(c) Prove the result (Ω(m n) bound) using the previous two exercises. Note that there the coins were private. What distributions will you choose for the inputs?

Source: http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/psets/pset3.pdf