Ronen Shaltiel, Emanuele Viola

Hardness amplification is the fundamental task of

converting a $\delta$-hard function $f : {0,1}^n ->

{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,

where $f$ is $\gamma$-hard if small circuits fail to

compute $f$ on at least a $\gamma$ fraction of the

inputs. Typically, $\eps,\delta$ are small (and

$\delta=2^{-k}$ captures the case ...
more >>>

Nicola Galesi, Massimo Lauria

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

more >>>Mateus de Oliveira Oliveira, Pavel Pudlak

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of

computation for partial Boolean functions. Using this model, we prove the following results:

1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.

2. MLP circuits are exponentially stronger than monotone span programs.

3. ...
more >>>

Michel Goemans, Shafi Goldwasser, Dhiraj Holden

In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>>

Leroy Chew, Friedrich Slivovsky

We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q-Resolution, and Merge Resolution.

These results are obtained by taking a technique ...
more >>>