randomness in TCS

Sums of independent random variables with unbounded variance ★★

Author(s): Feige

\begin{conjecture} If $X_1, \dotsc, X_n \geq 0$ are independent random variables with $\mathbb{E}[X_i] \leq \mu$, then $$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$ \end{conjecture}

Keywords: Inequality; Probability Theory; randomness in TCS

Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

\begin{conjecture} For every rational $\epsilon > 0$ and every rational $\Delta$, there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula $I$ on $n$ variables, for some $n$, and $m = \floor{\Delta n}$ clauses drawn uniformly at random from the set of formulas on $n$ variables. Return with probability at least 0.5 (over the instances) that $I$ is \textit{typical} without returning \textit{typical} for \textit{any} instance with at least $(1 - \epsilon)m$ simultaneously satisfiable clauses. \end{conjecture}

Keywords: NP; randomness in TCS; satisfiability

Syndicate content