Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExplicit Expanding Expanders
212
0
0.0
(
0
)
Added by
Michael Dinitz
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are close to each other. We study the following question: Construct an an infinite sequence of expanders $G_0,G_1,dots$, such that for every two consecutive graphs $G_i$ and $G_{i+1}$, $G_{i+1}$ can be obtained from $G_i$ by adding a single vertex and inserting/removing a small number of edges, which we call the expansion cost of transitioning from $G_i$ to $G_{i+1}$. This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of $d$-regular expanders with expansion cost at most $5d/2$, for any $dgeq 6$. Our construction leverages the notion of a 2-lift of a graph. This operation was first analyzed by Bilu and Linial, who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to interpolate between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout. While our main motivation is centralized (datacenter networks), we also get the best-known distributed expander construction in the self-healing model.
rate research
Read More
We present an elementary way to transform an expander graph into a simplicial complex where all high order random walks have a constant spectral gap, i.e., they converge rapidly to the stationary distribution. As an upshot, we obtain new constructions, as well as a natural probabilistic model to sample constant degree high-dimensional expanders. In particular, we show that given an expander graph $G$, adding self loops to $G$ and taking the tensor product of the modified graph with a high-dimensional expander produces a new high-dimensional expander. Our proof of rapid mixing of high order random walks is based on the decomposable Markov chains framework introduced by Jerrum et al.
In this paper we study expander graphs and their minors. Specifically, we attempt to answer the following question: what is the largest function $f(n,alpha,d)$, such that every $n$-vertex $alpha$-expander with maximum vertex degree at most $d$ contains {bf every} graph $H$ with at most $f(n,alpha,d)$ edges and vertices as a minor? Our main result is that there is some universal constant $c$, such that $f(n,alpha,d)geq frac{n}{clog n}cdot left(frac{alpha}{d}right )^c$. This bound achieves a tight dependence on $n$: it is well known that there are bounded-degree $n$-vertex expanders, that do not contain any grid with $Omega(n/log n)$ vertices and edges as a minor. The best previous result showed that $f(n,alpha,d) geq Omega(n/log^{kappa}n)$, where $kappa$ depends on both $alpha$ and $d$. Additionally, we provide a randomized algorithm, that, given an $n$-vertex $alpha$-expander with maximum vertex degree at most $d$, and another graph $H$ containing at most $frac{n}{clog n}cdot left(frac{alpha}{d}right )^c$ vertices and edges, with high probability finds a model of $H$ in $G$, in time poly$(n)cdot (d/alpha)^{Oleft( log(d/alpha) right)}$. We note that similar but stronger results were independently obtained by Krivelevich and Nenadov: they show that $f(n,alpha,d)=Omega left(frac{nalpha^2}{d^2log n} right)$, and provide an efficient algorithm, that, given an $n$-vertex $alpha$-expander of maximum vertex degree at most $d$, and a graph $H$ with $Oleft( frac{nalpha^2}{d^2log n} right)$ vertices and edges, finds a model of $H$ in $G$. Finally, we observe that expanders are the `most minor-rich family of graphs in the following sense: for every $n$-vertex and $m$-edge graph $G$, there exists a graph $H$ with $O left( frac{n+m}{log n} right)$ vertices and edges, such that $H$ is not a minor of $G$.
We construct an explicit family of 3XOR instances which is hard for $O(sqrt{log n})$ levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time. Our construction is based on the high-dimensional expanders devised by Lubotzky, Samuels and Vishne, known as LSV complexes or Ramanujan complexes, and our analysis is based on two notions of expansion for these complexes: cosystolic expansion, and a local isoperimetric inequality due to Gromov. Our construction offers an interesting contrast to the recent work of Alev, Jeronimo and the last author~(FOCS 2019). They showed that 3XOR instances in which the variables correspond to vertices in a high-dimensional expander are easy to solve. In contrast, in our instances the variables correspond to the edges of the complex.
In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a $(1-varepsilon)$-satisfiable instance of Unique Games with the constraint graph $G$, our algorithm finds an assignment satisfying at least a $1- C varepsilon/h_G$ fraction of all constraints if $varepsilon < c lambda_G$ where $h_G$ is the edge expansion of $G$, $lambda_G$ is the second smallest eigenvalue of the Laplacian of $G$, and $C$ and $c$ are some absolute constants.
We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this definition, we describe an analogue of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analogue is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expander can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing only $|X(k-1)|=O(n)$ points in contrast to $binom{n}{k}$ points in the $(k)$-slice (which consists of all $n$-bit strings with exactly $k$ ones). Our random-walk definition and the decomposition has the additional advantage that they extend to the more general setting of posets, which include both high-dimensional expanders and the Grassmann poset, which appears in recent works on the unique games conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
