19
votes
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 ...
- 306
9
votes
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
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.
...
- 4,451
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.
- 397
4
votes
About some possible optimality properties of Ramanujan graphs
At least among regular bi-partite graphs, Ramanujan graphs provide the optimal approximation of the complete bipartite graph. Let's say that a graph $H$ $C$-approximates a graph $G$ if $tL_H \preceq ...
- 18.1k
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 ...
- 2,393
4
votes
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 ...
- 50.9k
4
votes
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.3k
3
votes
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
2
votes
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 ...
- 824
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 ...
- 41
2
votes
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.3k
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