Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with correlation bound:
TR14-184 | 29th December 2014
Ruiwen Chen, Valentine Kabanets

Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there ... more >>>

TR22-182 | 16th December 2022
Prahladh Harsha, Tulasi mohan Molli, A. Shankar

Criticality of AC0-Formulae

Revisions: 1

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function $f : \{0, 1\}^n\to \{0, 1\}$ is the minimum $\lambda \geq 1$ such that for all positive integers $t$,
\[Pr_{\rho\sim R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^t.\]
Håstad’s celebrated switching lemma ... more >>>

TR23-176 | 15th November 2023
William Hoza

A Technique for Hardness Amplification Against $\mathrm{AC}^0$

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $k = 1$ is resolved by Håstad, Rossman, ... more >>>

ISSN 1433-8092 | Imprint