Title: Courses / CS 530

Q: Law of Large Numbers
A: Let \(X_1,X_2,\dots, X_n\) be a sequence of independent and identically distributed random variables with \(\mathbb{E}[X_i] = \mu\). Then if \(\overline{X_n} = \frac{1}{n}\sum_{i=1}^n X_i\) is the sample mean, \(\overline{X_n} \to \mu\) as \(n \to \infty\).
There are two ways to state this convergence. One is the weak law, which is the only one you need to know. This says that for all \(\epsilon > 0\), \(\lim_{n \to \infty} \mathbb{P}[|\overline{X_n}-\mu| > \epsilon] = 0\).
------
In case you're curious, the other is the strong law, which is in fact slightly different. It can be stated \(\mathbb{P}[\lim_{n \to\infty} \overline{X_n} = \mu] = 1\). This means that the probability that the sequence of random variables obtained converges to \(\mu\) is 1. There can be some sequences that do not converge, for example the sequence \(0,0,0,\dots\) for independent Bernoullis with success probabablity great than 1, but the strong law says the probability of obtaining such a sequence is 0.
The weak law does not preclude the possibility that every realization of the sequence \(X_1,X_2,\dots\) you obtain does not have \(\mu\) as a limit: it could jump up to values much larger than \(\mu\) infinitely many times. The strong law says that with probability 1 this does not occur.

Q: Markov's Inequality
A: Given a non-negative random variable \(X\), we have \(\mathbb{P}[X \ge k] \le \frac{\mathbb{E}[X]}{k}\).
Another slightly more memorable way to write this is \(\mathbb{P}[X \ge k \cdot \mathbb{E}[X]] \le \frac{1}{k}\), or in words, the probability a non-negative random variable is at least \(k\) times its expectation is at most \(\frac{1}{k}\).

Q: Chebyshev's Inequality
A: Given a random variable \(X\), \(\mathbb{P}[|X - \mathbb{E}[X]| \ge k] \le \frac{\text{Var}(X)}{k^2}\). Unlike Markov, \(X\) does not have to be non-negative.
 A slightly easier version to remember: \(\mathbb{P}[|X-\mathbb{E}[X]| \ge k\cdot \sigma] \le \frac{1}{k^2}\), where \(\sigma\) is the standard deviation of \(k\). In words: the probability \(X\) is more than \(k\) standard deviations away from its mean is at most \(\frac{1}{k^2}\).

Q: Hoeffding's Inequality
A: Let \(X_1,\dots,X_n\) be independent random variables so that for all \(i\), we have \(a_i \le X_i \le b_i\) with probability 1. Let \(X=\sum_{i=1}^n X_i\). Then, \[\mathbb{P}[X - \mathbb{E}[X] \ge t] \le e^{-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}}\]So, we have
\[\mathbb{P}[|X - \mathbb{E}[X]| \ge t] \le 2e^{-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}}\]

Q: Apply Hoeffding to figure out the probability a poll of 1000 people is more than 5% off in its estimate. Then specify the rule of thumb for picking a sample size to get within a certain error.
A: Here \(a_i=0,b_i=1\) since the variables are binary. Now we just plug everything in, where \(\mu\) is the true expected value.
\(\mathbb{P}[|X-\mu| \ge 50] \le 2e^{-\frac{2 \cdot 50^2}{1000}} = 2e^{-5} \approx 0.013\)
so we are within 5% additive error with probability around 99%.
A good rule of thumb is that if you have \(n\) independent binary random variables, you should expect an error on the estimate of the expected value of around \(\frac{1}{\sqrt{n}}\) percent. So, to get an error of 5%, compute \(\frac{1}{\sqrt{n}} = 0.05\), or \(\sqrt{n}=20, n=400\), then make \(n\) a bit bigger, which is why \(n=500\) sufficed. In general it's good to triple the value you get, but for large deviation (5% is large), it's OK to just make it a little bigger.
------
(Note that using Chernoff bounds can help give tighter results for when the \(\mathbb{E}[X_i]\) is closer to 0 or 1, but this is the best you can do when the expected value is around 0.5.)

Q: Expected Value and Linearity of Expectation
A: For a discrete random variable \(X\),
\[\mathbb{E}[X] = \sum_{\omega \in \Omega} X(\omega) \cdot \mathbb{P}(\omega)\]Alternatively, \(\mathbb{E}[X] = \sum_{x \in R_X} x \cdot \mathbb{P}[X=x]\), where \(R_X\) is the range of \(X\). This is often more useful.
For a continuous random variable with probability density function \(f\),
\[\mathbb{E}[X] = \int_{-\infty}^\infty x \cdot f(x) dx\]Linearity of expectation means that for any variables \(X_1,\dots,X_n\), we have
\[\mathbb{E}[\sum_{i=1}^n X_i] = \sum_{i=1}^n \mathbb{E}[X]\]

Q: Variance and Variance Properties
A: The variance of a random variable \(X\) is \(\mathbb{E}[(X-\mathbb{E}[X])^2]\). This is also equal to the often more convenient expression \(\mathbb{E}[X^2] - \mathbb{E}[X]^2\).
We have \(\text{Var}(\sum_{i=1}^n X_i) = \sum_{i=1}^n \text{Var}(X_i)\) if \(X_1,\dots,X_n\) are pairwise independent. Also, \(\text{Var}(aX+b) = a^2\text{Var}(X)\) for \(a,b \in \mathbb{R}\).

Q: Definition of Approximation Algorithm
A: An \(\alpha\)-approximation for an optimization problem is a polynomial time algorithm which produces a solution of cost within a factor of \(\alpha\) of the optimal solution for every instance.
A randomized \(\alpha\)-approximation instead produces a solution of expected cost within a factor of \(\alpha\) for every input.

Q: PTAS, FPTAS, and APX
A: A polynomial time approximation scheme (PTAS) is a (\(1+\epsilon)\)-approximation for a problem that runs in polynomial time for every fixed \(\epsilon>0\). For example, a PTAS could run in time \(n^{1/\epsilon}\).
A fully polynomial time approximation schme (FPTAS) is a \((1+\epsilon)\)-approximation for a problem that runs in time polynomial in the input size and \(\frac{1}{\epsilon}\). For example, \(\frac{n^3}{\epsilon}\).
For maximization problems the \(1+\epsilon\) would be replaced with \(1-\epsilon\).
A problem is in APX ("approximable") if it has a constant-factor approximation algorithm. A problem is APX-Hard if it has no PTAS unless P=NP.

Q: Metric space
A: A metric space \(M,d\) is defined by a set of elements \(M\) with a metric \(d: M \times M \to \mathbb{R}_{\ge 0}\) with the following four properties:
1. \(d(x,x) = 0\) for all \(x \in M\): all points have distance 0 to themselves
2. If \(x \not= y\) then \(d(x,y) > 0\) (although this can be made arbitrarily small so often we allow a distance of 0)
3. \(d(x,y) = d(y,x)\) for all \(x,y \in M\)
4. \(d\) obeys the triangle inequality: \(d(x,z) \le d(x,y) + d(y,z)\) for all \(x,y,z \in M\).
A standard example of a metric space is Euclidean space, where points are tuples \((x_1,x_2) \in \mathbb{R}^2\) and \(d((x_1,x_2),(y_1,y_2)) = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2}\).

Q: Psuedopolynomial time
A: An algorithm runs in pseudopolynomial time if it runs in polynomial time in the input size when the numbers in the input are encoded in unary.

Q: Christofides' Algorithm for Metric TSP
A: As discussed in class, it's enough to find a multi-set of edges that connects the graph and has even degree at every vertex, as this edge set can always be "shortcut" to a Hamiltonian cycle of no greater cost.
Find a minimum spanning tree \(T\) of the graph: this gives connectivity. Then, compute the minimum cost perfect matching on the nodes with odd degree in \(T\): this makes all the vertices even degree.
This is a \(\frac{3}{2}\) approximation.

Q: Integrality Gap
A: The integrality gap of an ILP and its associated LP is the worst case ratio between the ILP OPT and the LP OPT over all instances.

Q: Integer Linear Program and Linear Program Relaxation
A: An Integer Linear Program (ILP) minimizes a linear objective function over a convex polyhedron \(P\). The variables are constrained to be integers. \[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{Z}_{\ge 0}^n \end{align*}\]If we instead only constrain the variables to be real numbers, we get a Linear Program (LP):\[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{R}_{\ge 0}^n \end{align*}\]Note we can flip min to max by negating the entries of \(c\), so these programs are fully general.
A natural extension is convex programs. Here we only need the feasible region to be a convex set and the objective function to be convex.

