We prove that, with high probability, the space complexity of refuting
a random unsatisfiable boolean formula in $k$-CNF on $n$
variables and $m = \Delta n$ clauses is
$O(n \cdot \Delta^{-\frac{1}{k-2}})$.

more >>>

Many of the keystream generators which are used in practice are LFSR-based in the sense
that they produce the keystream according to a rule $y=C(L(x))$,
where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel
linear feedback shift registers (LFSRs),
and $C$ denotes ... more >>>

We study interval-valued constraint satisfaction problems (CSPs),
in which the aim is to find an assignment of intervals to a given set of
variables subject to constraints on the relative positions of intervals.
Many well-known problems such as Interval Graph Recognition
and Interval Satisfiability can be considered as examples of ... more >>>