We give a method for approximating any $n$-dimensional
lattice with a lattice $\Lambda$ whose factor group
$\mathbb{Z}^n / \Lambda$ has $n-1$ cycles of equal length
with arbitrary precision. We also show that a direct
consequence of this is that the Shortest Vector Problem and the Closest
Vector Problem cannot ... more >>>

We define a collection of Prover-Delayer games that characterize certain subsystems of resolution. This allows us to give some natural criteria which guarantee lower bounds on the resolution width of a formula, and to extend these results to formulas of unbounded initial width.

We also use games to give upper ... more >>>

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>