There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that ${\rm LFP}_{\rm inv}$, the ``order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is ... more >>>

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

Recently, Moser and Tardos [MT10] came up with a constructive proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.

more >>>