Every graph $G$ can be represented by a collection of equi-radii spheres in a $d$-dimensional metric $\Delta$ such that there is an edge $uv$ in $G$ if and only if the spheres corresponding to $u$ and $v$ intersect. The smallest integer $d$ such that $G$ can be represented by a collection of spheres (all of the same radius) in $\Delta$ is called the sphericity of $G$, and if the collection of spheres are nonoverlapping, then the value $d$ is called the contact-dimension of $G$. In this paper, we study the sphericity and contact-dimension of the complete bipartite graph $K_{n,n}$ in various $L^p$-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.

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)$. We will show in a lemma that for every feasible $W$, the minimum weight spanning tree has total weight $O(n)$. For regular graphs, a similar lemma was proved by Kahn et al. (1989).

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(n3). 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(n2). 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) < 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). 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].

The $k$-fold direct sum encoding of a string $a \in \{0,1\}^n$ is a function $f_a$ that takes as input sets $S \subseteq [n]$ of size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i \pmod 2$. In this paper we prove a direct sum testing theorem. We describe a three query test that accepts with probability one any function of the form $f_a$ for some $a$ and rejects with probability $\Omega(\varepsilon)$ functions $f$ that are $\varepsilon$-far from being a direct sum encoding, where the constant behind the $\Omega$ notation is independent of $k$. This theorem has a couple of additional guises: Linearity testing: By identifying the subsets of $[n]$ with vectors in $\{0,1\}^n$ in the natural way, our result can be thought of as a linearity testing theorem for functions whose domain is restricted to the $k$th layer of the hypercube (i.e., the set of $n$-bit strings with Hamming weight $k$). Tensor power testing: By moving to $-1,1$ notation, the direct sum encoding is equivalent (up to a difference thatis negligible when $k\ll \sqrt n$) to a tensor power. Thus our theorem implies a three query test for deciding if a given tensor $f\in \{-1,1\}^{n^k}$ is a tensor power of a single dimensional vector $a\in \{-1,1\}^n$, i.e., whether there is some $a$ such that $f = a^{\otimes k}$. We also provide a four query test for checking if a given $\pm 1$ matrix has rank $1$. Our test naturally extends the linearity test of Blum, Luby, and Rubinfeld [ J. Comput. Syst. Sci., 47 (1993), pp. 549--595]. Our analysis proceeds by first handling the $k=n/2$ case and then reducing this case to the general $k

We present the hosted coloring framework for studying al- gorithmic and hardness results for the k-coloring problem. There is a class H of host graphs. One selects a graph H ∈ 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 H is the class of all n-vertex d-regular graphs, a member H ∈ 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 < δ ≤ 1), 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 in- volve randomness. In one model within the framework (with k = 3) H is a d regular spectral expander (meaning that ex- cept 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 ran- dom. We show that the 3-coloring algorithm of Alon and Kahale [1997] can be modified to apply to this case. In an- other 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 √ n, finding a 3-coloring is NP-hard. To- gether 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.

The k-fold direct sum encoding of a string α ∈ --0,1}n is a function fα that takes as input sets S ⊆ [n] of size k and outputs fα (S) = ∑i ∈ S αi (mod 2. In this paper we prove a Direct Sum Testing theorem. We describe a three query test that accepts with probability one any function of the form fα for some α, and rejects with probability Ω(ε) functions f that are ε being a direct sum encoding.