A new algorithm for optimal 2-constraint satisfaction and its implications
From MaRDI portal
Publication:2581276
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.
Cites work
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- A \(2^{|E|/4}\)-time algorithm for MAX-CUT
- A simplified NP-complete MAXSAT problem
- Algorithms for maximum independent sets
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- An improved exponential-time algorithm for k -SAT
- Color-coding
- Computing Partitions with Applications to the Knapsack Problem
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- 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
- Finding a Minimum Circuit in a Graph
- scientific article; zbMATH DE number 1629855 (Why is no real title available?)
- scientific article; zbMATH DE number 2086240 (Why is no real title available?)
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 1354135 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- scientific article; zbMATH DE number 1522934 (Why is no real title available?)
- scientific article; zbMATH DE number 2086385 (Why is no real title available?)
- scientific article; zbMATH DE number 2086643 (Why is no real title available?)
- Matrix multiplication via arithmetic progressions
- MAX SAT approximation beyond the limits of polynomial-time approximation
- New Upper Bounds for Maximum Satisfiability
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Partial-Match Retrieval Algorithms
- Worst-case study of local search for MAX-\(k\)-SAT.
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
Cited in
(only showing first 100 items - show all)- On two techniques of combining branching and treewidth
- Proofs of Work from worst-case assumptions
- A note on hardness of diameter approximation
- Quantum algorithm design: techniques and applications
- A new upper bound for \(( n , 3)\)-MAX-SAT
- Enumerating models of DNF faster: breaking the dependency on the formula size
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Exact algorithms for counting 3-colorings of graphs
- Solving string problems on graphs using the labeled direct product
- The fine-grained complexity of multi-dimensional ordering properties
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- k-approximate quasiperiodicity under Hamming and edit distance
- Scheduling lower bounds via AND subset sum
- Lengths of words accepted by nondeterministic finite automata
- 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
- Algorithms and conditional lower bounds for planning problems
- Tight conditional lower bounds for longest common increasing subsequence
- Improved exact algorithms for mildly sparse instances of MAX SAT
- Longest common substring with approximately \(k\) mismatches
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- New exact algorithms for the 2-constraint satisfaction problem
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- Exact algorithms for problems related to the densest \(k\)-set problem
- An exact algorithm for MAX-CUT in sparse graphs
- A note on the complexity of computing the number of reachable vertices in a digraph
- The complexity of binary matrix completion under diameter constraints
- Separating OR, SUM, and XOR circuits
- Locality-Sensitive Hashing Without False Negatives for l_p
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- The relative exponential time complexity of approximate counting satisfying assignments
- Exact and approximation algorithms for the maximum constraint satisfaction problem over the point algebra
- The relative exponential time complexity of approximate counting satisfying assignments
- On the complexity of closest pair via polar-pair of point-sets
- Is constraint satisfaction over two variables always easy?
- New upper bounds for the problem of maximal satisfiability
- New Plain-Exponential Time Classes for Graph Homomorphism
- Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies
- On the equivalence among problems of bounded width
- Improved algorithms for sparse MAX-SAT and MAX-k-CSP
- The Time Complexity of Constraint Satisfaction
- A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
- Partitioning into sets of bounded cardinality
- On exact algorithms for the permutation CSP
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- scientific article; zbMATH DE number 2019637 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Local maxima and improved exact algorithm for MAX-2-SAT
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- Tighter connections between Formula-SAT and shaving logs
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Tensor network complexity of multilinear maps
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Fine-Grained Complexity Theory (Tutorial)
- Sketching, streaming, and fine-grained complexity of (weighted) LCS
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Algorithms and hardness for diameter in dynamic graphs
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- scientific article; zbMATH DE number 7561744 (Why is no real title available?)
- Tensor network complexity of multilinear maps
- Tight conditional lower bounds for longest common increasing subsequence
- On the complexity of closest pair via polar-pair of point-sets
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Orthogonal vectors indexing
- Approximate nearest neighbors search without false negatives for \(l_2\) for \(c>\sqrt{\log\log n}\)
- On the hardness of approximate and exact (bichromatic) maximum inner product
- New algorithms and lower bounds for all-pairs max-flow in undirected graphs
- Counting solutions to polynomial systems via reductions
- Automata, Languages and Programming
- scientific article; zbMATH DE number 7651160 (Why is no real title available?)
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
- scientific article; zbMATH DE number 7650079 (Why is no real title available?)
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- The diameter of AT‐free graphs
- A modeling and computational study of the frustration index in signed networks
- On approximate near-neighbors search under the (continuous) Fréchet distance in higher dimensions
- On the Complexity of String Matching for Graphs
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
- A story of diameter, radius, and (almost) Helly property
- Algorithms and complexity on indexing founder graphs
- Computing and listing avoidable vertices and paths
- Fine-Grained Complexity of Regular Path Queries
- Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions
- Quantum complexity for vector domination problem
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- A polyhedral perspective on tropical convolutions
- Computing and listing avoidable vertices and paths
- Computing generalized convolutions faster than brute force
- Balancing graph Voronoi diagrams with one more vertex
- New plain-exponential time classes for graph homomorphism
- Optimal Wheeler language recognition
- Hierarchical categories in colored searching
- An experimental evaluation of semidefinite programming and spectral algorithms for max cut
- Leanness computation: small values and special graph classes
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- Towards permissionless consensus in the standard model via fine-grained complexity
- Finer-grained reductions in fine-grained hardness of approximation
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)
