Krokhin, Andrei; Opršal, Jakub; Wrochna, Marcin; Živný, Stanislav Topology and adjunction in promise constraint satisfaction. (English) Zbl 07672224 SIAM J. Comput. 52, No. 1, 38-79 (2023). MSC: 68Q17 68Q25 68R05 05C15 PDFBibTeX XMLCite \textit{A. Krokhin} et al., SIAM J. Comput. 52, No. 1, 38--79 (2023; Zbl 07672224) Full Text: DOI arXiv
Ciardo, Lorenzo; Živný, Stanislav CLAP: a new algorithm for promise CSPs. (English) Zbl 07672223 SIAM J. Comput. 52, No. 1, 1-37 (2023). MSC: 68Q25 68R01 90C05 PDFBibTeX XMLCite \textit{L. Ciardo} and \textit{S. Živný}, SIAM J. Comput. 52, No. 1, 1--37 (2023; Zbl 07672223) Full Text: DOI arXiv
Carbonnel, Clément; Romero, Miguel; Živný, Stanislav The complexity of general-valued constraint satisfaction problems seen from the other side. (English) Zbl 07470541 SIAM J. Comput. 51, No. 1, 19-69 (2022). MSC: 68Q25 68R01 03B70 90C05 PDFBibTeX XMLCite \textit{C. Carbonnel} et al., SIAM J. Comput. 51, No. 1, 19--69 (2022; Zbl 07470541) Full Text: DOI arXiv
Brakensiek, Joshua; Guruswami, Venkatesan Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy. (English) Zbl 1494.68094 SIAM J. Comput. 50, No. 6, 1663-1700 (2021). MSC: 68Q25 08A70 68R07 68W25 PDFBibTeX XMLCite \textit{J. Brakensiek} and \textit{V. Guruswami}, SIAM J. Comput. 50, No. 6, 1663--1700 (2021; Zbl 1494.68094) Full Text: DOI arXiv
Okrasa, Karolina; Rzążewski, Paweł Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs. (English) Zbl 1511.68126 SIAM J. Comput. 50, No. 2, 487-508 (2021). MSC: 68Q25 05C60 05C85 68Q27 68R10 PDFBibTeX XMLCite \textit{K. Okrasa} and \textit{P. Rzążewski}, SIAM J. Comput. 50, No. 2, 487--508 (2021; Zbl 1511.68126) Full Text: DOI arXiv
Barto, Libor; Pinsker, Michael Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems). (English) Zbl 1432.68169 SIAM J. Comput. 49, No. 2, 365-393 (2020). MSC: 68Q25 03C05 03C35 08A70 68Q17 68Q27 68R07 PDFBibTeX XMLCite \textit{L. Barto} and \textit{M. Pinsker}, SIAM J. Comput. 49, No. 2, 365--393 (2020; Zbl 1432.68169) Full Text: DOI arXiv
Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongrácz, András Constraint satisfaction problems for reducts of homogeneous graphs. (English) Zbl 1430.68121 SIAM J. Comput. 48, No. 4, 1224-1264 (2019). MSC: 68Q25 03C15 05C55 05C75 08A70 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., SIAM J. Comput. 48, No. 4, 1224--1264 (2019; Zbl 1430.68121) Full Text: DOI
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan Nonnegative weighted #CSP: an effective complexity dichotomy. (English) Zbl 1356.68094 SIAM J. Comput. 45, No. 6, 2177-2198 (2016). MSC: 68Q25 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., SIAM J. Comput. 45, No. 6, 2177--2198 (2016; Zbl 1356.68094) Full Text: DOI arXiv
Cai, Jin-Yi; Guo, Heng; Williams, Tyson A complete dichotomy rises from the capture of vanishing signatures. (English) Zbl 1350.68133 SIAM J. Comput. 45, No. 5, 1671-1728 (2016). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., SIAM J. Comput. 45, No. 5, 1671--1728 (2016; Zbl 1350.68133) Full Text: DOI arXiv
Barceló, Pablo; Romero, Miguel; Vardi, Moshe Y. Semantic acyclicity on graph databases. (English) Zbl 1407.68123 SIAM J. Comput. 45, No. 4, 1339-1376 (2016). MSC: 68P15 PDFBibTeX XMLCite \textit{P. Barceló} et al., SIAM J. Comput. 45, No. 4, 1339--1376 (2016; Zbl 1407.68123) Full Text: DOI
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark Approximately counting \(H\)-colorings is \(\#\)BIS-hard. (English) Zbl 1342.68147 SIAM J. Comput. 45, No. 3, 680-711 (2016). MSC: 68Q17 05C15 05C30 05C69 68W20 68W25 PDFBibTeX XMLCite \textit{A. Galanis} et al., SIAM J. Comput. 45, No. 3, 680--711 (2016; Zbl 1342.68147) Full Text: DOI
Fomin, Fedor V.; Todinca, Ioan; Villanger, Yngve Large induced subgraphs via triangulations and CMSO. (English) Zbl 1357.05144 SIAM J. Comput. 44, No. 1, 54-87 (2015). MSC: 05C85 05C69 68W40 68Q25 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., SIAM J. Comput. 44, No. 1, 54--87 (2015; Zbl 1357.05144) Full Text: DOI arXiv
Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting list matrix partitions of graphs. (English) Zbl 1329.68139 SIAM J. Comput. 44, No. 4, 1089-1118 (2015). MSC: 68Q25 05C30 05C50 68Q17 PDFBibTeX XMLCite \textit{A. Göbel} et al., SIAM J. Comput. 44, No. 4, 1089--1118 (2015; Zbl 1329.68139) Full Text: DOI arXiv
Kolmogorov, Vladimir; Thapper, Johan; Živný, Stanislav The power of linear programming for general-valued CSPs. (English) Zbl 1456.68059 SIAM J. Comput. 44, No. 1, 1-36 (2015). MSC: 68Q25 68Q17 68R07 90C05 90C27 PDFBibTeX XMLCite \textit{V. Kolmogorov} et al., SIAM J. Comput. 44, No. 1, 1--36 (2015; Zbl 1456.68059) Full Text: DOI arXiv