Amin Coja-Oghlan

Affiliations:
  • Goethe University of Frankfurt, Mathematics Institute, Frankfurt am Main, Germany


According to our database1, Amin Coja-Oghlan authored at least 110 papers between 2002 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Noisy group testing via spatial coupling.
CoRR, 2024

2023
The rank of sparse random matrices.
Random Struct. Algorithms, 2023

The k-XORSAT threshold revisited.
CoRR, 2023

The Full Rank Condition for Sparse Random Matrices.
Proceedings of the Approximation, 2023

2022
The Ising Antiferromagnet and Max Cut on Random Regular Graphs.
SIAM J. Discret. Math., 2022

Lower Bounds on the Chromatic Number of Random Graphs.
Comb., 2022

Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study.
Proceedings of the 20th International Symposium on Experimental Algorithms, 2022

The Sparse Parity Matrix.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On the Hierarchy of Distributed Majority Protocols.
Proceedings of the 26th International Conference on Principles of Distributed Systems, 2022

Metastability of the Potts Ferromagnet on Random Regular Graphs.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Statistical and Computational Phase Transitions in Group Testing.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021
The Cut Metric for Probability Distributions.
SIAM J. Discret. Math., 2021

The number of satisfying assignments of random 2-SAT formulas.
Random Struct. Algorithms, 2021

Optimal group testing.
Comb. Probab. Comput., 2021

The full rank condition for sparse random matrices.
CoRR, 2021

Inference and Mutual Information on Random Factor Graphs.
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2020
Information-Theoretic and Algorithmic Thresholds for Group Testing.
IEEE Trans. Inf. Theory, 2020

The replica symmetric phase of random constraint satisfaction problems.
Comb. Probab. Comput., 2020

Belief Propagation on the random k-SAT model.
CoRR, 2020

The random 2-SAT partition function.
CoRR, 2020

The Satisfiability Threshold For Random Linear Equations.
Comb., 2020

2019
Hypergraph coloring up to condensation.
Random Struct. Algorithms, 2019

Core forging and local limit theorems for the <i>k</i>-core of random graphs.
J. Comb. Theory, Ser. B, 2019

Optimal non-adaptive group testing.
CoRR, 2019

The rank of sparse random matrices.
CoRR, 2019

2018
The Number of Satisfying Assignments of Random Regular k-SAT Formulas.
Comb. Probab. Comput., 2018

The rank of random matrices over finite fields.
CoRR, 2018

Local Convergence of Random Graph Colorings.
Comb., 2018

2017
The Minimum Bisection in the Planted Bisection Model.
Theory Comput., 2017

Walksat Stalls Well Below Satisfiability.
SIAM J. Discret. Math., 2017

Belief Propagation Guided Decimation Fails on Random Formulas.
J. ACM, 2017

Limits of discrete distributions and Gibbs measures on random graphs.
Eur. J. Comb., 2017

Planting Colourings Silently.
Comb. Probab. Comput., 2017

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

Information-theoretic thresholds from the cavity method.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Charting the Replica Symmetric Phase.
Proceedings of the Approximation, 2017

2016
Harnessing the Bethe free energy.
Random Struct. Algorithms, 2016

On the chromatic number of random regular graphs.
J. Comb. Theory, Ser. B, 2016

On the Potts Antiferromagnet on Random Graphs.
Electron. J. Comb., 2016

Belief Propagation on Replica Symmetric Random Factor Graph Models.
Proceedings of the Approximation, 2016

The Condensation Phase Transition in the Regular k-SAT Model.
Proceedings of the Approximation, 2016

2015
On independent sets in random graphs.
Random Struct. Algorithms, 2015

How does the core sit inside the mantle?
Electron. Notes Discret. Math., 2015

'The Asymptotic Number of Connected <i>d</i>-Uniform Hypergraphs' - CORRIGENDUM.
Comb. Probab. Comput., 2015

Contagious Sets in Expanders.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Analyzing Walksat on Random Formulas.
SIAM J. Comput., 2014

The Asymptotic Number of Connected <i>d</i>-Uniform Hypergraphs.
Comb. Probab. Comput., 2014

Local Limit Theorems for the Giant Component of Random Hypergraphs.
Comb. Probab. Comput., 2014

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

The asymptotic k-SAT threshold.
Proceedings of the Symposium on Theory of Computing, 2014

The Condensation Phase Transition in Random Graph Coloring.
Proceedings of the Approximation, 2014

2013
Random regular k-SAT.
CoRR, 2013

Upper-Bounding the k-Colorability Threshold by Counting Covers.
Electron. J. Comb., 2013