Q: Polyhedron and polytope and their matrix form
A: A polyhedron is the intersection of a finite number of halfspaces. A polytope is a bounded polyhedron.
We will typically write a polyhedron as the set of points \(x \in \mathbb{R}^n\) obeying the equations \(Ax \ge b\) for some matrix \(A \in \mathbb{R}^{m \times n}\) and vector \(b \in \mathbb{R}^m\). Each row of \(A\) represents one of the halfspaces of the polyhedron.

Q: Convex set
A: A set \(S \subseteq \mathbb{R}^d\) is convex if for any two points \(a,b \in S\) and any \(\alpha \in [0,1]\), the point \(\alpha a + (1-\alpha)b\) also lies in \(S\).
In this class, the primary example of a convex set will be a polyhedron: the intersection of finitely many half-spaces.

Q: Linear algebraic view of a vertex of a polyhedron
A: If \(v\) is a vertex of a polyhedron in \(n\) dimensions defined by half-spaces \(Ax \ge b\), then there is a matrix \(\tilde{A}\) consisting of \(n\) linearly independent rows of \(A\) so that \(v\) is the unique solution to the equation system \(\tilde{A}x = \tilde{b}\).
It is useful to notice that the subset of rows picked in \(\tilde{A}\) must be tight constraints.

Q: Relax and round framework
A: Start with an ILP whose feasible solutions are the feasible solutions for your optimization problem. Make sure the linear constraints of the ILP have a poly-time separation oracle. Then, relax the ILP to an LP, which is polynomial time solvable by the ellipsoid method. After solving this LP, round the resulting solution to a feasible integer solution, ideally without losing too much in cost (or whatever measure is of interest).
This can also be applied for more general convex programs.

Q: Ellipsoid method and separation oracle
A: Let \(P\) be a convex set. A separation oracle for \(P\) is a polynomial time procedure that given a point \(x \in \mathbb{R}^n\), either certifies that \(x \in P\) or returns a hyperplane that separates \(x\) from \(P\). In other words, it returns a vector \(a \in \mathbb{R}^n\) such that \(a^Tx > a^Ty\) for all \(y \in P\).
The ellipsoid method is a polynomial time algorithm that can optimize over any convex set with a separation oracle. (In other words, it can solve any LP whose feasible region is convex and has a separation oracle.)
In this course, \(P\) will typically be a convex polyhedron defined by a (possibly exponential size) collection of hyperplanes, and our separation oracle will return one of these hyperplanes.

Q: Minimum spanning tree
A: Given a graph \(G=(V,E)\) with weights \(w_e\) on the edges, a minimum spanning tree \(T\) is a spanning tree the the smallest possible weight \(\sum_{e \in T} w_e\).
A minimum spanning tree (MST) can be found using a greedy procedure called Kruskal's algorithm: keep adding the edge with the smallest weight to your MST as long as it does not create a cycle. Stop when every edge creates a cycle, at which point you must have a spanning tree if the original graph was connected.

Q: Carathéodory's Theorem
A: If \(x \in \mathbb{R}^n\) is a point in a polytope \(P\), then we can write \(x\) as a convex combination of at most \(n+1\) vertices \(v_1,\dots,v_{n+1}\) of \(P\).
In other words, we have \(x = \sum_{i=1}^{n+1} \lambda_i v_i\) where \(\sum_{i=1}^{n+1} \lambda_i = 1\) and \(\lambda_i \ge 0\) for all \(i\).

Q: Convex function
A: A function is convex if its epigraph is a convex set. The epigraph of a function is the set \(\{(a,b) \in X \times \mathbb{R} \mid r \ge f(x)\}\).
Another useful characterization is: a function is convex if its Hessian is positive semi-definite. Remember the Hessian \(\nabla^2\) is the matrix of partial derivatives with \(\nabla^2_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}\).

Q: Rank-Nullity Theorem
A: Given a matrix \(A \in \mathbb{R}^{m \times n}\),
\[\text{rank}(A) + \text{nullity}(A) = n\]where the rank of a matrix is the maximum number of linearly independent rows (or columns) and the nullity is the maximum number of linearly independent vectors \(x\) for which \(Ax=0\) (in other words, the rank of the null space of \(A\)).

Q: PSD Matrix
A: A symmetric matrix \(A \in \mathbb{R}^{n \times n}\) is positive semidefinite, or PSD, if one of three equivalent conditions hold:
(1) \(A\) has no negative eigenvalues
(2) \(x^TAx \ge 0\) for all \(x \in \mathbb{R}^n\)
(3) \(A\) has a square root \(A^{1/2}\) so that \(A^{1/2}(A^{1/2})^T = A\).

Q: Spectral Theorem
A: Given a symmetric matrix \(A\), there are eigenvalues \(\lambda_1,\dots,\lambda_n\) and corresponding orthonormal eigenvectors \(v_1,\dots,v_n\) such that
\[A = \sum_{i=1}^n \lambda_i v_iv_i^T\]Where recall \(v_1,\dots,v_n\) is orthonormal if \(\langle v_i, v_j\rangle = 0\) for \(i \not= j\) and \(\langle v_i, v_i \rangle = 1\).

Q: Eigenvalue and eigenvector
A: An eigenvalue of a matrix \(A\) is a value \(\lambda \in \mathbb{R}\) so that \(Ax = \lambda x\) for some \(x \in \mathbb{R}^n\).
An eigenvector is a vector \(x \in \mathbb{R}^n\) so that there exists some \(\lambda \in \mathbb{R}\) so that \(Ax = \lambda x\).
Therefore we naturally say \(\lambda,x\) form an eigenvalue, eigenvector pair if \(Ax=\lambda x\).

Q: Covariance matrix
A: For a random vector \(x \in \mathbb{R}^n\), the covariance matrix of \(x\) is
\[\mathbb{E}[(x-\mathbb{E}[x])(x-\mathbb{E}[x])^T]\]
If the expected value of \(x\) is the 0 vector, this simplifies to
\[\mathbb{E}[xx^T]\]

Q: Proof that every PSD matrix \(Y\) has a distribution with covariance matrix \(Y\)
A: Let \(r_1,\dots,r_n\) be independent random variables where \(r_i\) mean 0 and variance 1. Then, let \(x=Y^{1/2}r\) be your random vector. Then:
\[\mathbb{E}[xx^T] = \mathbb{E}[Y^{1/2}rr^TY^{1/2}]=Y^{1/2}\mathbb{E}[rr^T]Y^{1/2}=Y\]where we used that \(\mathbb{E}[rr^T] = I\).

Q: Spectral Norm of a Symmetric Matrix
A: Given a symmetric matrix \(A \in \mathbb{R}^{n \times n}\), the spectral norm \(||A||_2\) is the value of the largest eigenvalue in absolute value. In other words \(||A||_2 = \max\{|\lambda_1|,|\lambda_n|\}\).
We also can show:
\[||A||_2 = \max_{x \in \mathbb{R}^n, x \not= 0} \frac{|x^TAx|}{x^Tx}\]so, for all \(x \in \mathbb{R}^n\),
\[|x^TAx| \le ||A||_2 \cdot ||x||_2^2\]

Q: Average Case Analysis
A: In average case analysis, we define a distribution over instances and then design algorithms that work with high probability for a random instance sampled from this distribution.
For example, we showed that Max Cut in the \(G(n,\frac{1}{2})\) model has an average case\(1-o(1)\) approximation. In particular, we showed that there is an algorithm which gets a guarantee of \(1-o(1)\) with probability close to 1 on a graph sampled from \(G(n,\frac{1}{2})\).

Q: Competitive Ratio of an Online Algorithm
A: The competitive ratio of a (possibly randomized) online algorithm is the worst case ratio over all instances of the expected value of the algorithm's performance divided by the value of the offline optimal solution.

Q: Dual of a Linear Program
A: Given a linear program:
\[\begin{align*} \max c^Tx \\ Ax \le b \\ x \in \mathbb{R}_{\ge 0}^n \end{align*}\]
The dual of that program is the result of adding up copies of every constraint in \(A\). For each constraint \(A_ix \le b\), where \(A_i\) is the \(i\)th row of \(A\), we create a variable \(y_i\) indicating that we add \(y_i\) copies of this constraint. This will be one big equation with a righthand side of \(b^Ty\), so to get the best upper bound on the primal, we want to minimize this bound. For it to be a valid bound, we need to have a coefficient of at least \(c\) for every variable in the lefthand side of this equation.
So, the dual of that linear program is:
\[\begin{align*} \min b^Ty \\ A^Ty \ge c \\ y \in \mathbb{R}_{\ge 0}^n \end{align*}\]

