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
- 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?)
- 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
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Matrix multiplication via arithmetic progressions
- 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)- Solving string problems on graphs using the labeled direct product
- Exact and approximation algorithms for the maximum constraint satisfaction problem over the point algebra
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- The fine-grained complexity of multi-dimensional ordering properties
- Optimal Wheeler language recognition
- Improved exact algorithms for mildly sparse instances of MAX SAT
- scientific article; zbMATH DE number 2019637 (Why is no real title available?)
- The Time Complexity of Constraint Satisfaction
- On exact algorithms for the permutation CSP
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
- Enumerating models of DNF faster: breaking the dependency on the formula size
- 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
- Tight conditional lower bounds for longest common increasing subsequence
- Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Fine-Grained Complexity of Regular Path Queries
- 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
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- Separating OR, SUM, and XOR circuits
- scientific article; zbMATH DE number 7563818 (Why is no real title available?)
- 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
- Exact algorithms for exact satisfiability and number of perfect matchings
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- \(k\)-approximate quasiperiodicity under Hamming and edit distance
- Hierarchical categories in colored searching
- A modeling and computational study of the frustration index in signed networks
- On the Complexity of String Matching for Graphs
- New exact algorithms for the 2-constraint satisfaction problem
- scientific article; zbMATH DE number 7650079 (Why is no real title available?)
- An exact algorithm for MAX-CUT in sparse graphs
- Scheduling lower bounds via AND subset sum
- An experimental evaluation of semidefinite programming and spectral algorithms for max cut
- Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions
- A story of diameter, radius, and (almost) Helly property
- Optimal 2-constraint satisfaction via sum-product algorithms
- Local maxima and improved exact algorithm for MAX-2-SAT
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- New Plain-Exponential Time Classes for Graph Homomorphism
- scientific article; zbMATH DE number 7561345 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 7561744 (Why is no real title available?)
- Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
- Computing branchwidth via efficient triangulations and blocks
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- Algorithms and complexity on indexing founder graphs
- The relative exponential time complexity of approximate counting satisfying assignments
- Leanness computation: small values and special graph classes
- Longest common substring with approximately \(k\) mismatches
- Into the square: on the complexity of some quadratic-time solvable problems
- Tensor network complexity of multilinear maps
- Lengths of words accepted by nondeterministic finite automata
- Computing and listing avoidable vertices and paths
- The diameter of AT‐free graphs
- Computing generalized convolutions faster than brute force
- Locality-Sensitive Hashing Without False Negatives for $$l_p$$
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- scientific article; zbMATH DE number 7561506 (Why is no real title available?)
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
- On approximate near-neighbors search under the (continuous) Fréchet distance in higher dimensions
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- A polyhedral perspective on tropical convolutions
- A note on the complexity of computing the number of reachable vertices in a digraph
- Quantum algorithms for finding constant-sized sub-hypergraphs
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
- Algorithms and conditional lower bounds for planning problems
- Balancing graph Voronoi diagrams with one more vertex
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Proofs of Work from worst-case assumptions
- The relative exponential time complexity of approximate counting satisfying assignments
- New plain-exponential time classes for graph homomorphism
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Partitioning into sets of bounded cardinality
- New algorithms and lower bounds for all-pairs max-flow in undirected graphs
- Quantum complexity for vector domination problem
- Towards permissionless consensus in the standard model via fine-grained complexity
- A new upper bound for \(( n , 3)\)-MAX-SAT
- Exact algorithms for counting 3-colorings of graphs
- Fine-Grained Complexity Theory (Tutorial)
- On the equivalence among problems of bounded width
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Is constraint satisfaction over two variables always easy?
- Finer-grained reductions in fine-grained hardness of approximation
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Approximate nearest neighbors search without false negatives for \(l_2\) for \(c>\sqrt{\log\log n}\)
- Computing and listing avoidable vertices and paths
- Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
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)
