{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T07:59:42Z","timestamp":1781251182849,"version":"3.54.1"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100009193","name":"Marsden Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009193","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2026,6,30]]},"DOI":"10.1137\/25m1767200","type":"journal-article","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T07:21:11Z","timestamp":1781248871000},"page":"905-918","source":"Crossref","is-referenced-by-count":0,"title":["Refuting Perfect Matchings in Spectral Expanders Is Hard"],"prefix":"10.1137","volume":"40","author":[{"given":"Ari","family":"Biswas","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, CV4 7AL, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajko","family":"Nenadov","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Canterbury, Christchurch, 8140 New Zealand."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,6,12]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"J. Abascal, V. Guruswami, and P. K. Kothari, Strongly refuting all semi-random Boolean CSPs, in Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Alexandria, VA, virtual, SODA \u201921, Society for Industrial and Applied Mathematics (SIAM), Association for Computing Machinery (ACM), Philadelphia, New York, 2021, pp. 454\u2013472.","DOI":"10.1137\/1.9781611976465.28"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"M. Alekhnovich and A. Razborov,\n                      Lower bounds for polynomial calculus:\u00a0Non-binomial case\n                      , in Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001),\u00a0IEEE Computer Society, Los Alamitos, CA,\u00a02001, pp. 190\u2013199.","DOI":"10.1109\/SFCS.2001.959893"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"ref4","unstructured":"A. Atserias and T. Hakoniemi, Size-degree trade-offs for sums-of-squares and positivstellensatz proofs, in Proceedings of the 34th Computational Complexity Conference, CCC \u201919, LIPIcs.\u00a0Leibniz Int.\u00a0Proc.\u00a0Inform., 137,\u00a0Schloss Dagstuhl.\u00a0Leibniz-Zent.\u00a0Inform., Wadern, 2020."},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"P. Austrin and K. Risse, Perfect matching in random graphs is as hard as tseitin, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2022.","DOI":"10.1137\/1.9781611977073.43"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Impagliazzo, J. Kraj\u010d\u00ed\u010dek, T. Pitassi, P. Pudl\u00e1k, and A. Woods, Exponential lower bounds for the pigeonhole principle, in Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC \u201992, Association for Computing Machinery, New York, 1992, pp. 200\u2013220.","DOI":"10.1145\/129712.129733"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"S. Buss, D. Grigoriev, R. Impagliazzo, and T. Pitassi, Linear gaps between degrees for the polynomial calculus modulo distinct primes, in Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC \u201999, Association for Computing Machinery, New York, 1999, pp. 547\u2013556.","DOI":"10.1145\/301250.301399"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA200990"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"J. Conneryd, S. F. De Rezende, J. Nordstr\u00f6m, S. Pang, and K. Risse, Graph colouring is hard on average for polynomial calculus and nullstellensatz, in Proceedings of the IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA,\u00a02023, pp. 1\u201311.","DOI":"10.1109\/FOCS57990.2023.00007"},{"key":"ref10","unstructured":"S. A. Cook and R. A. Reckhow, The relative efficiency of propositional proof systems, 1st ed. Association for Computing Machinery, New York, 2023, pp. 173\u2013192."},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"S. F. De Rezende, A. Potechin, and K. Risse, Clique is hard on average for unary sherali-adams, in Proceedings of the IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, pp. 12\u201325.","DOI":"10.1109\/FOCS57990.2023.00008"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8660"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"Y. Filmus, M. Lauria, M. Mik\u0161a, J. Nordstr\u00f6m, and M. Vinyals, Towards an understanding of polynomial calculus:\u00a0New separations and lower bounds (extended abstract), in Automata, Languages, and Programming, Proceedings of the 40th International Colloquium, ICALP 2013, Riga, Latvia, 2013, Proceedings, Part I, Springer, Berlin, 2013, pp. 437\u2013448.","DOI":"10.1007\/978-3-642-39206-1_37"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1561\/0400000086"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2022.103166"},{"key":"ref16","unstructured":"L. Glinskih and D. Itsykson, Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs, in Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, Aalborg, Denmark, Schloss Dagstuhl \u2013 Leibniz Zentrum f\u00fcr Informatik, Wadern, 2017, 12."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050024"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-021-00213-2"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"J. Kleinberg and R. Rubinfeld, Short paths in expander graphs, in Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS \u201996, IEEE Computer Society, Los Alamitos, CA,\u00a01996, pp. 86\u201395.","DOI":"10.1109\/SFCS.1996.548467"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"P. K. Kothari, R. Mori, R. O\u2019Donnell, and D. Witmer, Sum of squares lower bounds for refuting any CSP, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Association for Computing Machinery, New York, 2017, pp. 132\u2013145.","DOI":"10.1145\/3055399.3055485"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnz086"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"A. Maciel, T. Pitassi, and A. R. Woods, A new proof of the weak pigeonhole principle, in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC \u201900, Association for Computing Machinery, New York, 2000, pp. 368\u2013377.","DOI":"10.1145\/335305.335348"},{"key":"ref24","volume-title":"Probability and Computing:\u00a0Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher M.","year":"2017"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-023-00033-8"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"T. Pitassi, B. Rossman, R. A. Servedio, and L.Y. Tan, Poly-logarithmic Frege depth lower bounds via an expander switching lemma, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201916, Association for Computing Machinery, New York, 2016, pp. 644\u2013657.","DOI":"10.1145\/2897518.2897637"},{"key":"ref27","unstructured":"A. Potechin, Sum of squares bounds for the ordering principle, in Proceedings of the 35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 169, S. Saraf, ed. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2020, 38."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972640"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"R. Raz, Elusive functions and lower bounds for arithmetic circuits, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC \u201908, Association for Computing Machinery, New York, 2008, pp. 711\u2013720.","DOI":"10.1145\/1374376.1374479"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46011-X_8"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00453-X"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"G. Schoenebeck, Linear level lasserre lower bounds for certain k-csps, in Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201908, IEEE Computer Society, 2008, pp. 593\u2013602.","DOI":"10.1109\/FOCS.2008.74"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOP1263"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1952-028-2"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T07:21:33Z","timestamp":1781248893000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1767200"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,12]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/25M1767200"],"URL":"https:\/\/doi.org\/10.1137\/25m1767200","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,12]]}}}