Twenty years ago, Bobkov, Houdr\'e, and the last author introduced a Poincar\'e-type functional graph parameter, \lambda_\infty (G) , of a graph G , and related it to the {\em vertex expansion} of G via a Cheeger-type inequality . This is analogous to the Cheeger-type inequality relating the spectral gap  , \lambda_2 (G), of the graph to its {\em edge expansion}. While \lambda_2 can be computed efficiently, the computational complexity of \lambda_\infty has remained an open question. Following the work of the second author with Raghavendra and Vempala, wherein the complexity of \lambda_\infty was related to the so-called Small-Set Expansion (SSE) problem, it has been believed that computing \lambda_\infty is a hard problem. We settle this question by proving that computing \lambda_\infty is indeed NP-hard . Additionally, we use our techniques to prove NP-hardness of computing the spread constant (of a graph) \emph{  , a geometric measure  introduced by Alon, Boppana, and Spencer, in the context of deriving an asymptotic isoperimetric inequality on cartesian products of graphs. We complement our hardness results by providing approximation schemes for computing \lambda_\infty and the spread constant of star graphs, and investigate constant approximability for weighted trees. Finally{\em   , we provide improved approximation results for the maximum variance embedding problem for general graphs, by replacing the optimal orthogonal projection (PCA) with a randomized projection approach .
 Bobkov, Houdr\'e, and the last author introduced a Poincar\'e-type functional parameter, \lambda_\infty , of a graph G . They related \lambda_\infty to the {\em vertex expansion} of the graph via a Cheeger-type inequality , analogous to the inequality relating the spectral gap of the graph , \lambda_2 , to its {\em edge expansion}. While \lambda_2 can be computed efficiently, the computational complexity of \lambda_\infty has remained an open question. Following the work of the second author with Raghavendra and Vempala, wherein the complexity of \lambda_\infty was related to the so-called small-set expansion (SSE) problem, it has been believed that computing \lambda_\infty is a hard problem. We confirm this conjecture by proving that computing \lambda_\infty is indeed NP-hard , even for weighted trees. Our gadget further proves NP-hardness of computing \emph{spread constant of a weighted tree; i.e. , a geometric measure of the graph, introduced by Alon, Boppana, and Spencer, in the context of deriving an asymptotic isoperimetric inequality of Cartesian products of graphs. We conclude this case by providing a fully polynomial time approximation scheme. We further study a generalization of spread constant in machine learning literature, namely the{\em maximum variance embedding problem. For trees , we provide fast combinatorial algorithms that avoid solving a semidefinite relaxation of the problem. On the other hand, for general graphs, we propose a randomized projection method that can outperform the optimal orthogonal projection , i.e., PCA, classically used for rounding of the optimum lifted solution (to SDP relaxation) of the problem .
D
Twenty years ago,
D
graph
D
(G)
R
, and related it
. They related \lambda_\infty
R
G
the graph
R
. This is
,
D
Cheeger-type
A
of the graph
R
(G), of the graph
,
R
Small-Set Expansion
small-set expansion
R
settle this question
confirm this conjecture
R
. Additionally, we use our techniques to prove
, even for weighted trees. Our gadget further proves
D
the spread constant (of a graph)
A
spread constant
A
of a weighted tree; i.e.
A
of the graph,
R
on cartesian
of Cartesian
R
complement our hardness results by providing approximation schemes for computing \lambda_\infty and the spread constant of star graphs, and investigate constant approximability for weighted trees. Finally
conclude this case by providing a fully polynomial time approximation scheme. We further study a generalization of spread constant in machine learning literature, namely the
A
maximum variance embedding
A
problem. For trees
R
improved approximation results for the maximum variance embedding problem
fast combinatorial algorithms that avoid solving a semidefinite relaxation of the problem. On the other hand,
R
by replacing
we propose a randomized projection method that can outperform
R
(PCA) with a randomized projection approach
, i.e., PCA, classically used for rounding of the optimum lifted solution (to SDP relaxation) of the problem