Skip to main content
Share Your Experience: Take the 2024 Developer Survey
19 votes

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 ...
Scott Aaronson's user avatar
9 votes

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 ...
Adam Smith's user avatar
8 votes

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. ...
Clement C.'s user avatar
  • 4,471
5 votes

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.
A.2's user avatar
  • 397
4 votes

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 ...
GMB's user avatar
  • 2,403
4 votes

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 ...
David Eppstein's user avatar
4 votes

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 I cannot say why people use zig-zag instead, other than ...
Ryan Williams's user avatar
3 votes

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. ...
guest's user avatar
  • 96
2 votes

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 ...
Arnaud's user avatar
  • 834
2 votes

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 ...
loplo's user avatar
  • 41
2 votes

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 ...
Yuval Filmus's user avatar
  • 14.5k
1 vote

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) ...
smapers's user avatar
  • 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.
Thatchaphol's user avatar
  • 1,130

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