scientific article; zbMATH DE number 5485536
From MaRDI portal
Publication:3549708
zbMATH Open1231.68142MaRDI QIDQ3549708FDOQ3549708
Authors: Prasad Raghavendra 
Publication date: 5 January 2009
Title of this publication is not available (Why is that?)
Cited In (88)
- Computational topology and the unique games conjecture
- Approximating unique games using low diameter graph decomposition
- Title not available (Why is that?)
- Lower bounds of functions on finite abelian groups
- From weak to strong linear programming gaps for all constraint satisfaction problems
- Constant-query testability of assignments to constraint satisfaction problems
- On the Approximability of Presidential Type Predicates
- CLAP: A New Algorithm for Promise CSPs
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- PTAS for Sparse General-valued CSPs
- Nearly optimal NP-hardness of unique coverage
- Mathematics of computation through the lens of linear equations and lattices
- 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
- Dimension-free L2 maximal inequality for spherical means in the hypercube
- Accelerated first-order methods for a class of semidefinite programs
- Fitting metrics and ultrametrics with minimum disagreements
- Robust algorithms with polynomial loss for near-unanimity CSPs
- 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
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Grothendieck’s Theorem, past and present
- On regularity of Max-CSPs and Min-CSPs
- 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
- 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
- Enumerating homomorphisms
- On Khot’s unique games conjecture
- Bounds on 2-query locally testable codes with affine tests
- Title not available (Why is that?)
- The complexity of conservative valued CSPs
- Random Laplacian matrices and convex relaxations
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- 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
- Title not available (Why is that?)
- Noise stability of functions with low influences: invariance and optimality
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- Title not available (Why is that?)
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Gaussian bounds for noise correlation of resilient functions
- An approximation algorithm for the maximum spectral subgraph problem
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Approximation Algorithms for CSPs
- The complexity of general-valued CSPs
- Lower bounds for the graph homomorphism problem
- Robust dimension free isoperimetry in Gaussian space
- On computational capabilities of Ising machines based on nonlinear oscillators
- Convex Algebraic Geometry of Curvature Operators
- Sherali-Adams relaxations for valued CSPs
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Short Proofs Are Hard to Find
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Lift-and-project methods for set cover and knapsack
- Half-integrality, LP-branching, and FPT algorithms
- Approximating the little Grothendieck problem over the orthogonal and unitary groups
- Approximating CSPs using LP relaxation
- Semidefinite programming and constraint programming
- 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\)
- Survey on nonlocal games and operator space theory
- Spectral algorithms for unique games
- Maximally stable Gaussian partitions with discrete applications
- Hard constraint satisfaction problems have hard gaps at location 1
- Convex relaxations and integrality gaps
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Learnability of solutions to conjunctive queries
- Approximability Distance in the Space of H-Colourability Problems
- Simultaneous approximation of constraint satisfaction problems
- Computational protein design as an optimization problem
- Unique games on the hypercube
- UG-hardness to NP-hardness by losing half
- Robustly solvable constraint satisfaction problems
- On the complexity of submodular function minimisation on diamonds
- Title not available (Why is that?)
- 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)
