Lesson 1

Basic Problems.

1. (10 points) A sequence of integers is said to have a majority element if more than half of its entries are the same. Design a one-sided error randomized algorithm that checks whether a given sequence of length \(n\) has a majority element in time \(O(n)\). Whenever the algorithm outputs an element, it should be the majority element; if a majority element exists, the probability that the algorithm reports that there is no majority element should be at most \(0.1\).
   Hint:

   Consider picking an element at random from the sequence and verifying if it is indeed the majority element. How many such independent trials are needed to ensure that the probability of missing the majority element is sufficiently small?
2. (10 points) Prove that the expected running time of Randomized QuickSelect is \(O(n)\).
   Hint:

   The time taken on a sequence of length \(n\) is the time taken on a sequence of length \(3n/4\) plus the time to reduce the size to \(3n/4\). Show that the expected value of the last summand is \(O(n)\).
3. (10 points) Show that the number of minimum cuts in a connected undirected graph on \(n \ge 2\) vertices is at most \(\binom{ n }{ 2 }\).
4. (10 points) We have a CNF formula with \(3m\) clauses: exactly \(m\) unit clauses (length \(1\)), \(m\) clauses of length \(2\), and the remaining clauses have length at least \(3\). Assume that the literals in each clause involve distinct variables. Prove that one can satisfy at least \(\frac{17}{8}m\) clauses simultaneously.
   Hint:

   Consider assigning a value of True or False to each variable independently and uniformly at random. Calculate the probability that a clause of length \(k\) is satisfied under this random assignment.
5. (15 points) Construct a linear time deterministic algorithm to output a coloring/cut achieving at least \(\frac{|E|}{2}\) edges across the cut.
6. (15 points) Let \(v_{1},…,v_{n} \in \mathbb{R}^{n}\) be vectors such that \(|v_{i}|=1\). Prove that there exist \(\varepsilon_{i} \in \{1,-1\}\) such that \(\bigl|\sum \varepsilon_{i} v_{i}\bigr| \le \sqrt{n}\), and also \(\delta_{i} \in \{1,-1\}\) such that \(\bigl|\sum \delta_{i} v_{i}\bigr| \ge \sqrt{n}\).
   Hint:

   Consider choosing the signs \(\sigma_{i}\) independently and uniformly at random from the set \(\{-1, 1\}\). Calculate the expected value of the squared norm of the sum \(\sum \sigma_{i} v_{i}\).
7. (15 points) Prove that for any graph \(G = (V,E)\), the following inequality holds: \[\alpha(G) \ge \sum_{v \in V}\frac{1}{\deg(v)+1},\] where \(\alpha(G)\) denotes the maximum size of an independent set in \(G\).
   Hint:

   Consider a random ordering (permutation) of the vertices of \(G\). Construct a set \(S\) by selecting a vertex if and only if it appears before all of its neighbors in the random ordering.
8. (15 points) Let \(A_{1}, …, A_{m}\) be sets of size \(a\), and let \(B_{1}, …, B_{m}\) be sets of size \(b\), such that \(A_{i} \cap B_{j} = \varnothing\) if and only if \(i = j\). Prove that \(m \le \binom{a+b}{a}\).
9. (15 points) Let \(n, k, t\) be integers and let \(p \in (0, 1)\). Prove that if \[\binom{n}{k}p^{\binom{k}{2}}+ \binom{n}{t}(1-p)^{\binom{t}{2}}< 1,\] then the Ramsey number satisfies \(R(k, t) > n\).
10. (20 points) Let \(d > 1\) be a real number, and let \(G(V, E)\) be a graph with \(n\) vertices and \(nd/2\) edges. Prove that \(\alpha(G) \ge \frac{n}{2d}\).
11. (20 points) Prove that the deterministic communication complexity of string equality is \(n\).
12. (20 points) In this problem, we'll design a protocol for confidential computation.

    Three cryptographers went out to dinner. At the end of the meal, the waiter approached them and said that the dinner had been paid for anonymously. The cryptographers know that it was paid either by one of the three of them or by a security agency. They respect each other’s wish to remain anonymous, but they still want to find out whether one of them paid or the agency did. How can they learn this without discovering who exactly paid (in the case that one of them did)?

    In this toy formulation, each cryptographer could write down a bit of information on a piece of paper (whether she paid for the dinner or not), fold it, and put it into a hat. After that, they could take all the slips out of the hat and open them. However, we are interested in a solution without such a centralized server (the hat) to which all other machines (cryptographers) send their data. Accordingly, we are looking for a solution in which the cryptographers learn the correct answer and learn nothing about the payer, after exchanging some number of messages with one another.

