7
votes
Geometric picture behind quantum expanders
[This answer was copied from my answer on the now-defunct theoreticalphysics stackexchange site.]
For classical expanders, the spectral definition can be expressed in terms of the second-smallest ...
- 1,030
6
votes
Accepted
Dichotomy of the spectra of directed graphs
The answer to “alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component” is YES (though I don’t understand what is “alternative” about this statement, as ...
- 16.9k
6
votes
Accepted
How is SDP an extension of spectral algorithms?
This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the ...
- 18.1k
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
1
vote
Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?
Without any further constraints, this expression will in general be unbounded, so the maximum won't exist.
Let $V$ be $\{v_1,\ldots,v_n\}$ with $n\ge 2$. Pick $i\neq j$ such that $v_i,v_j$ are not ...
- 2,500
1
vote
Entries of the Inverse Laplacian
I originally wanted to pose the question, but then I started investigating and found a few very helpful interpretation that haven't been collected anywhere (to my knowledge). Hence, I will write my ...
- 141
1
vote
Spectral sparsification of graphs with negative edge weights
I personally do not work in spectral graph theory. I write this from a linear algebra perspective.
This definition seems to apply naturally to graphs which are permitted to have negative edge weights
...
- 111
1
vote
Accepted
When can partial spectral sparsifiers be combined?
Regarding your 1st question: no, this would not hold in general.
Rather (answering your 2nd question), the right way to interpret the approach by Spielman and Teng is as follows: let $G'$ be a vertex-...
- 849
1
vote
Accepted
Fast Computation of First k Eigenvectors of Graph Laplacian
Answer to Q1:
In [1], it is argued at the end of section 1 that the first k eigenvectors can be approximated in time roughly $O(mk)$ (up to log-factors), with $m$ the number of edges. They are not ...
- 849
1
vote
Dichotomy of the spectra of directed graphs
I feel like the bounds will very strongly depend on the particular connectivity structure of the graph.
One example would be a one-way cycle of length $N$. With the correct ordering, it's not hard ...
- 319
1
vote
Making an adjacency matrix positive semidefinite
This is simple. Assume the adjacency matrix is $A$. As it is symmetric, it guarantees that $A$ can be diagonalized as $A=U\Sigma U^T$ by SVD decomposition, where $\Sigma=diag(\lambda_1,...,\lambda_n)$ ...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible