Montanari, Andrea; Zhong, Yiqiao; Zhou, Kangjie Tractability from overparametrization: the example of the negative perceptron. (English) Zbl 07819897 Probab. Theory Relat. Fields 188, No. 3-4, 805-910 (2024). MSC: 90C05 68T07 82B44 PDFBibTeX XMLCite \textit{A. Montanari} et al., Probab. Theory Relat. Fields 188, No. 3--4, 805--910 (2024; Zbl 07819897) Full Text: DOI arXiv
Nam, Danny; Sly, Allan; Sohn, Youngtak One-step replica symmetry breaking of random regular NAE-SAT. II. (English) Zbl 07811482 Commun. Math. Phys. 405, No. 3, Paper No. 61, 63 p. (2024). MSC: 68Qxx 68R10 05D40 05C15 82Bxx PDFBibTeX XMLCite \textit{D. Nam} et al., Commun. Math. Phys. 405, No. 3, Paper No. 61, 63 p. (2024; Zbl 07811482) Full Text: DOI arXiv OA License
Tyapkin, D. N.; Shabanov, D. A. On the structure of the set of panchromatic colorings of a random hypergraph. (English. Russian original) Zbl 07786644 Dokl. Math. 108, No. 1, 286-290 (2023); translation from Dokl. Ross. Akad. Nauk, Mat. Inform. Protsessy Upr. 512, 52-57 (2023). MSC: 05C15 05C65 05C80 05D40 PDFBibTeX XMLCite \textit{D. N. Tyapkin} and \textit{D. A. Shabanov}, Dokl. Math. 108, No. 1, 286--290 (2023; Zbl 07786644); translation from Dokl. Ross. Akad. Nauk, Mat. Inform. Protsessy Upr. 512, 52--57 (2023) Full Text: DOI
Davenport, James H. Digital collections of examples in mathematical sciences. (English) Zbl 07763413 Hujdurović, Ademir (ed.) et al., European congress of mathematics. Proceedings of the 8th congress, 8ECM, Portorož, Slovenia, June 20–26, 2021. Berlin: European Mathematical Society (EMS). 719-731 (2023). MSC: 68-02 PDFBibTeX XMLCite \textit{J. H. Davenport}, in: European congress of mathematics. Proceedings of the 8th congress, 8ECM, Portorož, Slovenia, June 20--26, 2021. Berlin: European Mathematical Society (EMS). 719--731 (2023; Zbl 07763413) Full Text: DOI arXiv
Altschuler, Dylan J.; Niles-Weed, Jonathan The discrepancy of random rectangular matrices. (English) Zbl 07749528 Random Struct. Algorithms 60, No. 4, 551-593 (2022). MSC: 65-XX 15-XX PDFBibTeX XMLCite \textit{D. J. Altschuler} and \textit{J. Niles-Weed}, Random Struct. Algorithms 60, No. 4, 551--593 (2022; Zbl 07749528) Full Text: DOI arXiv
Coja-Oghlan, Amin; Müller, Noela; Ravelomanana, Jean B. Belief propagation on the random \(k\)-SAT model. (English) Zbl 1498.60044 Ann. Appl. Probab. 32, No. 5, 3718-3796 (2022). MSC: 60C05 68Q87 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Ann. Appl. Probab. 32, No. 5, 3718--3796 (2022; Zbl 1498.60044) Full Text: DOI arXiv
Antonopoulos, Antonis; Bakali, Eleni; Chalki, Aggeliki; Pagourtzis, Aris; Pantavos, Petros; Zachos, Stathis Completeness, approximability and exponential time results for counting problems with easy decision version. (English) Zbl 07533864 Theor. Comput. Sci. 915, 55-73 (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Antonopoulos} et al., Theor. Comput. Sci. 915, 55--73 (2022; Zbl 07533864) Full Text: DOI
Airey, Dylan; Bowen, Lewis; Lin, Yuqing Frank A topological dynamical system with two different positive sofic entropies. (English) Zbl 1497.37013 Trans. Am. Math. Soc., Ser. B 9, 35-98 (2022). Reviewer: Hasan Akin (Trieste) MSC: 37B05 37B40 37B10 37B51 37E25 05C65 PDFBibTeX XMLCite \textit{D. Airey} et al., Trans. Am. Math. Soc., Ser. B 9, 35--98 (2022; Zbl 1497.37013) Full Text: DOI arXiv
Silwal, Sandeep A concentration inequality for the facility location problem. (English) Zbl 1525.90259 Oper. Res. Lett. 50, No. 2, 213-217 (2022). MSC: 90B80 90C15 PDFBibTeX XMLCite \textit{S. Silwal}, Oper. Res. Lett. 50, No. 2, 213--217 (2022; Zbl 1525.90259) Full Text: DOI arXiv
Sly, Allan; Sun, Nike; Zhang, Yumeng The number of solutions for random regular NAE-SAT. (English) Zbl 1490.60282 Probab. Theory Relat. Fields 182, No. 1-2, 1-109 (2022). MSC: 60K35 82B44 PDFBibTeX XMLCite \textit{A. Sly} et al., Probab. Theory Relat. Fields 182, No. 1--2, 1--109 (2022; Zbl 1490.60282) Full Text: DOI arXiv
Larsson, Joel; Markström, Klas Biased random \(k\)-SAT. (English) Zbl 1522.68377 Random Struct. Algorithms 59, No. 2, 238-266 (2021). MSC: 68R07 60C05 68Q87 PDFBibTeX XMLCite \textit{J. Larsson} and \textit{K. Markström}, Random Struct. Algorithms 59, No. 2, 238--266 (2021; Zbl 1522.68377) Full Text: DOI arXiv OA License
Achlioptas, Dimitris; Coja-Oghlan, Amin; Hahn-Klimroth, Max; Lee, Joon; Müller, Noëla; Penschuck, Manuel; Zhou, Guangyan The number of satisfying assignments of random 2-SAT formulas. (English) Zbl 1522.68375 Random Struct. Algorithms 58, No. 4, 609-647 (2021). MSC: 68R07 60F05 68Q87 PDFBibTeX XMLCite \textit{D. Achlioptas} et al., Random Struct. Algorithms 58, No. 4, 609--647 (2021; Zbl 1522.68375) Full Text: DOI OA License
Omelchenko, Oleksii; Bulatov, Andrei A. Satisfiability threshold for power law random 2-SAT in configuration model. (English) Zbl 1514.68275 Theor. Comput. Sci. 888, 70-94 (2021). MSC: 68T20 68Q87 68R07 PDFBibTeX XMLCite \textit{O. Omelchenko} and \textit{A. A. Bulatov}, Theor. Comput. Sci. 888, 70--94 (2021; Zbl 1514.68275) Full Text: DOI arXiv
Kravtsov, D. A.; Krokhmal, N. E.; Shabanov, D. A. Panchromatic colorings of random hypergraphs. (English. Russian original) Zbl 1459.05304 Discrete Math. Appl. 31, No. 1, 19-41 (2021); translation from Diskretn. Mat. 31, No. 2, 84-113 (2019). Reviewer: Yilun Shang (Newcastle) MSC: 05C80 05C65 05C15 60C05 PDFBibTeX XMLCite \textit{D. A. Kravtsov} et al., Discrete Math. Appl. 31, No. 1, 19--41 (2021; Zbl 1459.05304); translation from Diskretn. Mat. 31, No. 2, 84--113 (2019) Full Text: DOI
Coja-Oghlan, Amin; Kapetanopoulos, Tobias; Müller, Noela The replica symmetric phase of random constraint satisfaction problems. (English) Zbl 1504.68152 Comb. Probab. Comput. 29, No. 3, 346-422 (2020). MSC: 68R07 68Q87 82B26 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Comb. Probab. Comput. 29, No. 3, 346--422 (2020; Zbl 1504.68152) Full Text: DOI arXiv
Ayre, Peter; Coja-Oghlan, Amin; Gao, Pu; Müller, Noëla The satisfiability threshold for random linear equations. (English) Zbl 1463.05507 Combinatorica 40, No. 2, 179-235 (2020). Reviewer: Ko-Wei Lih (Taipei) MSC: 05C80 05C50 PDFBibTeX XMLCite \textit{P. Ayre} et al., Combinatorica 40, No. 2, 179--235 (2020; Zbl 1463.05507) Full Text: DOI arXiv
Coja-Oghlan, Amin; Gebhard, Oliver; Hahn-Klimroth, Max; Loick, Philipp Information-theoretic and algorithmic thresholds for group testing. (English) Zbl 07561536 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 43, 14 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 43, 14 p. (2019; Zbl 07561536) Full Text: DOI
Budzynski, Louise; Ricci-Tersenghi, Federico; Semerjian, Guilhem Biased landscapes for random constraint satisfaction problems. (English) Zbl 07382786 J. Stat. Mech. Theory Exp. 2019, No. 2, Article ID 023302, 44 p. (2019). MSC: 82-XX PDFBibTeX XMLCite \textit{L. Budzynski} et al., J. Stat. Mech. Theory Exp. 2019, No. 2, Article ID 023302, 44 p. (2019; Zbl 07382786) Full Text: DOI arXiv
Coja-Oghlan, Amin; Perkins, Will Spin systems on Bethe lattices. (English) Zbl 1431.82013 Commun. Math. Phys. 372, No. 2, 441-523 (2019). MSC: 82B23 81T25 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} and \textit{W. Perkins}, Commun. Math. Phys. 372, No. 2, 441--523 (2019; Zbl 1431.82013) Full Text: DOI arXiv
Kravstov, Dmitry; Krokhmal, Nikolay; Shabanov, Dmitry Panchromatic 3-colorings of random hypergraphs. (English) Zbl 1414.05119 Eur. J. Comb. 78, 28-43 (2019). MSC: 05C15 05C80 05C65 PDFBibTeX XMLCite \textit{D. Kravstov} et al., Eur. J. Comb. 78, 28--43 (2019; Zbl 1414.05119) Full Text: DOI
Semenov, A. S. Two-colorings of a random hypergraph. (English. Russian original) Zbl 1481.05053 Theory Probab. Appl. 64, No. 1, 59-77 (2019); translation from Teor. Veroyatn. Primen. 64, No. 1, 75-97 (2019). MSC: 05C15 05C65 05C80 60C05 05D40 PDFBibTeX XMLCite \textit{A. S. Semenov}, Theory Probab. Appl. 64, No. 1, 59--77 (2019; Zbl 1481.05053); translation from Teor. Veroyatn. Primen. 64, No. 1, 75--97 (2019) Full Text: DOI
Molloy, Michael The list chromatic number of graphs with small clique number. (English) Zbl 1402.05076 J. Comb. Theory, Ser. B 134, 264-284 (2019). MSC: 05C15 05C07 PDFBibTeX XMLCite \textit{M. Molloy}, J. Comb. Theory, Ser. B 134, 264--284 (2019; Zbl 1402.05076) Full Text: DOI arXiv
Kravtsov, D. A.; Krokhmal, N. E.; Shabanov, D. A. On panchromatic colourings of a random hypergraph. (English. Russian original) Zbl 1437.05076 Russ. Math. Surv. 73, No. 4, 731-733 (2018); translation from Usp. Mat. Nauk 73, No. 4, 175-176 (2018). Reviewer: Brigitte Servatius (Worcester) MSC: 05C15 05C80 05C65 PDFBibTeX XMLCite \textit{D. A. Kravtsov} et al., Russ. Math. Surv. 73, No. 4, 731--733 (2018; Zbl 1437.05076); translation from Usp. Mat. Nauk 73, No. 4, 175--176 (2018) Full Text: DOI
Coja-Oghlan, Amin Phase transitions in discrete structures. (English) Zbl 1403.82009 Mehrmann, Volker (ed.) et al., European congress of mathematics. Proceedings of the 7th ECM (7ECM) congress, Berlin, Germany, July 18–22, 2016. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-176-7/hbk; 978-3-03719-676-2/ebook). 599-618 (2018). MSC: 82B26 05C80 82B44 PDFBibTeX XMLCite \textit{A. Coja-Oghlan}, in: European congress of mathematics. Proceedings of the 7th ECM (7ECM) congress, Berlin, Germany, July 18--22, 2016. Zürich: European Mathematical Society (EMS). 599--618 (2018; Zbl 1403.82009) Full Text: DOI
Coja-Oghlan, Amin; Wormald, Nick The number of satisfying assignments of random regular \(k\)-SAT formulas. (English) Zbl 1393.60010 Comb. Probab. Comput. 27, No. 4, 496-530 (2018). MSC: 60C05 05C80 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} and \textit{N. Wormald}, Comb. Probab. Comput. 27, No. 4, 496--530 (2018; Zbl 1393.60010) Full Text: DOI arXiv
Coja-Oghlan, Amin; Krzakala, Florent; Perkins, Will; Zdeborová, Lenka Information-theoretic thresholds from the cavity method. (English) Zbl 1397.82013 Adv. Math. 333, 694-795 (2018). Reviewer: Hasan Akin (Gaziantep) MSC: 82B20 82B26 05C80 82D40 05C15 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Adv. Math. 333, 694--795 (2018; Zbl 1397.82013) Full Text: DOI arXiv
Coja-Oghlan, Amin; Efthymiou, Charilaos; Jaafari, Nor; Kang, Mihyun; Kapetanopoulos, Tobias Charting the replica symmetric phase. (English) Zbl 1395.82039 Commun. Math. Phys. 359, No. 2, 603-698 (2018). Reviewer: Hasan Akin (Gaziantep) MSC: 82B20 82B26 81R40 82B05 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Commun. Math. Phys. 359, No. 2, 603--698 (2018; Zbl 1395.82039) Full Text: DOI Link
Coja-Oghlan, Amin; Efthymiou, Charilaos; Jaafari, Nor; Kang, Mihyun; Kapetanopoulos, Tobias Charting the replica symmetric phase. (English) Zbl 1467.82011 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 40, 17 p. (2017). MSC: 82B20 82B26 81R40 82B05 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 40, 17 p. (2017; Zbl 1467.82011) Full Text: DOI arXiv
Gabrié, Marylou; Dani, Varsha; Semerjian, Guilhem; Zdeborová, Lenka Phase transitions in the \(q\)-coloring of random hypergraphs. (English) Zbl 1380.05141 J. Phys. A, Math. Theor. 50, No. 50, Article ID 505002, 44 p. (2017). MSC: 05C65 05C15 05C80 82C26 82C44 PDFBibTeX XMLCite \textit{M. Gabrié} et al., J. Phys. A, Math. Theor. 50, No. 50, Article ID 505002, 44 p. (2017; Zbl 1380.05141) Full Text: DOI arXiv
Kravtsov, Dmitry; Krokhmal, Nikolay; Shabanov, Dmitry Panchromatic 3-coloring of a random hypergraph. (English) Zbl 1378.05063 Drmota, Michael (ed.) et al., Extended abstracts of the ninth European conference on combinatorics, graph theory and applications, EuroComb 2017, Vienna, Austria, August 28 – September 1, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 61, 781-787 (2017). MSC: 05C15 05C80 05C65 PDFBibTeX XMLCite \textit{D. Kravtsov} et al., Electron. Notes Discrete Math. 61, 781--787 (2017; Zbl 1378.05063) Full Text: DOI
Shabanov, D. A. On the concentration of the chromatic number of a random hypergraph. (English. Russian original) Zbl 1373.05069 Dokl. Math. 96, No. 1, 321-325 (2017); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 475, No. 1, 24-28 (2016). MSC: 05C15 05C80 05C65 PDFBibTeX XMLCite \textit{D. A. Shabanov}, Dokl. Math. 96, No. 1, 321--325 (2017; Zbl 1373.05069); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 475, No. 1, 24--28 (2016) Full Text: DOI
Coja-Oghlan, A.; Perkins, W.; Skubch, K. Limits of discrete distributions and Gibbs measures on random graphs. (English) Zbl 1369.05183 Eur. J. Comb. 66, 37-59 (2017). MSC: 05C80 60K35 82B44 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Eur. J. Comb. 66, 37--59 (2017; Zbl 1369.05183) Full Text: DOI arXiv
Rassmann, Felicia On the number of solutions in random hypergraph 2-colouring. (English) Zbl 1369.05086 Electron. J. Comb. 24, No. 3, Research Paper P3.11, 31 p. (2017). MSC: 05C15 05C65 05C80 60C05 PDFBibTeX XMLCite \textit{F. Rassmann}, Electron. J. Comb. 24, No. 3, Research Paper P3.11, 31 p. (2017; Zbl 1369.05086) Full Text: arXiv Link
Tan, Wei En Waiter-client and client-waiter colourability and \(k\)-SAT games. (English) Zbl 1366.05072 Electron. J. Comb. 24, No. 2, Research Paper P2.46, 13 p. (2017). MSC: 05C57 91A43 91A05 91A24 05C15 PDFBibTeX XMLCite \textit{W. E. Tan}, Electron. J. Comb. 24, No. 2, Research Paper P2.46, 13 p. (2017; Zbl 1366.05072) Full Text: arXiv Link
Coja-Oghlan, A.; Haqshenas, A.; Hetterich, S. Walksat stalls well below satisfiability. (English) Zbl 1371.68109 SIAM J. Discrete Math. 31, No. 2, 1160-1173 (2017). MSC: 68Q25 68Q87 68W20 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., SIAM J. Discrete Math. 31, No. 2, 1160--1173 (2017; Zbl 1371.68109) Full Text: DOI arXiv
Gamarnik, David; Sudan, Madhu Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem. (English) Zbl 1388.60037 SIAM J. Comput. 46, No. 2, 590-619 (2017). MSC: 60C05 82B20 05C80 PDFBibTeX XMLCite \textit{D. Gamarnik} and \textit{M. Sudan}, SIAM J. Comput. 46, No. 2, 590--619 (2017; Zbl 1388.60037) Full Text: DOI
Braunstein, Alfredo; Dall’Asta, Luca; Semerjian, Guilhem; Zdeborová, Lenka The large deviations of the whitening process in random constraint satisfaction problems. (English) Zbl 1459.90135 J. Stat. Mech. Theory Exp. 2016, No. 5, Article ID 053401, 79 p. (2016). MSC: 90C15 68Q25 68W40 82D30 PDFBibTeX XMLCite \textit{A. Braunstein} et al., J. Stat. Mech. Theory Exp. 2016, No. 5, Article ID 053401, 79 p. (2016; Zbl 1459.90135) Full Text: DOI arXiv
Bapst, Victor; Coja-Oghlan, Amin Harnessing the Bethe free energy. (English) Zbl 1352.05162 Random Struct. Algorithms 49, No. 4, 694-741 (2016). MSC: 05C80 05C42 PDFBibTeX XMLCite \textit{V. Bapst} and \textit{A. Coja-Oghlan}, Random Struct. Algorithms 49, No. 4, 694--741 (2016; Zbl 1352.05162) Full Text: DOI arXiv
Genitrini, Antoine; Mailler, Cécile Generalised and quotient models for random and/or trees and application to satisfiability. (English) Zbl 1355.68199 Algorithmica 76, No. 4, 1106-1138 (2016). MSC: 68R05 05C05 05C80 06E30 68Q87 PDFBibTeX XMLCite \textit{A. Genitrini} and \textit{C. Mailler}, Algorithmica 76, No. 4, 1106--1138 (2016; Zbl 1355.68199) Full Text: DOI arXiv
Ding, Jian; Sly, Allan; Sun, Nike Satisfiability threshold for random regular nae-sat. (English) Zbl 1335.68243 Commun. Math. Phys. 341, No. 2, 435-489 (2016). MSC: 68T20 05C80 68Q25 82B05 PDFBibTeX XMLCite \textit{J. Ding} et al., Commun. Math. Phys. 341, No. 2, 435--489 (2016; Zbl 1335.68243) Full Text: DOI
Coja-Oghlan, Amin; Panagiotou, Konstantinos The asymptotic \(k\)-SAT threshold. (English) Zbl 1394.60007 Adv. Math. 288, 985-1068 (2016). Reviewer: Nikolaos Fountoulakis (Edgbaston) MSC: 60C05 05C80 68Q25 82B27 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} and \textit{K. Panagiotou}, Adv. Math. 288, 985--1068 (2016; Zbl 1394.60007) Full Text: DOI arXiv
Efthymiou, Charilaos Random instances of problems in NP – algorithms and statistical physics. (English) Zbl 1331.68103 Zaroliagis, Christos (ed.) et al., Algorithms, probability, networks, and games. Scientific papers and essays dedicated to Paul G. Spirakis on the occasion of his 60th birthday. Cham: Springer (ISBN 978-3-319-24023-7/pbk; 978-3-319-24024-4/ebook). Lecture Notes in Computer Science 9295, 196-222 (2015). MSC: 68Q25 05C80 05C85 68Q17 68Q87 68W01 PDFBibTeX XMLCite \textit{C. Efthymiou}, Lect. Notes Comput. Sci. 9295, 196--222 (2015; Zbl 1331.68103) Full Text: DOI
Perkins, Will Random \(k\)-SAT and the power of two choices. (English) Zbl 1322.05125 Random Struct. Algorithms 47, No. 1, 163-173 (2015). MSC: 05C80 68T20 60C05 PDFBibTeX XMLCite \textit{W. Perkins}, Random Struct. Algorithms 47, No. 1, 163--173 (2015; Zbl 1322.05125) Full Text: DOI arXiv
Dyer, Martin; Frieze, Alan; Greenhill, Catherine On the chromatic number of a random hypergraph. (English) Zbl 1315.05051 J. Comb. Theory, Ser. B 113, 68-122 (2015). MSC: 05C15 05C80 05C65 PDFBibTeX XMLCite \textit{M. Dyer} et al., J. Comb. Theory, Ser. B 113, 68--122 (2015; Zbl 1315.05051) Full Text: DOI arXiv
de Panafieu, Élie; Ravelomanana, Vlady Analytic description of the phase transition of inhomogeneous multigraphs. (English) Zbl 1315.05127 Eur. J. Comb. 48, 186-197 (2015). MSC: 05C80 05C15 PDFBibTeX XMLCite \textit{É. de Panafieu} and \textit{V. Ravelomanana}, Eur. J. Comb. 48, 186--197 (2015; Zbl 1315.05127) Full Text: DOI
Berthet, Quentin Optimal testing for planted satisfiability problems. (English) Zbl 1307.62015 Electron. J. Stat. 9, 298-317 (2015). MSC: 62C20 68R01 60C05 PDFBibTeX XMLCite \textit{Q. Berthet}, Electron. J. Stat. 9, No. 1, 298--317 (2015; Zbl 1307.62015) Full Text: DOI arXiv Euclid
Dell, Holger; Van Melkebeek, Dieter Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. (English) Zbl 1321.68274 J. ACM 61, No. 4, Article No. 23, 27 p. (2014). MSC: 68Q15 05C70 05C65 68Q17 68Q25 68Q45 PDFBibTeX XMLCite \textit{H. Dell} and \textit{D. Van Melkebeek}, J. ACM 61, No. 4, Article No. 23, 27 p. (2014; Zbl 1321.68274) Full Text: DOI Link
Coja-Oghlan, Amin; Zdeborová, Lenka The condensation transition in random hypergraph 2-coloring. (English) Zbl 1421.68068 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 241-250 (2012). MSC: 68Q25 05C15 05C65 05C80 68Q87 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} and \textit{L. Zdeborová}, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 241--250 (2012; Zbl 1421.68068) Full Text: arXiv Link
Goerdt, Andreas; Falke, Lutz Satisfiability thresholds beyond \(k\)-XORSAT. (English) Zbl 1360.68779 Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. 7th international computer science symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3–7, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-30641-9/pbk). Lecture Notes in Computer Science 7353, 148-159 (2012). MSC: 68T20 PDFBibTeX XMLCite \textit{A. Goerdt} and \textit{L. Falke}, Lect. Notes Comput. Sci. 7353, 148--159 (2012; Zbl 1360.68779) Full Text: DOI arXiv
Connamacher, Harold Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT. (English) Zbl 1280.68237 Theor. Comput. Sci. 421, 25-55 (2012). MSC: 68T20 68Q87 68Q25 PDFBibTeX XMLCite \textit{H. Connamacher}, Theor. Comput. Sci. 421, 25--55 (2012; Zbl 1280.68237) Full Text: DOI
Dani, Varsha; Moore, Cristopher Independent sets in random graphs from the weighted second moment method. (English) Zbl 1343.05135 Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 472-482 (2011). MSC: 05C80 05C69 PDFBibTeX XMLCite \textit{V. Dani} and \textit{C. Moore}, Lect. Notes Comput. Sci. 6845, 472--482 (2011; Zbl 1343.05135) Full Text: DOI arXiv
Coja-Oghlan, Amin; Pachon-Pinzon, Angelica Y. The decimation process in random \(k\)-SAT. (English) Zbl 1332.68069 Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 305-316 (2011). MSC: 68Q25 68Q87 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} and \textit{A. Y. Pachon-Pinzon}, Lect. Notes Comput. Sci. 6755, 305--316 (2011; Zbl 1332.68069) Full Text: DOI
Hervé, Daudé; Vlady, Ravelomanana Random 2 XORSAT phase transition. (English) Zbl 1206.68285 Algorithmica 59, No. 1, 48-65 (2011). MSC: 68T20 05C80 PDFBibTeX XMLCite \textit{D. Hervé} and \textit{R. Vlady}, Algorithmica 59, No. 1, 48--65 (2011; Zbl 1206.68285) Full Text: DOI
Goerdt, Andreas On random betweenness constraints. (English) Zbl 1258.68101 Comb. Probab. Comput. 19, No. 5-6, 775-790 (2010). MSC: 68Q87 68Q25 PDFBibTeX XMLCite \textit{A. Goerdt}, Comb. Probab. Comput. 19, No. 5--6, 775--790 (2010; Zbl 1258.68101) Full Text: DOI
Sun, Y. F.; Guo, B. H.; Wei, W.; Zheng, Z. M. On the thresholds in linear and nonlinear Boolean equations. (English) Zbl 1202.82031 Eur. Phys. J. B, Condens. Matter Complex Syst. 76, No. 1, 123-146 (2010). MSC: 82B26 06E30 68Q99 PDFBibTeX XMLCite \textit{Y. F. Sun} et al., Eur. Phys. J. B, Condens. Matter Complex Syst. 76, No. 1, 123--146 (2010; Zbl 1202.82031) Full Text: DOI
Coja-Oghlan, Amin; Krivelevich, Michael; Vilenchik, Dan Why almost all \(k\)-colorable graphs are easy to color. (English) Zbl 1216.05031 Theory Comput. Syst. 46, No. 3, 523-565 (2010). MSC: 05C15 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Theory Comput. Syst. 46, No. 3, 523--565 (2010; Zbl 1216.05031) Full Text: DOI
Molloy, Michael When does the giant component bring unsatisfiability? (English) Zbl 1195.05077 Combinatorica 28, No. 6, 693-734 (2008). Reviewer: David B. Penman (Colchester) MSC: 05C82 68Q25 60C05 PDFBibTeX XMLCite \textit{M. Molloy}, Combinatorica 28, No. 6, 693--734 (2008; Zbl 1195.05077) Full Text: DOI
Daudé, Hervé; Ravelomanana, Vlady Random 2-XORSAT at the satisfiability threshold. (English) Zbl 1136.68518 Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 12-23 (2008). MSC: 68T20 05C80 PDFBibTeX XMLCite \textit{H. Daudé} and \textit{V. Ravelomanana}, Lect. Notes Comput. Sci. 4957, 12--23 (2008; Zbl 1136.68518) Full Text: DOI
Krivelevich, Michael; Nachmias, Asaf Coloring complete bipartite graphs from random lists. (English) Zbl 1110.05035 Random Struct. Algorithms 29, No. 4, 436-449 (2006). MSC: 05C15 05C65 05C80 60C05 05D40 PDFBibTeX XMLCite \textit{M. Krivelevich} and \textit{A. Nachmias}, Random Struct. Algorithms 29, No. 4, 436--449 (2006; Zbl 1110.05035) Full Text: DOI arXiv
Kaporis, Alexis C.; Kirousis, Lefteris M.; Lalas, Efthimios G. The probabilistic analysis of a greedy satisfiability algorithm. (English) Zbl 1099.68100 Random Struct. Algorithms 28, No. 4, 444-480 (2006). MSC: 68T20 68W40 60C05 PDFBibTeX XMLCite \textit{A. C. Kaporis} et al., Random Struct. Algorithms 28, No. 4, 444--480 (2006; Zbl 1099.68100) Full Text: DOI
Kaporis, Alexis C.; Kirousis, Lefteris M.; Lalas, Efthimios Selecting complementary pairs of literals. (English) Zbl 1179.68144 Kranakis, Evangelos (ed.) et al., Typical case complexity and phase transitions. Papers from the workshop, Ottawa, ON, Canada, May 14–16, 2003. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 16, 47-70 (2003). MSC: 68T20 PDFBibTeX XMLCite \textit{A. C. Kaporis} et al., Electron. Notes Discrete Math. 16, 47--70 (2003; Zbl 1179.68144) Full Text: DOI