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