Long Code testing is a fundamental problem in the area of property
testing and hardness of approximation.
Long Code is a function of the form $f(x)=x_i$ for some index $i$.
In the Long Code testing, the problem is, given oracle access to a
collection of Boolean functions, to decide whether ... more >>>

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajLos calculus is polynomially bounded.

more >>>

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou
studied in [Gopalan et al., ICALP2006] connectivity properties of the
solution-space of Boolean formulas, and investigated complexity issues
on connectivity problems in Schaefer's framework [Schaefer, STOC1978].
A set S of logical relations is Schaefer if all relations in ... more >>>

This paper presents a new upper bound for the
$k$-satisfiability problem. For small $k$'s, especially for $k=3$,
there have been a lot of algorithms which run significantly faster
than the trivial $2^n$ bound. The following list summarizes those
algorithms where a constant $c$ means that the algorithm runs in time
more >>>