Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR18-174 | 19th October 2018

#### Parity Decision Tree Complexity is Greater Than Granularity

We prove a new lower bound on the parity decision tree complexity \$D_{\oplus}(f)\$ of a Boolean function \$f\$. Namely, granularity of the Boolean function \$f\$ is the smallest \$k\$ such that all Fourier coefficients of \$f\$ are integer multiples of \$1/2^k\$. We show that \$D_{\oplus}(f)\geq k+1\$.

This lower bound is ... more >>>

TR18-173 | 17th October 2018
Eric Allender, Rahul Ilango, Neekon Vafa

#### The Non-Hardness of Approximating Circuit Size

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME(\$n^{0.49}\$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>

TR18-172 | 11th October 2018
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

#### Building Strategies into QBF Proofs

Strategy extraction is of paramount importance for quantified Boolean formulas (QBF), both in solving and proof complexity. It extracts (counter)models for a QBF from a run of the solver resp. the proof of the QBF, thereby allowing to certify the solver's answer resp. establish soundness of the system. So far ... more >>>

Next

ISSN 1433-8092 | Imprint