Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with CSP:
TR00-042 | 21st June 2000
Lars Engebretsen

Lower Bounds for non-Boolean Constraint Satisfaction

Revisions: 1

We show that the k-CSP problem over a finite Abelian group G
cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for
any constant epsilon>0, unless P=NP. This lower bound matches
well with the best known upper bound, |G|^{k-1}, of Serna,
Trevisan and Xhafa. The proof uses a combination of PCP
techniques---most notably a ... more >>>

TR04-097 | 2nd November 2004
Víctor Dalmau

Malt'sev Constraints made Simple

We give in this paper a different and simpler proof of the tractability of Mal'tsev contraints.

more >>>

TR11-071 | 27th April 2011
Serge Gaspers, Stefan Szeider

The Parameterized Complexity of Local Consistency

Revisions: 1

We investigate the parameterized complexity of deciding whether a constraint network is $k$-consistent. We show that, parameterized by $k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size $d$ and the maximum number $\ell$ of constraints in which a variable occurs. ... more >>>

TR16-142 | 11th September 2016
Jason Li, Ryan O'Donnell

Bounding laconic proof systems by solving CSPs in parallel

Revisions: 1

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, Håstad, and ... more >>>

TR19-092 | 9th July 2019
Venkatesan Guruswami, Jakub Opršal, Sai Sandeep

Revisiting Alphabet Reduction in Dinur's PCP

Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the ... more >>>

TR19-181 | 9th December 2019
Michal Koucky, Vojtech Rodl, Navid Talebanfard

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Revisions: 1

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph on $m$ edges with bounded vertex degree has a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. ... more >>>

TR20-043 | 29th March 2020
Dorit Aharonov, Alex Bredariol Grilo

A combinatorial MA-complete problem

Revisions: 2

Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>>

ISSN 1433-8092 | Imprint