Amin Coja-Oghlan

Johannes Christian Lawnik

Lena Krieg

Olga Scheftelowitsch

CoRR, 2024

Noisy group testing via spatial coupling.

[BibT_eX]

[DOI]

CoRR, 2024

The $k$-XORSAT Threshold Revisited.

[BibT_eX]

[DOI]

Electron. J. Comb., 2024

The Number of Random 2-SAT Solutions Is Asymptotically Log-Normal.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

The rank of sparse random matrices.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2023

The Full Rank Condition for Sparse Random Matrices.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

The Ising Antiferromagnet and Max Cut on Random Regular Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2022

Lower Bounds on the Chromatic Number of Random Graphs.

[BibT_eX]

[DOI]

Peter J. Ayre

Jean Bernoulli Ravelomanana

Catherine S. Greenhill

Comb., 2022

Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study.

[BibT_eX]

[DOI]

Proceedings of the 20th International Symposium on Experimental Algorithms, 2022

The Sparse Parity Matrix.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On the Hierarchy of Distributed Majority Protocols.

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on Principles of Distributed Systems, 2022

Metastability of the Potts Ferromagnet on Random Regular Graphs.

[BibT_eX]

[DOI]

Jean Bernoulli Ravelomanana

Andreas Galanis

Leslie Ann Goldberg

Daniel Stefankovic

Eric Vigoda

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Statistical and Computational Phase Transitions in Group Testing.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

The Cut Metric for Probability Distributions.

[BibT_eX]

[DOI]

Max Hahn-Klimroth

SIAM J. Discret. Math., 2021

The number of satisfying assignments of random 2-SAT formulas.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2021

Optimal group testing.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2021

Inference and Mutual Information on Random Factor Graphs.

[BibT_eX]

[DOI]

Matija Pasch

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2020

Information-Theoretic and Algorithmic Thresholds for Group Testing.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

The replica symmetric phase of random constraint satisfaction problems.

[BibT_eX]

[DOI]

Tobias Kapetanopoulos

Noëla Müller

Comb. Probab. Comput., 2020

Belief Propagation on the random k-SAT model.

[BibT_eX]

[DOI]

Noëla Müller

Jean B. Ravelomanana

CoRR, 2020

The random 2-SAT partition function.

[BibT_eX]

[DOI]

CoRR, 2020

The Satisfiability Threshold For Random Linear Equations.

[BibT_eX]

[DOI]

Comb., 2020

2019

Hypergraph coloring up to condensation.

[BibT_eX]

[DOI]

Peter J. Ayre

Catherine S. Greenhill

Random Struct. Algorithms, 2019

Core forging and local limit theorems for the k-core of random graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2019

Optimal non-adaptive group testing.

[BibT_eX]

[DOI]

CoRR, 2019

The rank of sparse random matrices.

[BibT_eX]

[DOI]

CoRR, 2019

2018

The Number of Satisfying Assignments of Random Regular k-SAT Formulas.

[BibT_eX]

[DOI]

Nick Wormald

Comb. Probab. Comput., 2018

The rank of random matrices over finite fields.

[BibT_eX]

[DOI]

Pu Gao

CoRR, 2018

Local Convergence of Random Graph Colorings.

[BibT_eX]

[DOI]

Nor Jaafari

Comb., 2018

2017

The Minimum Bisection in the Planted Bisection Model.

[BibT_eX]

[DOI]

Theory Comput., 2017

Walksat Stalls Well Below Satisfiability.

[BibT_eX]

[DOI]

Amir Haqshenas

Samuel Hetterich

SIAM J. Discret. Math., 2017

Belief Propagation Guided Decimation Fails on Random Formulas.

[BibT_eX]

[DOI]

J. ACM, 2017

Limits of discrete distributions and Gibbs measures on random graphs.

[BibT_eX]

[DOI]

Will Perkins

Kathrin Skubch

Eur. J. Comb., 2017

Planting Colourings Silently.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2017

