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 条

[41] BANG-BANG AND MULTIPLE VALUED OPTIMAL SOLUTIONS OF CONTROL PROBLEMS RELATED TO QUASI-LINEAR ELLIPTIC EQUATIONS
Emamizadeh, Behrouz
Liu, Yichen
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2020, 58 (02) : 1103 - 1117
[42] An Efficient Primal-Dual Interior Point Method for Linear Programming Problems Based on a New Kernel Function with a Trigonometric Barrier Term
Bouafia, Mousaab
Benterki, Djamel
Yassine, Adnan
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2016, 170 (02) : 528 - 545
[43] Sprint and jump performances in highly trained young soccer players of different chronological age: Effects of linear VS. CHANGE-OF-DIRECTION sprint training
Pavillon, Thomas
Tourny, Claire
Ben Aabderrahman, Abderraouf
Salhi, Iyed
Zouita, Sghaeir
Rouissi, Mehdi
Hackney, Anthony C.
Granacher, Urs
Zouhal, Hassane
JOURNAL OF EXERCISE SCIENCE & FITNESS, 2021, 19 (02) : 81 - 90
[44] Effects of unilateral vs. bilateral resistance training interventions on measures of strength, jump, linear and change of direction speed: a systematic review and meta-analysis
Liao, Kai-Fang
Nassis, George
Bishop, Chris
Yang, Wei
Bian, Chao
Li, Yong-Ming
BIOLOGY OF SPORT, 2022, 39 (03) : 485 - 497
[45] Effects of Strength vs. Plyometric Training Programs on Vertical Jumping, Linear Sprint and Change of Direction Speed Performance in Female Soccer Players: A Systematic Review and Meta-Analysis
Pardos-Mainer, Elena
Lozano, Demetrio
Torrontegui-Duarte, Marcelino
Carton-Llorente, Antonio
Roso-Moliner, Alberto
INTERNATIONAL JOURNAL OF ENVIRONMENTAL RESEARCH AND PUBLIC HEALTH, 2021, 18 (02) : 1 - 20
[46] Effects of velocity based training vs. traditional 1RM percentage-based training on improving strength, jump, linear sprint and change of direction speed performance: A Systematic review with meta-analysis
Liao, Kai-Fang
Wang, Xin-Xin
Han, Meng-Yuan
Li, Lin-Long
Nassis, George P.
Li, Yong-Ming
PLOS ONE, 2021, 16 (11):

← 1 2 3 4 5 →