Andreas Basse-O’Connor

collaborators

Showing math.PRShow all

3 papers · 1 filter

math.PR2025

Degrees of Freedom for Critical Random 2-SAT

Andreas Basse-O'Connor, Mette Skjøtt

The random $k$ -SAT problem serves as a model that represents the 'typical' $k$ -SAT instances. This model is thought to undergo a phase transition as the clause density changes, and…

math.PR2025

On the Regularity of Random 2-SAT and 3-SAT

Andreas Basse-O'Connor, Tobias Lindhardt Overgaard, Mette Skjøtt

We consider the random $k$ -SAT problem with $n$ variables, $m = m (n)$ clauses, and clause density $α = lim_{n \to \infty} m / n$ for $k = 2, 3$ . It is known that if $α$ is small enough, then…

math.PR2023

Some Results on Random Mixed SAT Problems

Andreas Basse-O'Connor, Tobias Lindhardt Overgaard, Mette Skjøtt

In this short paper we present a survey of some results concerning the random SAT problems. To elaborate, the Boolean Satisfiability (SAT) Problem refers to the problem of determin…