scientific article; zbMATH DE number 5485536
From MaRDI portal
Publication:3549708
Cited in
(88)- On the complexity of random satisfiability problems with planted solutions
- Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs
- Notes on computational-to-statistical gaps: predictions using statistical physics
- Lift \& project systems performing on the partial-vertex-cover polytope
- Computational topology and the unique games conjecture
- Approximating unique games using low diameter graph decomposition
- On regularity of Max-CSPs and Min-CSPs
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Grothendieck’s Theorem, past and present
- Bi-covering: covering edges with two small subsets of vertices
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- Enumerating homomorphisms
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- The power of linear programming for general-valued CSPs
- Bounds on 2-query locally testable codes with affine tests
- On Khot’s unique games conjecture
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- The complexity of conservative valued CSPs
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- Random Laplacian matrices and convex relaxations
- Lower bounds of functions on finite abelian groups
- From weak to strong linear programming gaps for all constraint satisfaction problems
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Constant-query testability of assignments to constraint satisfaction problems
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Noise correlation bounds for uniform low degree functions
- The power of Sherali-Adams relaxations for general-valued CSPs
- Noise stability of functions with low influences: invariance and optimality
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- scientific article; zbMATH DE number 7053310 (Why is no real title available?)
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Gaussian bounds for noise correlation of resilient functions
- On the Approximability of Presidential Type Predicates
- scientific article; zbMATH DE number 7650095 (Why is no real title available?)
- CLAP: A New Algorithm for Promise CSPs
- An approximation algorithm for the maximum spectral subgraph problem
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- On computational capabilities of Ising machines based on nonlinear oscillators
- Robust dimension free isoperimetry in Gaussian space
- Lower bounds for the graph homomorphism problem
- Approximation Algorithms for CSPs
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- The complexity of general-valued CSPs
- Sherali-Adams relaxations for valued CSPs
- Convex Algebraic Geometry of Curvature Operators
- PTAS for Sparse General-valued CSPs
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Nearly optimal NP-hardness of unique coverage
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- Mathematics of computation through the lens of linear equations and lattices
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Lift-and-project methods for set cover and knapsack
- Approximating the little Grothendieck problem over the orthogonal and unitary groups
- Short Proofs Are Hard to Find
- Half-integrality, LP-branching, and FPT algorithms
- Semidefinite programming and constraint programming
- Approximating CSPs using LP relaxation
- Grothendieck constant is norm of Strassen matrix multiplication tensor
- Gaussian bounds for noise correlation of functions
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
- Spectral algorithms for unique games
- Hard constraint satisfaction problems have hard gaps at location 1
- Maximally stable Gaussian partitions with discrete applications
- Survey on nonlocal games and operator space theory
- Convex relaxations and integrality gaps
- On approximability of satisfiable k-CSPs. II
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- SDPs and robust satisfiability of promise CSP
- The power of unentangled quantum proofs with non-negative amplitudes
- An improved dictatorship test with perfect completeness
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Learnability of solutions to conjunctive queries
- Approximability Distance in the Space of H-Colourability Problems
- Dimension-free L2 maximal inequality for spherical means in the hypercube
- Simultaneous approximation of constraint satisfaction problems
- Accelerated first-order methods for a class of semidefinite programs
- Fitting metrics and ultrametrics with minimum disagreements
- Computational protein design as an optimization problem
- Unique games on the hypercube
- On the complexity of submodular function minimisation on diamonds
- Robustly solvable constraint satisfaction problems
- scientific article; zbMATH DE number 6474898 (Why is no real title available?)
- Robust algorithms with polynomial loss for near-unanimity CSPs
- UG-hardness to NP-hardness by losing half
- Properties of an approximability-related parameter on circular complete graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549708)
