# Tag Info

## Hot answers tagged expanders

Accepted

### What are the obstructions to extending $L=SL$ to $L=NL$?

The central problem is that, on directed graphs, even a truly random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk. The standard counterexample here is ...
Accepted

### Are social networks typically good expanders?

Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap. What you could hope for is good ...
• 878

### reference request for construction of expanders

You can look at this survey by Hoory, Linial, and Wigderson [1]. Chapter 9, specifically (p. 508) is on the zigzag product. ...
• 4,481

### reference request for construction of expanders

Here are some additional notes: lecture notes by Dieter van Melkebeek , notes from Luca Trevisan's course on expanders.
• 397

### Regularity Lemma for Sparse Graphs

Below is a long-winded answer, but tl;dr in the general case there is no hope for such a formulation, but for many of the particular classes of sparse graphs that have regularity lemmas this ...
• 2,403
Accepted

### Existence of $d$-regular expander graph that can be represented as a bipartite graph

The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the bipartite double cover, which preserves regularity. But it might not preserve expansion; in ...
• 51.1k
Accepted

### Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

There is a paper already in 2005 that describes how to do this... See https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html I cannot say why people use zig-zag instead, other than ...
• 27.5k
Accepted

### Deterministic error reduction, state-of-the-art?

Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions. ...
• 96
Accepted

### Expander Graph from Hypergraph

This is not an answer but is too long for a comment: The graph you care about is called the line graph of the hypergraph. For usual graphs, it is well known that the line graph of an expander graph ...
• 834

### Are all linear-rate and -distance classical linear codes expanding?

Really cool question! This is a little bit on the handwavy side of things, but here is my take. The conclusion is that we can show the existence of an $\Omega(1)$-expander of size $\Theta(n)$, let me ...
• 41
Accepted

### High-dimensional expanders through the lens of algebraic topology

High-dimensional expanders come in several flavors. The most common ones in TCS are spectral expanders, coboundary expanders, and cosystolic expanders. The latter two are defined using the algebraic ...
• 14.5k
1 vote
Accepted

### Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

Yes! But I can see why it is confusing. A strongly explicit graph family $\{G_n = (V_n,E_n)\}$ (parameterized e.g. by number of vertices $n$) is described by an efficient ($\mathrm{polylog}(n)$ time) ...
• 849
1 vote

### Are social networks typically good expanders?

Power-law graphs are arguably good models for social network graphs. This paper by Gkantsidis, Mihail, and Saberi shows that power-law graphs are expanders.
• 1,130

Only top scored, non community-wiki answers of a minimum length are eligible