<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<ul>
<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>
<li>1-tt-reducibility and m-reducibility differ on NP.</li>
<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ... more >>>

We show that in the bounded degree model for graph property testing,
adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>