Larrauri and Živný [ICALP’24/ACM ToCL’24] recently established a complete complexity classification of the problem of solving a system of equations over a monoid \({N}\) assuming that a solution exists over a monoid \({M}\) , where both monoids are finite and \({M}\) admits a homomorphism to \({N}\) . Using the algebraic approach to promise constraint satisfaction problems, we extend their complexity classification in two directions: we obtain a complexity dichotomy in the case where arbitrary relations are added to the monoids, and we moreover allow the monoid \({M}\) to be finitely generated.

It is an open question whether the search and decision versions of promise CSPs are equivalent. Most known algorithms for PCSPs solve only their decision variant, and it is unknown whether they can be adapted to solve search as well. The main approaches, called BLP, AIP and BLP + AIP, handle a PCSP by finding a solution to a relaxation of some integer program. We prove that rounding those solutions to a proper search certificate can be as hard as any problem in the class TFNP. In other words, these algorithms are ineffective for search. Building on the algebraic approach to PCSPs, we find sufficient conditions that imply ineffectiveness for search. Our tools are tailored to algorithms that are characterized by minions in a suitable way, and can also be used to prove undecidability results for meta-problems. This way, we show that the families of templates solvable via BLP, AIP, and BLP + AIP are undecidable. Using the same techniques we also analyze several algebraic conditions that are known to guarantee the tractability of finite-template CSPs. We prove that several meta-problems related to cyclic polymorphims and WNUs are undecidable for PCSPs. In particular, there is no algorithm deciding whether a finite PCSP template (1) admits cyclic a polymorphism, (2) admits a WNU.

A celebrated result of Håstad established that, for any constant ε > 0, it is NP-hard to find an assignment satisfying a (1/|G|+ε)-fraction of the constraints of a given 3-LIN instance over an Abelian group G even if one is promised that an assignment satisfying a (1-ε)-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3-LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3-LIN the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3-LIN instance is almost satisfiable over an arbitrarily more restrictive group.

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 constant edge probability, where the probabilities of first-order sentences converge to 0 or 1. In other cases, such as certain "sparse random graph" models, the probabilities of sentences converge, although not necessarily to 0 or 1. In this work we deal with extensions of first-order logic with aggregate operators, variations of averaging. These logics will consist of real-valued terms, and we allow arbitrary Lipschitz functions to be used as "connectives". We show that some of the well-known convergence laws extend to this setting.

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 restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups.

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 restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups.

Testing analog integrated circuit (IC) designs is notoriously hard. Simulating tens of milliseconds from an accurate transistor level model of a complex analog design can take up to two weeks of computation. Therefore, the number of tests that can be executed during the late development stage of an analog IC can be very limited. We leverage the recent advancements in machine learning (ML) and propose two techniques, artificial neural networks (ANN) and Gaussian processes, to learn a surrogate model from an existing test suite. We then explore the surrogate model with Bayesian optimization to guide the generation of additional tests. We use an industrial bandgap case study to evaluate the two approaches and demonstrate the virtue of Bayesian optimization in efficiently generating complementary tests with constrained effort.

Abstract We extend the convergence law for sparse random graphs proven by Lynch to arbitrary relational languages. We consider a finite relational vocabulary $\sigma $ and a first-order theory $T$ for $\sigma $ composed of symmetry and anti-reflexivity axioms. We define a binomial random model of finite $\sigma $-structures that satisfy $T$ and show that first-order properties have well defined asymptotic probabilities when the expected number of tuples satisfying each relation in $\sigma $ is linear. It is also shown that these limit probabilities are well behaved with respect to several parameters that represent the density of tuples in each relation $R$ in the vocabulary $\sigma $. An application of these results to the problem of random Boolean satisfiability is presented. We show that in a random $k$-CNF formula on $n$ variables, where each possible clause occurs with probability $\sim c/n^{k-1}$, independently any first-order property of $k$-CNF formulas that implies unsatisfiability does almost surely not hold as $n$ tends to infinity.