Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > K-DNF FORMULAS:
Reports tagged with k-DNF formulas:
TR09-100 | 16th October 2009
Jakob Nordström, Alexander Razborov

#### On Minimal Unsatisfiability and Time-Space Trade-offs for \$k\$-DNF Resolution

In the context of proving lower bounds on proof space in \$k\$-DNF
resolution, [Ben-Sasson and Nordstr&ouml;m 2009] introduced the concept of
minimally unsatisfiable sets of \$k\$-DNF formulas and proved that a
minimally unsatisfiable \$k\$-DNF set with \$m\$ formulas can have at most
\$O((mk)^{k+1})\$ variables. They also gave an example of ... more >>>

TR18-010 | 14th January 2018
Alexander A. Sherstov

#### Algorithmic polynomials

The approximate degree of a Boolean function \$f(x_{1},x_{2},\ldots,x_{n})\$ is the minimum degree of a real polynomial that approximates \$f\$ pointwise within \$1/3\$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

ISSN 1433-8092 | Imprint