Untitled Document

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

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

1-x\approx e^{-x},\quad\quad\sqrt{1-x}\approx 1-x/2,\quad\quad n!\approx(n/e)^% {n},\quad\quad\left(\frac{n}{k}\right)^{k}\leq{n\choose k}\leq\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)
For each of the following polynomials either prove that they are real stable or given a counter example showing that they are not:
1. i)
  
  Let $1\leq k\leq n$ be an integer: $p(z_{1},\dots,z_{n})=\sum_{S\in{n\choose k}}\prod_{i\in S}z_{i}$ .
2. ii)
  
  $z_{1}-z_{1}z_{2}z_{3}$
3. iii)
  
  $z_{1}z_{2}-z_{3}z_{4}$
2)

Recall the determinant maximization problem: we are given $n$ vectors $v_{1},\dots,v_{n}\in\mathbb{R}^{d}$ and an integer $k$ and we want to output a set $S\in{n\choose k}$ maximizing $\det(\sum_{i\in S}v_{i}v_{i}^{T})$ . Suppose we can solve the following concave programming relaxation deterministically in polynomial time.

$\displaystyle\max$ $\displaystyle\hskip 12.91663pt\log\sum_{S\in{n\choose k}}x^{S}\det(\sum_{i\in S% }v_{i}v_{i}^{T})$ (1.1)

s.t., $\displaystyle\hskip 12.91663pt\sum_{i}x_{i}=k,\quad\quad x_{i}\geq 0,\forall i.$

Design a deterministic algorithm that rounds the solution to the above program and obtains an $e^{k}$ -approximation for the problem.
3)

Extra Credit: Let $G$ be a graph with vertices $v_{1},\dots,v_{n}$ ; Prove or dis-prove the following polynomial is real stable.

$p(z_{v_{1}},\dots,z_{v_{n}})=\sum_{M\text{ matching}}(-1)^{|M|}\prod_{u\text{ % not saturated in M}}z_{u}$

	$\displaystyle\max$	$\displaystyle\hskip 12.91663pt\log\sum_{S\in{n\choose k}}x^{S}\det(\sum_{i\in S% }v_{i}v_{i}^{T})$		(1.1)
	s.t.,	$\displaystyle\hskip 12.91663pt\sum_{i}x_{i}=k,\quad\quad x_{i}\geq 0,\forall i.$		(1.1)