Complexity of approximating CSP with balance / hard constraints

DOI10.1145/2554797.2554837MaRDI QIDQ2988897zbMATH OpenOpenAlexFDO

Authors Euiwoong Lee, Venkatesan Guruswami

Publication date 19 May 2017

Published in Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2554797.2554837

zbMATH Keywords

complexity dichotomyconstraint satisfaction problemdictatorship testinginapproximabilityrobust satisfiabilityunique games conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of approximating CSP with balance/hard constraints
• Approximation Algorithms for CSPs
• The approximability of constraint satisfaction problems
• On the efficient approximability of constraint satisfaction problems
• On the complexity of \#CSP
• The complexity of constraint satisfaction revisited
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
• Complexity and approximability of parameterized MAX-CSPs
• Complexity and Approximability of Parameterized MAX-CSPs

Cites work

• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(5)

• The balance problem of min-max systems is co-nNP hard
• Complexity of approximating CSP with balance/hard constraints
• Balanced max 2-sat might not be the hardest
• Approximation Algorithms for CSPs
• Hard constraint satisfaction problems have hard gaps at location 1

This page was built for publication: Complexity of approximating CSP with balance / hard constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988897)