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
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, 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
