Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel Inapproximability of the independent set polynomial in the complex plane. (English) Zbl 1476.68193 SIAM J. Comput. 49, No. 5, STOC18-395-STOC18-448 (2020). MSC: 68R10 05C31 05C69 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{I. Bezáková} et al., SIAM J. Comput. 49, No. 5, STOC18--395-STOC18--448 (2020; Zbl 1476.68193) Full Text: DOI
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel Inapproximability of the independent set polynomial in the complex plane. (English) Zbl 1427.68229 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1234-1240 (2018). MSC: 68R10 05C31 05C69 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{I. Bezáková} et al., in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 1234--1240 (2018; Zbl 1427.68229) Full Text: DOI arXiv
Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. (English) Zbl 1338.68086 J. Comput. Syst. Sci. 82, No. 5, 690-711 (2016). MSC: 68Q17 05C69 05C85 68Q25 68W25 82C20 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., J. Comput. Syst. Sci. 82, No. 5, 690--711 (2016; Zbl 1338.68086) Full Text: DOI arXiv
Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. (English) Zbl 1359.68119 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 17th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2014) and the 18th international workshop on randomization and computation (RANDOM 2014), Universitat Politècnica de Catalunya, Barcelona, Spain, September 4–6, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-74-3). LIPIcs – Leibniz International Proceedings in Informatics 28, 582-595 (2014). MSC: 68Q25 05C30 05C69 68Q17 82B26 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., LIPIcs -- Leibniz Int. Proc. Inform. 28, 582--595 (2014; Zbl 1359.68119) Full Text: DOI