16 citations · 27 across the 6 of their papers we have counts for
7 papers
Not All Saturated 3-Forests Are Tight
Heidi Gebauer, Anna Gundert, Robin A. Moser +1
A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the co…
Improving PPSZ for 3-SAT using Critical Variables
Timon Hertli, Robin A. Moser, Dominik Scheder
A critical variable of a satisfiable CNF formula is a variable that has the same value in all satisfying assignments. Using a simple case distinction on the fraction of critical va…
A Full Derandomization of Schoening's k-SAT Algorithm
Robin A. Moser, Dominik Scheder
Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running i…
Vectors in a Box
Kevin Buchin, Jiří Matoušek, Robin A. Moser +1
For an integer d>=1, let tau(d) be the smallest integer with the following property: If v1,v2,...,vt is a sequence of t>=2 vectors in [-1,1]^d with v1+v2+...+vt in [-1,1]^d, then t…
A constructive proof of the general Lovasz Local Lemma
Robin A. Moser, Gábor Tardos
The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough…
A constructive proof of the Lovasz Local Lemma
Robin A. Moser
The Lovasz Local Lemma [EL75] is a powerful tool to prove the existence of combinatorial objects meeting a prescribed collection of criteria. The technique can directly be applied…