Ben-Sasson and Sudan in~\cite{BS04} asked if the following test
is robust for the tensor product of a code with another code--
pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that ... more >>>

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables .
Assume that this polynomial satisfies the property : \\

$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$ . \\

We prove that ... more >>>

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>