Core forging and local limit theorems for the k-core of random graphs.

[BibT_eX]

[DOI]

CoRR, 2017

Information-theoretic thresholds from the cavity method.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Charting the Replica Symmetric Phase.

[BibT_eX]

[DOI]

Tobias Kapetanopoulos

Proceedings of the Approximation, 2017

2016

Harnessing the Bethe free energy.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

On the chromatic number of random regular graphs.

[BibT_eX]

[DOI]

Samuel Hetterich

J. Comb. Theory B, 2016

On the Potts Antiferromagnet on Random Graphs.

[BibT_eX]

[DOI]

Nor Jaafari

Electron. J. Comb., 2016

Belief Propagation on Replica Symmetric Random Factor Graph Models.

[BibT_eX]

[DOI]

Will Perkins

Proceedings of the Approximation, 2016

The Condensation Phase Transition in the Regular k-SAT Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

On independent sets in random graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2015

How does the core sit inside the mantle?

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2015

'The Asymptotic Number of Connected d-Uniform Hypergraphs' - CORRIGENDUM.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2015

Contagious Sets in Expanders.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Analyzing Walksat on Random Formulas.

[BibT_eX]

[DOI]

Alan M. Frieze

SIAM J. Comput., 2014

The Asymptotic Number of Connected d-Uniform Hypergraphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2014

Local Limit Theorems for the Giant Component of Random Hypergraphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2014

A positive temperature phase transition in random hypergraph 2-coloring.

[BibT_eX]

[DOI]

Felicia Raßmann

CoRR, 2014

The asymptotic k-SAT threshold.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

The Condensation Phase Transition in Random Graph Coloring.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Random regular k-SAT.

[BibT_eX]

[DOI]

CoRR, 2013

Upper-Bounding the k-Colorability Threshold by Counting Covers.

[BibT_eX]

[DOI]

Electron. J. Comb., 2013

Going after the k-SAT threshold.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Chasing the K-Colorability Threshold.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The Decimation Process in Random k-SAT.

[BibT_eX]

[DOI]

Angélica Y. Pachón-Pinzon

SIAM J. Discret. Math., 2012

Propagation Connectivity of Random Hypergraphs.

[BibT_eX]

[DOI]

Mikael Onsjö

Osamu Watanabe

Electron. J. Comb., 2012

Catching the k-NAESAT threshold.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The condensation transition in random hypergraph 2-coloring.

[BibT_eX]

[DOI]

Lenka Zdeborová

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

On the solution-space geometry of random constraint satisfaction problems.

[BibT_eX]

[DOI]

Dimitris Achlioptas

Federico Ricci-Tersenghi

Random Struct. Algorithms, 2011

On Belief Propagation Guided Decimation for Random k-SAT.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Decimation Process in Random k-SAT.

[BibT_eX]

[DOI]

Angélica Y. Pachón-Pinzon

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Eulerian Circuits.

[BibT_eX]

[DOI]

Peter Liske

Proceedings of the Algorithms Unplugged, 2011

2010

An Efficient Sparse Regularity Concept.

[BibT_eX]

[DOI]

Colin Cooper

Alan M. Frieze

SIAM J. Discret. Math., 2010

A Better Algorithm for Random k-SAT.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

The order of the giant component of random hypergraphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2010

Why Almost All k-Colorable Graphs Are Easy to Color.

[BibT_eX]

[DOI]

Michael Krivelevich

Theory Comput. Syst., 2010

2009

Finding Planted Partitions in Random Graphs with General Degree Distributions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

The evolution of the min-min random graph process.

[BibT_eX]

[DOI]

Discret. Math., 2009

A Spectral Approach to Analysing Belief Propagation for 3-Colouring.

[BibT_eX]

[DOI]

Elchanan Mossel

Comb. Probab. Comput., 2009

Random Constraint Satisfaction Problems

[BibT_eX]

[DOI]

Proceedings of the Proceedings Fifth Workshop on Developments in Computational Models--Computational Models From Nature, 2009