Going after the k-SAT threshold.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Chasing the K-Colorability Threshold.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
The Decimation Process in Random k-SAT.
SIAM J. Discret. Math., 2012

Propagation Connectivity of Random Hypergraphs.
Electron. J. Comb., 2012

Catching the k-NAESAT threshold.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The condensation transition in random hypergraph 2-coloring.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011
On the solution-space geometry of random constraint satisfaction problems.
Random Struct. Algorithms, 2011

On Belief Propagation Guided Decimation for Random k-SAT.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Decimation Process in Random <i>k</i>-SAT.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Eulerian Circuits.
Proceedings of the Algorithms Unplugged, 2011

2010
An Efficient Sparse Regularity Concept.
SIAM J. Discret. Math., 2010

A Better Algorithm for Random k-SAT.
SIAM J. Comput., 2010

Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions.
SIAM J. Comput., 2010

The order of the giant component of random hypergraphs.
Random Struct. Algorithms, 2010

Why Almost All <i>k</i>-Colorable Graphs Are Easy to Color.
Theory Comput. Syst., 2010

Graph Partitioning via Adaptive Spectral Techniques.
Comb. Probab. Comput., 2010

2009
Finding Planted Partitions in Random Graphs with General Degree Distributions.
SIAM J. Discret. Math., 2009

The evolution of the min-min random graph process.
Discret. Math., 2009

A Spectral Approach to Analysing Belief Propagation for 3-Colouring.
Comb. Probab. Comput., 2009

Random Constraint Satisfaction Problems
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.
Electron. J. Comb., 2009

On smoothed <i>k</i>-CNF formulas and the Walksat algorithm.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

A Better Algorithm for Random <i>k</i>-SAT.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008
Die Eulertour.
Proceedings of the Taschenbuch der Algorithmen, 2008

On the chromatic number of random graphs.
J. Comb. Theory, Ser. B, 2008

Random k-SAT: The Limiting Probability for Satisfiability for Moderately Growing k.
Electron. J. Comb., 2008

Partitioning Random Graphs with General Degree Distributions.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Algorithmic Barriers from Phase Transitions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Counting connected graphs and hypergraphs via the probabilistic method.
Random Struct. Algorithms, 2007

Solving NP-hard semirandom graph problems in polynomial expected time.
J. Algorithms, 2007

Strong Refutation Heuristics for Random k-SAT.
Comb. Probab. Comput., 2007

On the Laplacian Eigenvalues of G<sub>n, p</sub>.
Comb. Probab. Comput., 2007

Colouring Semirandom Graphs.
Comb. Probab. Comput., 2007

A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
CoRR, 2007

Why Almost All <i>k</i> -Colorable Graphs Are Easy.
Proceedings of the STACS 2007, 2007

Separating Populations with Wide Data: A Spectral Analysis.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006
MAX <i>k</i>-CUT and approximating the chromatic number of random graphs.
Random Struct. Algorithms, 2006

A spectral heuristic for bisecting random graphs.
Random Struct. Algorithms, 2006

A heuristic for the Stacker Crane Problem on trees which is almost surely exact.
J. Algorithms, 2006

An improved algorithm for approximating the chromatic number of G<sub>n, p</sub>.
Inf. Process. Lett., 2006

Finding Large Independent Sets in Polynomial Expected Time.
Comb. Probab. Comput., 2006

Spectral Partitioning of Random Graphs with Given Expected Degrees.
Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

An Adaptive Spectral Heuristic for Partitioning Random Graphs.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
A Hard Dial-a-Ride Problem that is Easy on Average.
J. Sched., 2005

The Lovász Number of Random Graphs.
Comb. Probab. Comput., 2005

2004
Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT.
Theor. Comput. Sci., 2004

Exact and approximative algorithms for coloring G(n, p).
Random Struct. Algorithms, 2004

Coloring Semirandom Graphs Optimally.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Revisiting the Algebra of Petri Net Processes under the Collective Token Philosophy.
Fundam. Informaticae, 2003

The Lovasz number of random graph
Electron. Colloquium Comput. Complex., 2003

Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques
Electron. Colloquium Comput. Complex., 2003

Colouring Random Graphs in Expected Polynomial Time.
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.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Certifying Unsatisfiability of Random 2<i>k</i>-SAT Formulas Using Approximation Techniques.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002
Finding Sparse Induced Subgraphs of Semirandom Graphs.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Varianz und Erwartungswert in Operatoralgebren.
Berichte aus der Informatik, Shaker, ISBN: 978-3-8265-9760-2, 2002


  Loading...