6 papers
Convergence Laws for Extensions of First-Order Logic with Averaging
Sam Adam-Day, Michael Benedikt, Alberto Larrauri
For many standard models of random structure, first-order logic sentences exhibit a convergence phenomenon on random inputs. The most well-known example is for random graphs with c…
Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
Alberto Larrauri
It is an open question whether the search and decision versions of promise CSPs are equivalent. Most known algorithms for PCSPs solve only their \emph{decision} variant, and it is…
Equations over Finite Monoids with Infinite Promises
Alberto Larrauri, Antoine Mottet, Stanislav Živný
Larrauri and Živný [ICALP'25/ACM ToCL'24] recently established a complete complexity classification of the problem of solving a system of equations over a monoid assuming that…
Optimal Inapproximability of Promise Equations over Finite Groups
Silvia Butti, Alberto Larrauri, Stanislav Živný
A celebrated result of Hastad established that, for any constant , it is NP-hard to find an assignment satisfying a -fraction of the constraints…
First Order Logic of Sparse Graphs with Given Degree Sequences
Alberto Larrauri, Guillem Perarnau
We consider limit probabilities of first order properties in random graphs with a given degree sequence. Under mild conditions on the degree sequence, we show that the closure set…
Solving promise equations over monoids and groups
Alberto Larrauri, Stanislav Živný
We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more rest…