Approximating Good Simultaneous Diophantine Approximations Is Almost NP-Hard

Let 1< p , and let H _p (U) denote the family of all functions f that are analytic in the unit disc U such that $$\parallel f\parallel _p = \mathop {\lim }\limits_{r \to 1^ - } \left( {\frac{1}{{2\pi }}\int\limits_0^{2\pi } {|f(re^{i\theta }...

For a graph G with n vertices and m edges, we give a randomized Las Vegas algorithm that approximates a small balanced vertex separator of G in almost linear time. More precisely, we show the following, for any $$\frac{2}{3}\le \alpha <1$$ and any ...

Let $\mathcal{F}$ be a set system over an underlying finite set $X$, and let $\mu$ be a nonnegative measure over $X$; i.e., for every $S \subseteq X$, $\mu(S)=\sum_{x\in S} \mu(x)$. A measure $\mu^*$ on $X$ is called a multiplicative ${\lambda}$-...