Amin Coja-Oghlan

Amin Coja-Oghlan, Dan Vilenchik: Chasing the k-colorability threshold. CoRR abs/1304.1063 (2013)

Amin Coja-Oghlan, Angelica Y. Pachon-Pinzon: The Decimation Process in Random k-SAT. SIAM J. Discrete Math. 26(4): 1471-1509 (2012)

Amin Coja-Oghlan, Alan M. Frieze: Analyzing Walksat on Random Formulas. ANALCO 2012: 48-67

Amin Coja-Oghlan, Lenka Zdeborová: The condensation transition in random hypergraph 2-coloring. SODA 2012: 241-250

Amin Coja-Oghlan, Konstantinos Panagiotou: Catching the k-NAESAT threshold. STOC 2012: 899-908

Amin Coja-Oghlan, Konstantinos Panagiotou: Going after the k-SAT Threshold. CoRR abs/1212.1682 (2012)

Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms 38(3): 251-268 (2011)

Michael Behrisch, Amin Coja-Oghlan, Peter Liske: Eulerian Circuits. Algorithms Unplugged 2011: 277-283

Amin Coja-Oghlan, Angelica Y. Pachon-Pinzon: The Decimation Process in Random k-SAT. ICALP (1) 2011: 305-316

Amin Coja-Oghlan, Charilaos Efthymiou: On independent sets in random graphs. SODA 2011: 136-144

Amin Coja-Oghlan: On Belief Propagation Guided Decimation for Random k-SAT. SODA 2011: 957-966

Amin Coja-Oghlan, Angelica Y. Pachon-Pinzon: The decimation process in random k-SAT. CoRR abs/1102.3145 (2011)

Amin Coja-Oghlan, Alan M. Frieze: Analyzing Walksat on random formulas. CoRR abs/1106.0120 (2011)

Amin Coja-Oghlan, Konstantinos Panagiotou: Catching the k-NAESAT Threshold. CoRR abs/1111.1274 (2011)

Amin Coja-Oghlan: Graph Partitioning via Adaptive Spectral Techniques. Combinatorics, Probability & Computing 19(2): 227-284 (2010)

Amin Coja-Oghlan, Michael Krivelevich, Dan Vilenchik: Why Almost All k-Colorable Graphs Are Easy to Color. Theory Comput. Syst. 46(3): 523-565 (2010)

Michael Behrisch, Amin Coja-Oghlan, Mihyun Kang: The order of the giant component of random hypergraphs. Random Struct. Algorithms 36(2): 149-184 (2010)

Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtech Rödl, Mathias Schacht: Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions. SIAM J. Comput. 39(6): 2336-2362 (2010)

Amin Coja-Oghlan: A Better Algorithm for Random k-SAT. SIAM J. Comput. 39(7): 2823-2864 (2010)

Amin Coja-Oghlan, Colin Cooper, Alan M. Frieze: An Efficient Sparse Regularity Concept. SIAM J. Discrete Math. 23(4): 2000-2034 (2010)

Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe: Propagation Connectivity of Random Hypergraphs. APPROX-RANDOM 2010: 490-503

Amin Coja-Oghlan: On belief propagation guided decimation for random k-SAT. CoRR abs/1007.1328 (2010)

Amin Coja-Oghlan, Charilaos Efthymiou: On independent sets in random graphs. CoRR abs/1007.1378 (2010)

Amin Coja-Oghlan, André Lanka: The Spectral Gap of Random Graphs with Given Expected Degrees. Electr. J. Comb. 16(1) (2009)

Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik: A Spectral Approach to Analysing Belief Propagation for 3-Colouring. Combinatorics, Probability & Computing 18(6): 881-912 (2009)

Amin Coja-Oghlan, Mihyun Kang: The evolution of the min-min random graph process. Discrete Mathematics 309(13): 4527-4544 (2009)

Amin Coja-Oghlan, André Lanka: Finding Planted Partitions in Random Graphs with General Degree Distributions. SIAM J. Discrete Math. 23(4): 1682-1714 (2009)

Amin Coja-Oghlan: A Better Algorithm for Random k-SAT. ICALP (1) 2009: 292-303

Amin Coja-Oghlan, Colin Cooper, Alan M. Frieze: An efficient sparse regularity concept. SODA 2009: 207-216

Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik: On smoothed k-CNF formulas and the Walksat algorithm. SODA 2009: 451-460

Amin Coja-Oghlan: Random Constraint Satisfaction Problems. DCM 2009: 32-37

Amin Coja-Oghlan, Alan M. Frieze: Random k-SAT: The Limiting Probability for Satisfiability for Moderately Growing k. Electr. J. Comb. 15(1) (2008)

Amin Coja-Oghlan, Konstantinos Panagiotou, Angelika Steger: On the chromatic number of random graphs. J. Comb. Theory, Ser. B 98(5): 980-993 (2008)

Dimitris Achlioptas, Amin Coja-Oghlan: Algorithmic Barriers from Phase Transitions. FOCS 2008: 793-802

Amin Coja-Oghlan, André Lanka: Partitioning Random Graphs with General Degree Distributions. IFIP TCS 2008: 127-141

Michael Behrisch, Amin Coja-Oghlan, Peter Liske: Die Eulertour. Taschenbuch der Algorithmen 2008: 295-301

Amin Coja-Oghlan, Andreas Goerdt, André Lanka: Strong Refutation Heuristics for Random k-SAT. Combinatorics, Probability & Computing 16(1): 5-28 (2007)

