Semidefinite Programming and Linear Equations vs. Homomorphism Problems

被引：0
作者：
Ciardo, Lorenzo [1 ]
Zivny, Stanislav [1 ]
机构：
[1] Univ Oxford, Oxford, England
来源：
PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024 | 2024年
关键词：
approximate graph colouring; approximate graph homomorphism; semidefinite programming relaxations; affine integer programming relaxations; Diophantine equations; promise constraint satisfaction; CONSTRAINT SATISFACTION; ASSOCIATION SCHEMES; ALGEBRAIC STRUCTURE; CHROMATIC NUMBER; SHERALI-ADAMS; COMPLEXITY; HARDNESS; POWER; RELAXATIONS; SYMMETRY;
D O I：
10.1145/3618260.3649635
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We introduce a relaxation for homomorphism problems that combines semidefinite programming with linear Diophantine equations, and propose a framework for the analysis of its power based on the spectral theory of association schemes. We use this framework to establish an unconditional lower bound against the semidefinite programming + linear equations model, by showing that the relaxation does not solve the approximate graph homomorphism problem and thus, in particular, the approximate graph colouring problem.
引用
收藏
页码：1935 / 1943
页数：9
相关论文
共 46 条
  • [21] Linear decomposition approach for a class of nonconvex programming problems
    Shen, Peiping
    Wang, Chunfeng
    JOURNAL OF INEQUALITIES AND APPLICATIONS, 2017,
  • [22] Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
    V. Jeyakumar
    S. Kim
    G. M. Lee
    G. Li
    Journal of Global Optimization, 2016, 65 : 175 - 190
  • [23] CISC vs. RISC hardware and programming complexity measures of addressing modes
    El-Aawar, Haissam
    Perspective Technologies and Methods in MEMS Design, 2006, : 43 - 48
  • [24] Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
    Jeyakumar, V.
    Kim, S.
    Lee, G. M.
    Li, G.
    JOURNAL OF GLOBAL OPTIMIZATION, 2016, 65 (02) : 175 - 190
  • [25] Robust semidefinite programming problems with general nonlinear parameter dependence: Approaches using the DC-representations
    Oishi, Yasuaki
    Alamo, Teodoro
    AUTOMATICA, 2012, 48 (11) : 2937 - 2944
  • [26] Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems
    Monteiro, Renato D. C.
    Ortiz, Camilo
    Svaiter, Benar F.
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2014, 57 (01) : 45 - 69
  • [27] Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems
    Renato D. C. Monteiro
    Camilo Ortiz
    Benar F. Svaiter
    Computational Optimization and Applications, 2014, 57 : 45 - 69
  • [28] ESTIMATING BOUNDS FOR QUADRATIC ASSIGNMENT PROBLEMS ASSOCIATED WITH HAMMING AND MANHATTAN DISTANCE MATRICES BASED ON SEMIDEFINITE PROGRAMMING
    Mittelmann, Hans
    Peng, Jiming
    SIAM JOURNAL ON OPTIMIZATION, 2010, 20 (06) : 3408 - 3426
  • [29] Two Variable vs. Linear Temporal Logic in Model Checking and Games
    Benedikt, Michael
    Lenhardt, Rastislav
    Worrell, James
    CONCUR 2011: CONCURRENCY THEORY, 2011, 6901 : 497 - 511
  • [30] ABS algorithms for diophantine linear equations and integer LP problems
    Zou M.-F.
    Xia Z.-Q.
    Journal of Applied Mathematics and Computing, 2005, 17 (1-2) : 93 - 107
12345