CSE 525: Randomized Algorithms and Probability Spring 2026 HW3 Submit to gradescope

Instructions

• You should think about each problem by yourself for at least an hour before choosing to collaborate with others.

• You are allowed to collaborate with fellow students taking the class in solving the problems. But you must write your solution on your own.

• You are not allowed to search for answers or hints on the web. You are encouraged to contact the instructor or the TAs for a possible hint.

• You cannot collaborate on Extra credit problems

• Solutions typeset in LATEX are preferred.

• Feel free to use the Discussion Board or email the instructor or the TAs if you have any questions or would like any clarifications about the problems.

• Please upload your solutions to Gradescope.

 

In solving these assignments, feel free to use these approximations:

$$1-x\approx e^{-x},\sqrt{1-x}\approx 1-x/2,n!\approx {(n/e)}^n,{\left(\frac{n}{k}\right)}^k\le \left(\genfrac{}{}{0pt}{}{n}{k}\right)\le {\left(\frac{en}{k}\right)}^k$$

The problems of this HW are hard. To get full points it is enough to solve one of the following problems, although you are encouraged to try both.

1. Let $G=(V,E)$ be an undirected graph and suppose each $v\in V$ is associated with a set $S(v)$ of $8r$ colors, where $r\ge 1$. Suppose further that for each $v\in V$ and $c\in S(v)$ there are at most $r$ neighbors $u$ of $v$ such that $c$ lies in $S(u)$.

   • Prove that there exists a proper coloring of $G$ assigning to each vertex $v$ a color from its class $S(v)$ such that, for any edge $u\sim v$, the colors assigned to $u$ and $v$ are different.

   • Design a randomized polynomial time algorithms. Feel free to assume $|S(v)|\ge c\cdot r$ (for all $v$) for a constant $c\gg 8$.

2. Let ${𝒜}_{\mathcal{1}},\mathrm{\dots },{𝒜}_{𝓃}$ be a set of bad events defined on independent variables $Z_1,\mathrm{\dots },Z_m$ with corresponding dependency graph $G$ (ignore conditions of the LLL for this problem). Note that $\mathbb{P}\left[\neg {𝒜}_{𝒾}\right]$ is uniquely defined as a function of the probabilities of $Z_i$’s. Prove or disprove: In the Moser-Tardos algorithm, for a fixed $t>1$ and $i\in [n]$, the probability that the $t$-th resampled event is ${𝒜}_i$ is at most $\mathbb{P}\left[{𝒜}_i\right]$. Prove this or find a counterexample.