Amin Coja-Oghlan

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
The Number of Satisfying Assignments of Random Regular k-SAT Formulas.
Combinatorics, Probability & Computing, 2018

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

The replica symmetric phase of random constraint satisfaction problems.
CoRR, 2018

Local Convergence of Random Graph Colorings.
Combinatorica, 2018

2017
The Minimum Bisection in the Planted Bisection Model.
Theory of Computing, 2017

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

How does the core sit inside the mantle?
Random Struct. Algorithms, 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.
Combinatorics, Probability & Computing, 2017

The satisfiability threshold for random linear equations.
CoRR, 2017

Charting the replica symmetric phase.
CoRR, 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

The number of satisfying assignments of random regular k-SAT formulas.
CoRR, 2016

Belief Propagation on replica symmetric random factor graph models.
CoRR, 2016

Information-theoretic thresholds from the cavity method.
CoRR, 2016

On the Potts Antiferromagnet on Random Graphs.
Electr. 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?
Electronic Notes in Discrete Mathematics, 2015

'The Asymptotic Number of Connected d-Uniform Hypergraphs' - CORRIGENDUM.
Combinatorics, Probability & Computing, 2015

Local convergence of random graph colorings.
CoRR, 2015

The minimum bisection in the planted bisection model.
CoRR, 2015

How does the core sit inside the mantle?
CoRR, 2015

The condensation phase transition in the regular k-SAT model.
CoRR, 2015

Harnessing the Bethe free energy.
CoRR, 2015

Hypergraph coloring up to condensation.
CoRR, 2015

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

Local Convergence of Random Graph Colorings.
Proceedings of the Approximation, 2015

The Minimum Bisection in the Planted Bisection Model.
Proceedings of the Approximation, 2015

Harnessing the Bethe Free Energy.
Proceedings of the Approximation, 2015

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

The Asymptotic Number of Connected d-Uniform Hypergraphs.
Combinatorics, Probability & Computing, 2014

Local Limit Theorems for the Giant Component of Random Hypergraphs.
Combinatorics, Probability & Computing, 2014

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

The condensation phase transition in random graph coloring.
CoRR, 2014

Planting colourings silently.
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
Upper-bounding the k-colorability threshold by counting covers
CoRR, 2013

Chasing the k-colorability threshold
CoRR, 2013

Contagious Sets in Expanders.
CoRR, 2013

Random regular k-SAT.
CoRR, 2013

Upper-Bounding the k-Colorability Threshold by Counting Covers.
Electr. 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. Discrete Math., 2012

Going after the k-SAT Threshold
CoRR, 2012

Propagation Connectivity of Random Hypergraphs.
Electr. 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

Analyzing Walksat on Random Formulas.
Proceedings of the 9th Meeting on Analytic Algorithmics and Combinatorics, 2012

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

Catching the k-NAESAT Threshold
CoRR, 2011

Analyzing Walksat on random formulas
CoRR, 2011

The decimation process in random k-SAT
CoRR, 2011

On independent sets in random graphs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete 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 k-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. Discrete 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 k-Colorable Graphs Are Easy to Color.
Theory Comput. Syst., 2010

Graph Partitioning via Adaptive Spectral Techniques.
Combinatorics, Probability & Computing, 2010

On independent sets in random graphs
CoRR, 2010

On belief propagation guided decimation for random k-SAT
CoRR, 2010

Propagation Connectivity of Random Hypergraphs.
Proceedings of the Approximation, 2010

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

The evolution of the min-min random graph process.
Discrete Mathematics, 2009

A Spectral Approach to Analysing Belief Propagation for 3-Colouring.
Combinatorics, Probability & Computing, 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.
Electr. J. Comb., 2009

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

An efficient sparse regularity concept.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

A Better Algorithm for Random k-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.
Electr. 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.
Combinatorics, Probability & Computing, 2007

On the Laplacian Eigenvalues of Gn, p.
Combinatorics, Probability & Computing, 2007

Colouring Semirandom Graphs.
Combinatorics, Probability & Computing, 2007

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

Why Almost All k -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

On the Chromatic Number of Random Graphs.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Local Limit Theorems for the Giant Component of Random Hypergraphs.
Proceedings of the Approximation, 2007

2006
MAX k-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 Gn, p.
Inf. Process. Lett., 2006

Graph partitioning via adaptive spectral techniques.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Finding Large Independent Sets in Polynomial Expected Time.
Combinatorics, Probability & Computing, 2006

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

The Spectral Gap of Random Graphs with Given Expected Degrees.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 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. Scheduling, 2005

The Lovász Number of Random Graphs.
Combinatorics, Probability & Computing, 2005

A spectral heuristic for bisecting random graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Counting Connected Graphs and Hypergraphs via the Probabilistic Method.
Proceedings of the Approximation, 2004

Strong Refutation Heuristics for Random k-SAT.
Proceedings of the Approximation, 2004

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

The Lovasz number of random graph
Electronic Colloquium on Computational Complexity (ECCC), 2003

Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques
Electronic Colloquium on Computational Complexity (ECCC), 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

Finding Large Independent Sets in Polynomial Expected Time.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

The Lovász Number of Random Graphs.
Proceedings of the Approximation, 2003

A Heuristic for the Stacker Crane Problem on Trees Which Is Almost Surely Exact.
Proceedings of the Algorithms and Computation, 14th International Symposium, 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 2k-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


  Loading...