Amin Coja-Oghlan | DeepAI

DeepAI AI Chat

Featured Co-authors

Alexander S. Wein
33 publications
Ilias Zadik
29 publications
Leslie Ann Goldberg
29 publications
Avrim Blum
28 publications
Daniel Stefankovic
25 publications
Eric Vigoda
24 publications
Andreas Galanis
23 publications
Dominik Kaaser
18 publications
Max Hahn-Klimroth
18 publications
Shuheng Zhou
17 publications
Alan Frieze
14 publications

∙ 01/23/2023

The k-XORSAT threshold revisited

We provide a simplified proof of the random k-XORSAT satisfiability thre...

0 Amin Coja-Oghlan, et al. ∙

∙ 06/15/2022

Statistical and Computational Phase Transitions in Group Testing

We study the group testing problem where the goal is to identify a set o...

0 Amin Coja-Oghlan, et al. ∙

∙ 05/17/2022

On the Hierarchy of Distributed Majority Protocols

We study the Consensus problem among n agents, defined as follows. Initi...

0 Petra Berenbrink, et al. ∙

∙ 02/11/2022

Metastability of the Potts ferromagnet on random regular graphs

We study the performance of Markov chains for the q-state ferromagnetic ...

0 Amin Coja-Oghlan, et al. ∙

∙ 12/28/2021

The full rank condition for sparse random matrices

We derive a sufficient condition for a sparse random matrix with given n...

0 Amin Coja-Oghlan, et al. ∙

∙ 11/04/2020

Belief Propagation on the random k-SAT model

Corroborating a prediction from statistical physics, we prove that the B...

0 Amin Coja-Oghlan, et al. ∙

∙ 09/22/2020

The Ising antiferromagnet and max cut on random regular graphs

The Ising antiferromagnet is an important statistical physics model with...

0 Amin Coja-Oghlan, et al. ∙

∙ 07/15/2020

Inference and mutual information on random factor graphs

Random factor graphs provide a powerful framework for the study of infer...

0 Amin Coja-Oghlan, et al. ∙

∙ 02/10/2020

The random 2-SAT partition function

We show that throughout the satisfiable phase the normalised number of s...

0 Dimitris Achlioptas, et al. ∙

∙ 11/06/2019

Optimal non-adaptive group testing

In non-adaptive group testing we aim to identify a small set of k∼ n^θ i...

0 Amin Coja-Oghlan, et al. ∙

∙ 06/13/2019

The rank of sparse random matrices

Generalising prior work on the rank of random matrices over finite field...

0 Amin Coja-Oghlan, et al. ∙

∙ 05/31/2019

The cut metric for probability distributions

Guided by the theory of graph limits, we investigate a variant of the cu...

0 Amin Coja-Oghlan, et al. ∙

∙ 02/06/2019

Information-theoretic and algorithmic thresholds for group testing

In the group testing problem we aim to identify a small number of infect...

0 Amin Coja-Oghlan, et al. ∙

∙ 12/23/2018

Lower bounds on the chromatic number of random graphs

We prove that a formula predicted on the basis of non-rigorous physics a...

0 Peter Ayre, et al. ∙

∙ 10/17/2018

The rank of random matrices over finite fields

We determine the rank of a random matrix A over a finite field with pres...

0 Amin Coja-Oghlan, et al. ∙

∙ 02/26/2018

The replica symmetric phase of random constraint satisfaction problems

Random constraint satisfaction problems play an important role in comput...

0 Amin Coja-Oghlan, et al. ∙

∙ 10/20/2017

The satisfiability threshold for random linear equations

Let A be a random m× n matrix over the finite field F_q with precisely k...

0 Peter Ayre, et al. ∙

∙ 06/25/2007

Separating populations with wide data: A spectral analysis

In this paper, we consider the problem of partitioning a small data samp...

0 Avrim Blum, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world