English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the Boolean maximum constraint satisfaction problem - Max CSP$(\Gamma)$ -one is given a collection of weighted applications of constraints from a finiteconstraint language $\Gamma$, over a common set of variables, and the goal isto assign Boolean values to the variables so that the total weight of satisfiedconstraints is maximized. There exists an elegant dichotomy theorem providing acriterion on $\Gamma$ for the problem to be polynomial-time solvable andstating that otherwise it becomes NP-hard. We study the NP hard cases throughthe lens of kernelization and provide a complete characterization of MaxCSP$(\Gamma)$ with respect to the optimal compression size. Namely, we provethat Max CSP$(\Gamma)$ parameterized by the number of variables $n$ is eitherpolynomial-time solvable, or there exists an integer $d \ge 2$ depending on$\Gamma$, such that  1. An instance of \textsc{Max CSP$(\Gamma)$} can be compressed into anequivalent instance with $O(n^d\log n)$ bits in polynomial time,  2. Max CSP$(\Gamma)$ does not admit such a compression to $O(n^{d-\epsilon})$bits unless $\text{NP} \subseteq \text{co-NP} / \text{poly}$.  Our reductions are based on interpreting constraints as multilinearpolynomials combined with the framework of constraint implementations. Asanother application of our reductions, we reveal tight connections betweenoptimal running times for solving Max CSP$(\Gamma)$. More precisely, we showthat obtaining a running time of the form $O(2^{(1-\epsilon)n})$ for particularclasses of Max CSPs is as hard as breaching this barrier for Max $d$-SAT forsome $d$.

Optimal polynomial-time compression for Boolean Max CSP