A new algorithm for optimal 2-constraint satisfaction and its implications

DOI10.1016/J.TCS.2005.09.023zbMATH Open1081.68095OpenAlexW2084732238WikidataQ56806889 ScholiaQ56806889MaRDI QIDQ2581276FDOQ2581276

Authors: Ryan Williams 

Publication date: 9 January 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.023

Recommendations

• Automata, Languages and Programming
• Optimal 2-constraint satisfaction via sum-product algorithms
• New exact algorithms for the 2-constraint satisfaction problem
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

zbMATH Keywords

constraint satisfactionexact algorithmsMax-CutMax-2-Sat

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Title not available (Why is that?)
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Color-coding
• Matrix multiplication via arithmetic progressions
• Computing Partitions with Applications to the Knapsack Problem
• A simplified NP-complete MAXSAT problem
• Title not available (Why is that?)
• Finding a Minimum Circuit in a Graph
• Title not available (Why is that?)
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Algorithms for maximum independent sets
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• An improved exponential-time algorithm for k -SAT
• Title not available (Why is that?)
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Partial-Match Retrieval Algorithms
• Worst-case study of local search for MAX-\(k\)-SAT.
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Title not available (Why is that?)
• New Upper Bounds for Maximum Satisfiability
• Title not available (Why is that?)
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Faster exact algorithms for hard problems: A parameterized point of view
• Title not available (Why is that?)
• A \(2^{|E|/4}\)-time algorithm for MAX-CUT
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• On exact algorithms for the permutation CSP
• Enumerating models of DNF faster: breaking the dependency on the formula size
• Tight conditional lower bounds for longest common increasing subsequence
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Tight conditional lower bounds for longest common increasing subsequence
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• New upper bounds for the problem of maximal satisfiability
• Quantum algorithm design: techniques and applications
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Title not available (Why is that?)
• On the hardness of approximate and exact (bichromatic) maximum inner product
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Tighter connections between Formula-SAT and shaving logs
• Separating OR, SUM, and XOR circuits
• A modeling and computational study of the frustration index in signed networks
• On the Complexity of String Matching for Graphs
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• \(k\)-approximate quasiperiodicity under Hamming and edit distance
• Exact algorithms for exact satisfiability and number of perfect matchings
• New exact algorithms for the 2-constraint satisfaction problem
• An exact algorithm for MAX-CUT in sparse graphs
• A story of diameter, radius, and (almost) Helly property
• Scheduling lower bounds via AND subset sum
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Local maxima and improved exact algorithm for MAX-2-SAT
• Optimal 2-constraint satisfaction via sum-product algorithms
• New Plain-Exponential Time Classes for Graph Homomorphism
• On two techniques of combining branching and treewidth
• If the current clique algorithms are optimal, so is Valiant's parser
• Orthogonal vectors indexing
• Automata, Languages and Programming
• Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
• Algorithms and complexity on indexing founder graphs
• Computing branchwidth via efficient triangulations and blocks
• The relative exponential time complexity of approximate counting satisfying assignments
• Longest common substring with approximately \(k\) mismatches
• Into the square: on the complexity of some quadratic-time solvable problems
• Lengths of words accepted by nondeterministic finite automata
• Locality-Sensitive Hashing Without False Negatives for $$l_p$$
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Title not available (Why is that?)
• A polyhedral perspective on tropical convolutions
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• A note on the complexity of computing the number of reachable vertices in a digraph
• Quantum algorithms for finding constant-sized sub-hypergraphs
• Algorithms and conditional lower bounds for planning problems
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Proofs of Work from worst-case assumptions
• Partitioning into sets of bounded cardinality
• New plain-exponential time classes for graph homomorphism
• A new upper bound for \(( n , 3)\)-MAX-SAT
• Fine-Grained Complexity Theory (Tutorial)
• Exact algorithms for counting 3-colorings of graphs
• Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
• On the complexity of closest pair via polar-pair of point-sets
• On the complexity of closest pair via polar-pair of point-sets
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• Counting solutions to polynomial systems via reductions
• A note on hardness of diameter approximation
• Title not available (Why is that?)
• Exact algorithms for problems related to the densest \(k\)-set problem
• The complexity of binary matrix completion under diameter constraints
• Solving string problems on graphs using the labeled direct product
• Exact and approximation algorithms for the maximum constraint satisfaction problem over the point algebra
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• The fine-grained complexity of multi-dimensional ordering properties
• Improved exact algorithms for mildly sparse instances of MAX SAT
• The Time Complexity of Constraint Satisfaction
• Fine-Grained Complexity of Regular Path Queries
• Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• Hierarchical categories in colored searching
• Title not available (Why is that?)
• An experimental evaluation of semidefinite programming and spectral algorithms for max cut
• Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
• Leanness computation: small values and special graph classes
• Tensor network complexity of multilinear maps
• Computing and listing avoidable vertices and paths
• The diameter of AT‐free graphs
• Computing generalized convolutions faster than brute force
• Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• On approximate near-neighbors search under the (continuous) Fréchet distance in higher dimensions
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Balancing graph Voronoi diagrams with one more vertex
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• The relative exponential time complexity of approximate counting satisfying assignments
• Title not available (Why is that?)
• Quantum complexity for vector domination problem
• Towards permissionless consensus in the standard model via fine-grained complexity
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• On the equivalence among problems of bounded width

Uses Software

• MAX-2-SAT

This page was built for publication: A new algorithm for optimal 2-constraint satisfaction and its implications

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