4 papers
Hardness of some optimization problems over correlation polyhedra
Alberto Caprara, Fabio Furini, Claudio Gentile +2
We prove the \textbf{NP}-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the rank-on…
Mathematics with large language models as provers and verifiers
Hieu Le Duc, Leo Liberti
During 2024 and 2025 the discussion about the theorem-proving capabilities of large language models started reporting interesting success stories, mostly to do with difficult exerc…
On Saxe's theorems about the complexity of the Distance Geometry Problem
Maël Kupperschmitt, Leo Liberti
In 1979, James B.~Saxe published an extended summary on the complexity of the Distance Geometry Problem in the proceedings of the 17th Allerton Conference. Many of the proofs in hi…
Unassigned distance geometry and the Buckminsterfullerene
Leo Liberti
The Buckminsterfullerene is an inorganic molecule consisting of 60 carbon atoms in the shape of a soccer ball. It was used in [Juhas et al., Nature 2006] to showcase algorithms tha…