scientific article
From MaRDI portal
Publication:3549708
zbMath1231.68142MaRDI QIDQ3549708
Publication date: 5 January 2009
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (86)
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ On regularity of Max-CSPs and Min-CSPs ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ Bounds on 2-query locally testable codes with affine tests ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ Approximating CSPs Using LP Relaxation ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Gaussian bounds for noise correlation of functions ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Approximating the little Grothendieck problem over the orthogonal and unitary groups ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Unnamed Item ⋮ New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ PTAS for Sparse General-valued CSPs ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Enumerating homomorphisms ⋮ Unnamed Item ⋮ Noise correlation bounds for uniform low degree functions ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Spectral algorithms for unique games ⋮ Unnamed Item ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Approximation Algorithms for CSPs ⋮ Computational protein design as an optimization problem ⋮ Grothendieck’s Theorem, past and present ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ On the complexity of submodular function minimisation on diamonds ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ On the Approximability of Presidential Type Predicates ⋮ Random Laplacian matrices and convex relaxations ⋮ Maximally stable Gaussian partitions with discrete applications ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ Survey on nonlocal games and operator space theory ⋮ Unnamed Item ⋮ Computational topology and the Unique Games Conjecture ⋮ Unnamed Item ⋮ 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 ⋮ Unnamed Item ⋮ Dimension-free L2 maximal inequality for spherical means in the hypercube ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Convex Relaxations and Integrality Gaps ⋮ Semidefinite Programming and Constraint Programming ⋮ Lift-and-project methods for set cover and knapsack ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ 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 ⋮ Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs ⋮ Unnamed Item ⋮ Approximability Distance in the Space of H-Colourability Problems ⋮ Short Proofs Are Hard to Find ⋮ UG-hardness to NP-hardness by losing half ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Convex Algebraic Geometry of Curvature Operators ⋮ On Khot’s unique games conjecture ⋮ Properties of an Approximability-related Parameter on Circular Complete Graphs ⋮ An approximation algorithm for the maximum spectral subgraph problem ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 ⋮ Nearly Optimal NP-Hardness of Unique Coverage ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor ⋮ Unnamed Item ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Improved Dictatorship Test with Perfect Completeness ⋮ Robust dimension free isoperimetry in Gaussian space
This page was built for publication:
