Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Arnab Chatterjee, Amin Coja-Oghlan, Noela Müller, Connor Riddlesden, Maurice Rolvien, Pavel Zakharov, and Haodong Zhu. The Number of Random 2-SAT Solutions Is Asymptotically Log-Normal. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chatterjee_et_al:LIPIcs.APPROX/RANDOM.2024.39, author = {Chatterjee, Arnab and Coja-Oghlan, Amin and M\"{u}ller, Noela and Riddlesden, Connor and Rolvien, Maurice and Zakharov, Pavel and Zhu, Haodong}, title = {{The Number of Random 2-SAT Solutions Is Asymptotically Log-Normal}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.39}, URN = {urn:nbn:de:0030-drops-210329}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.39}, annote = {Keywords: satisfiability problem, 2-SAT, random satisfiability, central limit theorem} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Evan Chang, Neel Kolhe, and Youngtak Sohn. Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chang_et_al:LIPIcs.APPROX/RANDOM.2024.47, author = {Chang, Evan and Kolhe, Neel and Sohn, Youngtak}, title = {{Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {47:1--47:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.47}, URN = {urn:nbn:de:0030-drops-210402}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.47}, annote = {Keywords: Random constraint satisfaction problem, replica symmetry breaking, interpolation bound} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Aiya Kuchukova, Marcus Pappik, Will Perkins, and Corrine Yap. Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 56:1-56:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kuchukova_et_al:LIPIcs.APPROX/RANDOM.2024.56, author = {Kuchukova, Aiya and Pappik, Marcus and Perkins, Will and Yap, Corrine}, title = {{Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {56:1--56:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.56}, URN = {urn:nbn:de:0030-drops-210493}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.56}, annote = {Keywords: ferromagnetic Ising model, fixed-magnetization Ising model, Kawasaki dynamics, Glauber dynamics, mixing time} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carlson_et_al:LIPIcs.ICALP.2024.35, author = {Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Potukuchi, Aditya}, title = {{A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {35:1--35:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.35}, URN = {urn:nbn:de:0030-drops-201782}, doi = {10.4230/LIPIcs.ICALP.2024.35}, annote = {Keywords: approximate counting, independent sets, bipartite graphs, graph containers} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Naoto Ohsaka. Alphabet Reduction for Reconfiguration Problems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 113:1-113:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ohsaka:LIPIcs.ICALP.2024.113, author = {Ohsaka, Naoto}, title = {{Alphabet Reduction for Reconfiguration Problems}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {113:1--113:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.113}, URN = {urn:nbn:de:0030-drops-202560}, doi = {10.4230/LIPIcs.ICALP.2024.113}, annote = {Keywords: reconfiguration problems, hardness of approximation, Hadamard codes, alphabet reduction} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Kingsley Yung. Limits of Sequential Local Algorithms on the Random k-XORSAT Problem. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 123:1-123:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{yung:LIPIcs.ICALP.2024.123, author = {Yung, Kingsley}, title = {{Limits of Sequential Local Algorithms on the Random k-XORSAT Problem}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {123:1--123:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.123}, URN = {urn:nbn:de:0030-drops-202666}, doi = {10.4230/LIPIcs.ICALP.2024.123}, annote = {Keywords: Random k-XORSAT, Sequential local algorithms, Average-case complexity, Phase transition, Overlap gap property} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Amin Coja-Oghlan, Jane Gao, Max Hahn-Klimroth, Joon Lee, Noela Müller, and Maurice Rolvien. The Full Rank Condition for Sparse Random Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX/RANDOM.2023.54, author = {Coja-Oghlan, Amin and Gao, Jane and Hahn-Klimroth, Max and Lee, Joon and M\"{u}ller, Noela and Rolvien, Maurice}, title = {{The Full Rank Condition for Sparse Random Matrices}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {54:1--54:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.54}, URN = {urn:nbn:de:0030-drops-188792}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.54}, annote = {Keywords: random matrices, rank, finite fields, rationals} }
Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the Hierarchy of Distributed Majority Protocols. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berenbrink_et_al:LIPIcs.OPODIS.2022.23, author = {Berenbrink, Petra and Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin}, title = {{On the Hierarchy of Distributed Majority Protocols}}, booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-265-5}, ISSN = {1868-8969}, year = {2023}, volume = {253}, editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.23}, URN = {urn:nbn:de:0030-drops-176434}, doi = {10.4230/LIPIcs.OPODIS.2022.23}, annote = {Keywords: Consensus, Majority, Hierarchy, Stochastic Dominance, Population Protocols, Gossip Model, Strassen’s Theorem} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 42:1-42:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2022.42, author = {Guruswami, Venkatesan and Kothari, Pravesh K. and Manohar, Peter}, title = {{Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {42:1--42:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.42}, URN = {urn:nbn:de:0030-drops-171642}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.42}, annote = {Keywords: Planted clique, Average-case complexity, Spectral refutation, Random matrix theory} }
Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)
Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, and Manuel Penschuck. Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cojaoghlan_et_al:LIPIcs.SEA.2022.8, author = {Coja-Oghlan, Amin and Hahn-Klimroth, Max and Loick, Philipp and Penschuck, Manuel}, title = {{Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study}}, booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-251-8}, ISSN = {1868-8969}, year = {2022}, volume = {233}, editor = {Schulz, Christian and U\c{c}ar, Bora}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.8}, URN = {urn:nbn:de:0030-drops-165422}, doi = {10.4230/LIPIcs.SEA.2022.8}, annote = {Keywords: Group testing, Probabilistic Construction, Belief Propagation, Simulation} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Štefankovič, and Eric Vigoda. Metastability of the Potts Ferromagnet on Random Regular Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 45:1-45:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cojaoghlan_et_al:LIPIcs.ICALP.2022.45, author = {Coja-Oghlan, Amin and Galanis, Andreas and Goldberg, Leslie Ann and Ravelomanana, Jean Bernoulli and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric}, title = {{Metastability of the Potts Ferromagnet on Random Regular Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {45:1--45:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.45}, URN = {urn:nbn:de:0030-drops-163865}, doi = {10.4230/LIPIcs.ICALP.2022.45}, annote = {Keywords: Markov chains, sampling, random regular graph, Potts model} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Charilaos Efthymiou. On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{efthymiou:LIPIcs.ICALP.2022.57, author = {Efthymiou, Charilaos}, title = {{On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {57:1--57:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.57}, URN = {urn:nbn:de:0030-drops-163982}, doi = {10.4230/LIPIcs.ICALP.2022.57}, annote = {Keywords: spin-system, spin-glass, sparse random (hyper)graph, approximate sampling, efficient algorithm} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Noela Müller, Konstantinos Panagiotou, and Matija Pasch. Inference and Mutual Information on Random Factor Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cojaoghlan_et_al:LIPIcs.STACS.2021.24, author = {Coja-Oghlan, Amin and Hahn-Klimroth, Max and Loick, Philipp and M\"{u}ller, Noela and Panagiotou, Konstantinos and Pasch, Matija}, title = {{Inference and Mutual Information on Random Factor Graphs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.24}, URN = {urn:nbn:de:0030-drops-136692}, doi = {10.4230/LIPIcs.STACS.2021.24}, annote = {Keywords: Information theory, random factor graphs, inference problems, phase transitions} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Andrea Lincoln and Adam Yedidia. Faster Random k-CNF Satisfiability. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 78:1-78:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lincoln_et_al:LIPIcs.ICALP.2020.78, author = {Lincoln, Andrea and Yedidia, Adam}, title = {{Faster Random k-CNF Satisfiability}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {78:1--78:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.78}, URN = {urn:nbn:de:0030-drops-124857}, doi = {10.4230/LIPIcs.ICALP.2020.78}, annote = {Keywords: Random k-SAT, Average-Case, Algorithms} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick. Information-Theoretic and Algorithmic Thresholds for Group Testing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cojaoghlan_et_al:LIPIcs.ICALP.2019.43, author = {Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Loick, Philipp}, title = {{Information-Theoretic and Algorithmic Thresholds for Group Testing}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {43:1--43:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.43}, URN = {urn:nbn:de:0030-drops-106196}, doi = {10.4230/LIPIcs.ICALP.2019.43}, annote = {Keywords: Group testing problem, phase transitions, information theory, efficient algorithms, sharp threshold, Bayesian inference} }
Feedback for Dagstuhl Publishing