203 citations · 470 across the 96 of their papers we have counts for
4 papers · 1 filter
-colouring -free graphs in subexponential time
Carla Groenland, Karolina Okrasa, Pawel Rzążewski +3
A graph is called -free if it does not contain the path on vertices as an induced subgraph. Let be a multigraph with the property that any two distinct vertices share…
Structure of random r-SAT below the pure literal threshold
Alexander D. Scott, Gregory B. Sorkin
It is well known that there is a sharp density threshold for a random -SAT formula to be satisfiable, and a similar, smaller, threshold for it to be satisfied by the pure litera…
Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP
Alexander D. Scott, Gregory B. Sorkin
The class -CSP, or simply Max 2-CSP, consists of constraint satisfaction problems with at most two -valued variables per clause. For instances with variables and …
Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function
Alexander D. Scott, Gregory B. Sorkin
We introduce a problem class we call Polynomial Constraint Satisfaction Problems, or PCSP. Where the usual CSPs from computer science and optimization have real-valued score functi…