• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site

## An improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances''

P. 203-2011.

Assume that \$\NP\not\subset\RP\$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm \$D\$ for SAT there is a polynomial time samplable distribution such that \$D\$ errs with probability at least \$1/6-\eps\$ on a random formula chosen with respect to that distribution. A challenging problem is to increase the error probability to the maximal possible \$1/2-\eps\$ (the random guessing has success probability 1/2). In this paper, we make a small step towards this goal: we show how to increase the error probability to \$1/3-\eps\$.

### In book

Berlin: Springer, 2013.