Source author record

Roee David

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

ResearcherUnclaimed source record

Discrete Mathematics Computational Complexity Data Structures and Algorithms math.PR

Catalog footprint

Research overview

2works

4topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On the effect of randomness on planted 3-coloring models

We present the hosted coloring framework for studying algorithmic and hardness results for the $k$ -coloring problem. There is a class ${\cal H}$ of host graphs. One selects a graph $H\in{\cal H}$ and plants in it a balanced $k$ -coloring (by partitioning the vertex set into $k$ roughly equal parts, and removing all edges within each part). The resulting graph $G$ is given as input to a polynomial time algorithm that needs to $k$ -color $G$ (any legal $k$ -coloring would do -- the algorithm is not required to recover the planted $k$ -coloring). Earlier planted models correspond to the case that ${\cal H}$ is the class of all $n$ -vertex $d$ -regular graphs, a member $H\in{\cal H}$ is chosen at random, and then a balanced $k$ -coloring is planted at random. Blum and Spencer [1995] designed algorithms for this model when $d=n^δ$ (for $0<δ\le1$ ), and Alon and Kahale [1997] managed to do so even when $d$ is a sufficiently large constant. The new aspect in our framework is that it need not involve randomness. In one model within the framework (with $k=3$ ) $H$ is a $d$ regular spectral expander (meaning that except for the largest eigenvalue of its adjacency matrix, every other eigenvalue has absolute value much smaller than $d$ ) chosen by an adversary, and the planted 3-coloring is random. We show that the 3-coloring algorithm of Alon and Kahale [1997] can be modified to apply to this case. In another model $H$ is a random $d$ -regular graph but the planted balanced $3$ -coloring is chosen by an adversary, after seeing $H$ . We show that for a certain range of average degrees somewhat below $\sqrt{n}$ , finding a 3-coloring is NP-hard. Together these results (and other results that we have) help clarify which aspects of randomness in the planted coloring model are the key to successful 3-coloring algorithms.

preprint2016arXiv

Random walks with the minimum degree local rule have $O(n^2)$ cover time

For a simple (unbiased) random walk on a connected graph with $n$ vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most $O(n^3)$ . We consider locally biased random walks, in which the probability of traversing an edge depends on the degrees of its endpoints. We confirm a conjecture of Abdullah, Cooper and Draief [2015] that the min-degree local bias rule ensures a cover time of $O(n^2)$ . For this we formulate and prove the following lemma about spanning trees. Let $R(e)$ denote for edge $e$ the minimum degree among its two endpoints. We say that a weight function $W$ for the edges is feasible if it is nonnegative, dominated by $R$ (for every edge $W(e) \le R(e)$ ) and the sum over all edges of the ratios $W(e)/R(e)$ equals $n-1$ . For example, in trees $W(e) = R(e)$ , and in regular graphs the sum of edge weights is $d(n-1)$ . {\bf Lemma:} for every feasible $W$ , the minimum weight spanning tree has total weight $O(n)$ . For regular graphs, a similar lemma was proved by Kahn, Linial, Nisan and Saks [1989].

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.

Roee David

Research overview

Is this your work?

2 publications

On the effect of randomness on planted 3-coloring models

Random walks with the minimum degree local rule have $O(n^2)$ cover time

See the researcher in context

Building this map preview

Roee David

Research overview

Is this your work?

2 publications

On the effect of randomness on planted 3-coloring models

Random walks with the minimum degree local rule have O(n2)O(n^2)O(n2) cover time

See the researcher in context

Building this map preview

Random walks with the minimum degree local rule have $O(n^2)$ cover time