Q: The Secretary Problem
A: In the secretary problem, there are \(n\) candidates for a job. Each candidate \(i\) has some value \(v_i\), where we can assume the values are unique for simplicity.
Upon interviewing a candidate, we can either hire them or permanently pass on their application. The candidates will arrive in a uniformly random order. The question is: with what probability can we ensure we select the best candidate? And the answer is \(1/e\), or about 37%, as \(n \to \infty\). The strategy that works is to wait until you have seen \(n/e\) candidates, and then take the first candidate that is the best of everyone you have seen so far.

Q: Primal dual algorithm
A: In a primal dual algorithm, you iteratively construct a primal integral solution \(x\). Whenever you add value to \(x\), you add the same amount of value to a dual solution \(y\). You then guarantee that at the end of the algorithm, \(\alpha y\) is a feasible dual solution. This ensures your algorithm is \(\alpha\) competitive (if it's an online problem) or \(\alpha\) approximate (for a normal approximation algorithm).

Q: Algorithms with predictions
A: In the algorithms with predictions framework, there is a machine learning model that predicts some unknown property, for example the future inputs of an online problem or the approximate location of an item in a binary search instance.
An algorithm is \(\beta\) robust if the competitive ratio or approximation ratio algorithm performs no worse than \(\beta\) no matter the quality of the predictions. It is \(\alpha\) consistent if as the prediction error tends to 0, the algorithm achieves a ratio of \(\alpha\).

Q: The 2-universal property of hash functions
A: Let \(h: U \to [k]\) be a random hash function. Then \(h\) is 2-universal if over the randomness of \(h\), for any \(x \not= y \in U\), we have \(\mathbb{P}[h(x)=h(y)] \le \frac{1}{k}\).
This is weaker than the pairwise independence property, which would require that for any \(x \not=y \in U\) and any \(a,b \in [k]\) we have \(\mathbb{P}[h(x)=a,h(y)=b] = \frac{1}{k^2}\).

Q: An example of a 2-universal hash family
A: Given a universe \(U\) and a range \([k]\), pick a prime \(p \ge |U|\). To generate our random hash function \(h:U \to [k]\), pick \(a \in \{1,\dots,p-1\}\) and \(b \in [p]\) independetly and uniformly at random. Let \(f_{a,b}(x) = ax+b \pmod{p}\). Then our random hash function is \(h_{a,b}(x) = f_{a,b}(x) \pmod{k}\).

Q: Nearest neighbor problem and the naïve algorithm
A: In the nearest neighbor problem we have a set of \(n\) points \(S \subseteq \mathbb{R}^d\) and a distance function \(d: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}_{\ge 0}\). Given an input \(x\), the goal is to find the point \(y \in S\) which minimizes \(d(x,y)\).
The naïve algorithm is to iterate over all \(n\) points and record the closest one. However this is too slow if \(n\) is huge.

Q: Locality sensitive hashing
A: Given a radius \(r\), a distance function \(d\), an approximation factor \(\alpha \ge 1\), and probabilities \(p_{close},p_{far}\), we say a distribution over hash functions \(h:\mathbb{R}^d \to \mathbb{Z}\) is \(\rho\)-locality sensitive if:
* For all \(x,y \in \mathbb{R}^d\) with \(d(x,y) \le r\) we have \(\mathbb{P}[h(x)=h(y)] \ge p_{close}\)
* For all \(x,y \in \mathbb{R}^d\) with \(d(x,y) \ge \alpha r\) we have \(\mathbb{P}[h(x)=h(y)] \le p_{far}\)
for \(p_{close} > p_{far}\) with \(p_{close} = p_{far}^\rho\).
By creating many copies of an LSH, it can be used to solve the radius-constrained approximate nearest neighbors problem, where you want to find a neighbor of distance \(\alpha r\) if one exists within distance \(r\). (This radius-constrained version can be in turn used to solve the approximate nearest neighbors problem.)

Q: Prove that the probability a random point in \(B_r^d\) lies in \(B_{(1-\epsilon)}^d\) goes to 0 as \(d \to \infty\)
A: In other words, we are showing that as \(d \to \infty\), the mass of the ball moves towards its boundary. Here we use that the volume formula for a ball in \(d\) dimensions with radius \(r\) is a constant depending on \(d\) times \(r^d\).
For the proof, we just need to show that the ratio of the volume of the \((1-\epsilon)r\) ball over the \(r\) ball goes to 0. And it does:
\[\frac{\text{Vol}(B_{(1-\epsilon)r}^d)}{\text{Vol}(B_r^d)} = \frac{((1-\epsilon)r)^d}{r^d} = (1-\epsilon)^d\]