13. (Improving Karger's Algorithm) Assume that \(G=(V,E)\) is an undirected multigraph with \(n=|V|\), and fix some minimum cut \(C\) of \(G\).
    • (3 points) Suppose we start from a graph on \(r\) vertices and run the random contraction process until exactly \(t\) vertices remain, where \(2 \le t \le r\). Prove that the probability that no edge of the fixed minimum cut \(C\) is contracted is at least \[\frac{t(t-1)}{r(r-1)}.\]
    
    
    • (2 points) For which \(t = t(n)\) is the probability of contracting from \(n\) vertices down to \(t\) vertices, such that the cut \(C\) survives, about \(\frac{1}{2}\)?
    
    
    • (3 points) The idea of the improved algorithm is that at the beginning the probability that \(C\) survives is very high, but at the end it is very low. So we can try to do the first few random contractions and then solve recursively.
      Explain why the following naive recursive idea is not sufficient to substantially improve the basic algorithm: contract down to \(t\) vertices, recurse on the contracted graph, and return the answer.
    
    
    • (10 points) Design a recursive algorithm such that if \(P(n)\) is the probability that your algorithm outputs the fixed minimum cut \(C\) on an \(n\)-vertex graph. Then \[P(n)\ge 1-\left(1-\frac{1}{2} P\!\left(\frac{n}{\sqrt2}\right)\right)^{2} \ge P\!\left(\frac{n}{\sqrt2}\right)-\frac{1}{4} P\!\left(\frac{n}{\sqrt2}\right)^{2}.\]
    
    
    • (2 points) Prove that \[P(n)=\Omega\!\left(\frac{1}{\log n}\right).\] And finish with a final algorithm with running time \(O(n^{2} \log^{2} n)\) and constant error probability.
    
    

14. Let \(G\) be a graph with \(|V(G)| = n\) and let \(d = 2|E(G)|/n\) be the average degree of \(G\).
    • (20 points) Show that if there exist positive integers \(t, a, m, r\) such that \[\frac{d^{t}}{n^{t-1}}- \binom{n}{r}\!\left(\frac{m}{n}\right)^{t}\ge a,\] then \(G\) contains a subset \(U\) of at least \(a\) vertices such that every subset \(R \subset U\) of size \(|R| = r\) has at least \(m\) common neighbours.
    
    
    • (10 points) Let \(G\) be a graph, \(a, m, r\) be positive integers and suppose there exists a subset \(U \subset V(G)\) of at least \(a\) vertices such that every subset \(R \subset U\) of size \(r\) has at least \(m\) common neighbours. Prove that if \(H\) is a bipartite graph on vertex sets \(A\) and \(B\) such that \(|H| \le m\), \(|A| \le a\) and every vertex in \(B\) has degree at most \(r\), then \(H\) is a subgraph of \(G\).
    
    
    • (10 points) For a graph \(H\) and an integer \(n\), the Turán number \(\operatorname{ex}(n,H)\) denotes the maximum number of edges in a graph on \(n\) vertices which does not contain \(H\) as a subgraph.
      Let \(H\) be a bipartite graph on vertex sets \(A\) and \(B\) such that all vertices in \(B\) have degree at most \(r\). Prove that there exists some constant \(c = C(H)\) such that \[\operatorname{ex}(n,H) \le c n^{2 - 1/r}.\]