Advanced Algorithm

Problems Min Cut $\in\text{P}$ Max Cut $\in\text{NPH}$ Polynomial Identity Testing (univariate) $\in$co $\text{NPH}$ Input: a polynomial $f\in\mathbb{F}[x]$ of degree $d$ Determine...

Problems Checking Identity $\text{EQ}(a,b)=[a=b]$ (bit string $x\in\{0,1\}^n$) Communication cost checking distinctness Input: $A,B\in\{1,2,\cdots,n\}$ Determine whether $A=B$(mult...

Metric Embedding Metric Space: $(X,d),X$ is a set and $d$ is a distance on $X$ Embedding: $\phi:X\rightarrow Y$ on two metric space $(X,d X),(Y,d Y)$ Distortion $\alpha\geq 1$: $\f...

Definition Linear Programming Problem: the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints feasible solution, feasible ar...

A Wishlist for Optimization Algorithms Nonlinear, non convex objectives Powerful enough to tackle hard problems in a systematic way, and meanwhile is still practical Becoming more...

Monte Carlo Method (P)Problem Universe $U$, subset $S\subseteq U$ where $\rho=\frac{|S|}{|U|}$ Assume a uniform sampler for elements Estimate $Z=|S|$ Monte Carlo Method (for estima...

Unique Games Conjecture Unique Label Cover(ULC): An undirected graph $G(V,E)$, $q$ colors, each dege $e$ associated with a bijection $\phi e:[q]\rightarrow[q]$. A coloring $\sigma\...