Amin Coja-Oghlan: Colouring Semirandom Graphs. Combinatorics, Probability & Computing 16(4): 515-552 (2007)

Amin Coja-Oghlan: On the Laplacian Eigenvalues of G_{n, p}. Combinatorics, Probability & Computing 16(6): 923-946 (2007)

Amin Coja-Oghlan: Solving NP-hard semirandom graph problems in polynomial expected time. J. Algorithms 62(1): 19-46 (2007)

Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani: Counting connected graphs and hypergraphs via the probabilistic method. Random Struct. Algorithms 31(3): 288-329 (2007)

Michael Behrisch, Amin Coja-Oghlan, Mihyun Kang: Local Limit Theorems for the Giant Component of Random Hypergraphs. APPROX-RANDOM 2007: 341-352

Amin Coja-Oghlan, Konstantinos Panagiotou, Angelika Steger: On the Chromatic Number of Random Graphs. ICALP 2007: 777-788

Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtech Rödl, Mathias Schacht: Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions. ICALP 2007: 789-800

Avrim Blum, Amin Coja-Oghlan, Alan M. Frieze, Shuheng Zhou: Separating Populations with Wide Data: A Spectral Analysis. ISAAC 2007: 439-451

Amin Coja-Oghlan, Michael Krivelevich, Dan Vilenchik: Why Almost All k -Colorable Graphs Are Easy. STACS 2007: 121-132

Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik: A Spectral Approach to Analyzing Belief Propagation for 3-Coloring. CoRR abs/0712.0171 (2007)

Amin Coja-Oghlan: Finding Large Independent Sets in Polynomial Expected Time. Combinatorics, Probability & Computing 15(5): 731-751 (2006)

Amin Coja-Oghlan, Lars Kuhtz: An improved algorithm for approximating the chromatic number of G_{n, p}. Inf. Process. Lett. 99(6): 234-238 (2006)

Amin Coja-Oghlan, Sven Oliver Krumke, Till Nierhoff: A heuristic for the Stacker Crane Problem on trees which is almost surely exact. J. Algorithms 61(1): 1-19 (2006)

Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani: MAX k-CUT and approximating the chromatic number of random graphs. Random Struct. Algorithms 28(3): 289-322 (2006)

Amin Coja-Oghlan: A spectral heuristic for bisecting random graphs. Random Struct. Algorithms 29(3): 351-398 (2006)

Amin Coja-Oghlan, André Lanka: The Spectral Gap of Random Graphs with Given Expected Degrees. ICALP (1) 2006: 15-26

Amin Coja-Oghlan: An Adaptive Spectral Heuristic for Partitioning Random Graphs. ICALP (1) 2006: 691-702

Amin Coja-Oghlan, Andreas Goerdt, André Lanka: Spectral Partitioning of Random Graphs with Given Expected Degrees. IFIP TCS 2006: 271-282

Amin Coja-Oghlan: Graph partitioning via adaptive spectral techniques. Electronic Colloquium on Computational Complexity (ECCC) 13(116) (2006)

Amin Coja-Oghlan: The Lovász Number of Random Graphs. Combinatorics, Probability & Computing 14(4): 439-465 (2005)

Amin Coja-Oghlan, Sven Oliver Krumke, Till Nierhoff: A Hard Dial-a-Ride Problem that is Easy on Average. J. Scheduling 8(3): 197-210 (2005)

Amin Coja-Oghlan: A spectral heuristic for bisecting random graphs. SODA 2005: 850-859

Amin Coja-Oghlan, Anusch Taraz: Exact and approximative algorithms for coloring G(n, p). Random Struct. Algorithms 24(3): 259-278 (2004)

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT. Theor. Comput. Sci. 329(1-3): 1-45 (2004)

Amin Coja-Oghlan, Andreas Goerdt, André Lanka: Strong Refutation Heuristics for Random k-SAT. APPROX-RANDOM 2004: 310-321

Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani: Counting Connected Graphs and Hypergraphs via the Probabilistic Method. APPROX-RANDOM 2004: 322-333

Amin Coja-Oghlan: Coloring Semirandom Graphs Optimally. ICALP 2004: 383-395

Amin Coja-Oghlan, Mark-Oliver Stehr: Revisiting the Algebra of Petri Net Processes under the Collective Token Philosophy. Fundam. Inform. 54(2-3): 151-164 (2003)

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich: Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques. FCT 2003: 15-26

Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani: MAX k-CUT and Approximating the Chromatic Number of Random Graphs. ICALP 2003: 200-211

Amin Coja-Oghlan, Sven Oliver Krumke, Till Nierhoff: A Heuristic for the Stacker Crane Problem on Trees Which Is Almost Surely Exact. ISAAC 2003: 605-614

Amin Coja-Oghlan: The Lovász Number of Random Graphs. RANDOM-APPROX 2003: 228-239

Amin Coja-Oghlan, Anusch Taraz: Colouring Random Graphs in Expected Polynomial Time. STACS 2003: 487-498

Amin Coja-Oghlan: Finding Large Independent Sets in Polynomial Expected Time. STACS 2003: 511-522

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich: Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques. Electronic Colloquium on Computational Complexity (ECCC) 10(030) (2003)

Amin Coja-Oghlan: The Lovasz number of random graph. Electronic Colloquium on Computational Complexity (ECCC)(073) (2003)

Amin Coja-Oghlan: Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming. MFCS 2002: 201-211

Amin Coja-Oghlan: Finding Sparse Induced Subgraphs of Semirandom Graphs. RANDOM 2002: 139-148