Q: Johnson Lindenstrauss Lemma
A: The JL lemma shows given \(n\) points in \(\mathbb{R}^d\), if we only care about their \(\ell_2\) distances (and up to a small approximation factor \(\epsilon\)), we can project them down to points in \(\mathbb{R}^k\) for \(k \in O(\log(n)/\epsilon^2)\).
Formally, given \(x_1,\dots,x_n \in \mathbb{R}^d\) and \(\epsilon > 0\), we can choose \(k \in O(\log(n)/\epsilon^2)\) and a matrix \(P \in \mathbb{R}^{k \times d}\) so that if \(y_i=Px_i\) for all \(1 \le i \le n\), the points \(y_1,\dots,y_n\) approximately preserve all the \(\ell_2\) distances of \(x_1,\dots,x_n\) so that for all \(i,j\) we have:
\[(1-\epsilon)\|x_i-x_j\|_2 \le \|y_i-y_j\|_2\le (1+\epsilon)\|x_i-x_j\|_2\]

Q: The Laplacian of a graph
A: The Laplacian matrix \(L \in \mathbb{R}^{n \times n}\) of a graph with \(n\) vertices is \(L=D-A\), where \(A\) is the adjacency matrix and \(D\) is the diagonal matrix of vertex degrees. One can show that for any \(x \in \mathbb{R}^n\), we have
\[x^TLx = \sum_{\{i,j\} \in E} (x_i-x_j)^2\]
so the Laplacian is PSD.

Q: Definition of a subspace of \(\mathbb{R}^n\) and its dimension
A: A subspace of \(\mathbb{R}^n\) is a set \(S \subseteq \mathbb{R}^n\) such that for any \(x,y \in S\) we have \(x+y \in S\), and for any \(x \in S\) and \(a \in \mathbb{R}\) we have \(ax \in S\).
The dimension of a subspace is the number of vectors in a basis for it. A basis of a subspace is a set of vectors \(v_1,\dots,v_k\) which are linearly independent and for which for any \(x \in S\) we can write \(x = \alpha_1v_1 + \dots + \alpha_kv_k\) for some \(\alpha \in \mathbb{R}^k\).

Q: Courant-Fischer theorem or Min-Max Theorem
A: Let \(A \in \mathbb{R}^{n \times n}\) be a symmetric matrix. Then:
\[\lambda_k = \min_{S \subseteq \mathbb{R}^n: \text{dim}(S)=k} \max_{x \in S} \frac{x^TAx}{x^Tx}\]

Q: Normalized Adjacency and Normalized Laplacian
A: The normalized adjacency matrix of a graph is:
\[\tilde{A} = D^{-1/2}AD^{-1/2}\]
The normalized Laplacian is
\[\tilde{L} = I-\tilde{A}\]The eigenvalues of \(\tilde{L}\) are between 0 and 2.

Q: Cheeger and the second eigenvalue of the normalized Laplacian
A: The second eigenvalue of the normalized Laplacian measures the graph's connectivity. It is 0 if and only if the graph is disconnected. Cheeger's inequality relates it to the conductance of the graph, \(\phi(G)\):
\[\frac{1}{2} \lambda_2 \le \phi(G) \le \sqrt{2\lambda_2}\]In other words, the larger the second eigenvalue, the larger the conductance must be.

Q: Conductance of a graph
A: Given a graph \(G\), the conductance of a cut \(S\) is:
\[\phi(S) = \frac{|\delta(S)|}{\text{vol}(S)}\]where \(\text{vol}(S) = \sum_{i \in S} d_i\), the sum of the degrees of the vertices in \(S\).
The conductance of the graph is:
\[\phi(G) = \min_{\text{vol}(S) \le \frac{1}{2}\text{vol}(V)} \phi(S)\]The conductance is a very important graph statistic. If it is small, it means that there is a set with large volume (many of the edges) which is separated from the graph by few edges. In a road network, this would correspond to a bottleneck: somewhere that has a lot of internal edges, but is difficult to leave. In a social network, a set with small conductance could be a tightly knit community with few outside connections.