Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with CNF formulas:
TR03-050 | 16th June 2003
Daniel Král

Locally satisfiable formulas

A CNF formula is k-satisfiable if each k clauses of it can be satisfied
simultaneously. Let \pi_k be the largest real number such that for each
k-satisfiable formula with variables x_i, there are probabilities p_i
with the following property: If each variable x_i is chosen randomly and
independently to be ... more >>>

TR22-123 | 4th September 2022
Alexander A. Sherstov

The Approximate Degree of DNF and CNF Formulas

The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ essentially matching the trivial upper bound of $n.$ This ... more >>>

ISSN 1433-8092 | Imprint