The Spectral Gap of Random Graphs with Given Expected Degrees.

[BibT_eX]

[DOI]

Electron. J. Comb., 2009

On smoothed k-CNF formulas and the Walksat algorithm.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

A Better Algorithm for Random k-SAT.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Die Eulertour.

[BibT_eX]

[DOI]

Peter Liske

Proceedings of the Taschenbuch der Algorithmen, 2008

On the chromatic number of random graphs.

[BibT_eX]

[DOI]

Angelika Steger

J. Comb. Theory B, 2008

Random k-SAT: The Limiting Probability for Satisfiability for Moderately Growing k.

[BibT_eX]

[DOI]

Alan M. Frieze

Electron. J. Comb., 2008

Partitioning Random Graphs with General Degree Distributions.

[BibT_eX]

[DOI]

Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Algorithmic Barriers from Phase Transitions.

[BibT_eX]

[DOI]

Dimitris Achlioptas

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Counting connected graphs and hypergraphs via the probabilistic method.

[BibT_eX]

[DOI]

Cristopher Moore

Vishal Sanwalani

Random Struct. Algorithms, 2007

Solving NP-hard semirandom graph problems in polynomial expected time.

[BibT_eX]

[DOI]

J. Algorithms, 2007

Strong Refutation Heuristics for Random k-SAT.

[BibT_eX]

[DOI]

Andreas Goerdt

Comb. Probab. Comput., 2007

On the Laplacian Eigenvalues of Gn, p.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

Colouring Semirandom Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

A Spectral Approach to Analyzing Belief Propagation for 3-Coloring

[BibT_eX]

[DOI]

Elchanan Mossel

CoRR, 2007

Why Almost All k -Colorable Graphs Are Easy.

[BibT_eX]

[DOI]

Michael Krivelevich

Proceedings of the STACS 2007, 2007

Separating Populations with Wide Data: A Spectral Analysis.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006

MAX k-CUT and approximating the chromatic number of random graphs.

[BibT_eX]

[DOI]

Cristopher Moore

Vishal Sanwalani

Random Struct. Algorithms, 2006

A spectral heuristic for bisecting random graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2006

A heuristic for the Stacker Crane Problem on trees which is almost surely exact.

[BibT_eX]

[DOI]

Sven Oliver Krumke

Till Nierhoff

J. Algorithms, 2006

An improved algorithm for approximating the chromatic number of Gn, p.

[BibT_eX]

[DOI]

Lars Kuhtz

Inf. Process. Lett., 2006

Graph partitioning via adaptive spectral techniques.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Finding Large Independent Sets in Polynomial Expected Time.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2006

Spectral Partitioning of Random Graphs with Given Expected Degrees.

[BibT_eX]

[DOI]

Andreas Goerdt

Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

An Adaptive Spectral Heuristic for Partitioning Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

A Hard Dial-a-Ride Problem that is Easy on Average.

[BibT_eX]

[DOI]

Sven Oliver Krumke

Till Nierhoff

J. Sched., 2005

The Lovász Number of Random Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2005

2004

Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Exact and approximative algorithms for coloring G(n, p).

[BibT_eX]

[DOI]

Anusch Taraz

Random Struct. Algorithms, 2004

Coloring Semirandom Graphs Optimally.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Revisiting the Algebra of Petri Net Processes under the Collective Token Philosophy.

[BibT_eX]

[DOI]

Mark-Oliver Stehr

Fundam. Informaticae, 2003

The Lovasz number of random graph

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Colouring Random Graphs in Expected Polynomial Time.

[BibT_eX]

[DOI]

Anusch Taraz

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

MAX k-CUT and Approximating the Chromatic Number of Random Graphs.

[BibT_eX]

[DOI]

Cristopher Moore

Vishal Sanwalani

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002

Finding Sparse Induced Subgraphs of Semirandom Graphs.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Varianz und Erwartungswert in Operatoralgebren.

[BibT_eX]