Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

DOI10.1137/19M1291054OpenAlexW4280572229MaRDI QIDQ5864666

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

Publication date: 8 June 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m1291054

zbMATH Keywords

algorithmscomputational complexityconstraint satisfaction problemserror-correcting codes

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of approximating CSP with balance/hard constraints
• Constructing Ramsey graphs from Boolean function representations
• The complexity of surjective homomorphism problems-a survey
• Structure identification of Boolean relations and plain bases for co-clones
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• A lower bound on the MOD 6 degree of the OR function
• On the algebraic structure of combinatorial problems
• Representing Boolean functions as polynomials modulo composite numbers
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
• Which problems have strongly exponential complexity?
• Submodular minimization under congruency constraints
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Closed systems of functions and predicates
• 2-Server PIR with Sub-Polynomial Communication
• Nonuniform Boolean constraint satisfaction problems with cardinality constraint
• The complexity of global cardinality constraints
• Matching Vector Codes
• On the efficiency of local decoding procedures for error-correcting codes
• Short monotone formulae for the majority function
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Towards 3-query locally decodable codes of subexponential length
• Two-query PCP with subconstant error
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• 3-Query Locally Decodable Codes of Subexponential Length
• A strongly polynomial algorithm for bimodular integer linear programming
• Intermediate problems in modular circuits satisfiability
• Linear Systems over Composite Moduli
• New Bounds for Matching Vector Families
• Breaking the circuit-size barrier in secret sharing
• Classifying the Complexity of Constraints Using Finite Algebras
• New hardness results for graph and hypergraph colorings
• The complexity of satisfiability problems
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• A new contraction technique with applications to congruency-constrained cuts
• A new contraction technique with applications to congruency-constrained cuts
• On the complexity of \(k\)-SAT

This page was built for publication: Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations