It is a known approach to translate propositional formulas into
systems of polynomial inequalities and to consider proof systems
for the latter ones. The well-studied proof systems of this kind
are the Cutting Planes proof system (CP) utilizing linear
inequalities and the Lovasz-Schrijver calculi (LS) utilizing
quadratic ... more >>>

Using known results regarding PCP,
we present simple proofs of the inapproximability
of vertex cover for hypergraphs.
Specifically, we show that

(1) Approximating the size of the minimum vertex cover
in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.
(2) Approximating the size ... more >>>

We present a new lower bound technique for two types of restricted
Branching Programs (BPs), namely for read-once BPs (BP1s) with
restricted amount of nondeterminism and for (1,+k)-BPs. For this
technique, we introduce the notion of (strictly) k-wise l-mixed
Boolean functions, which generalizes the concept of l-mixedness ... more >>>