Source author record

Samuel Hetterich

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms cond-mat.dis-nn math.PR

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Analysing Survey Propagation Guided Decimation on Random Formulas

Let $\varPhi$ be a uniformly distributed random $k$ -SAT formula with $n$ variables and $m$ clauses. For clauses/variables ratio $m/n \leq r_{k\text{-SAT}} \sim 2^k\ln2$ the formula $\varPhi$ is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond $m/n \sim 2k \ln(k)/k$ with a non-vanishing probability. Non-rigorous statistical mechanics work on $k$ -CNF led to the development of a new efficient "message passing algorithm" called \emph{Survey Propagation Guided Decimation} [Mézard et al., Science 2002]. Experiments conducted for $k=3,4,5$ suggest that the algorithm finds satisfying assignments close to $r_{k\text{-SAT}}$ . However, in the present paper we prove that the basic version of Survey Propagation Guided Decimation fails to solve random $k$ -SAT formulas efficiently already for $m/n=2^k(1+\varepsilon_k)\ln(k)/k$ with $\lim_{k\to\infty}\varepsilon_k= 0$ almost a factor $k$ below $r_{k\text{-SAT}}$ .

preprint2016arXiv

On universal hypergraphs

A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$ -uniform hypergraphs with maximum vertex degree bounded by $Δ$ and at most $n$ vertices any universal hypergraph has to contain $Ω(n^{r-r/Δ})$ many edges. We exploit constructions of Alon and Capalbo to obtain universal $r$ -uniform hypergraphs with the optimal number of edges $O(n^{r-r/Δ})$ when $r$ is even, $r \mid Δ$ or $Δ=2$ . Further we generalize the result of Alon and Asodi about optimal universal graphs for the family of graphs with at most $m$ edges and no isolated vertices to hypergraphs.

preprint2014arXiv

Local Algorithms for Graphs

We are going to analyze local algorithms over sparse random graphs. These algorithms are based on local information where local regards to a decision made by the exploration of a small neighbourhood of a certain vertex plus a believe of the structure of the whole graph and maybe added some randomness. This kind of algorithms can be a natural response to the given problem or an efficient approximation such as the Belief Propagation Algorithm.

preprint2013arXiv

On the chromatic number of random regular graphs

Let G(n,d) be the random d-regular graph on n vertices. For any integer k exceeding a certain constant k_0 we identify a number d_{k-col} such that G(n,d) is k-colorable w.h.p. if d<d_{k-col} and non-k-colorable w.h.p. if d>d_{k-col}.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.