The classic graphical Cheeger inequalities state that if M is an n × n symmetric doubly stochastic matrix, then where is the edge expansion of M, and λ2(M) is the second largest eigenvalue of M. We study the relationship between φ(A) and the spectral gap 1 – Re λ2(A) for any doubly stochastic matrix A (not necessarily symmetric), where λ2(A) is a nontrivial eigenvalue of A with maximum real part. Fiedler showed that the upper bound on φ(A) is unaffected, i.e., . With regards to the lower bound on φ(A), there are known constructions with indicating that at least a mild dependence on n is necessary to lower bound φ(A). In our first result, we provide an exponentially better construction of n × n doubly stochastic matrices An, for which In fact, all nontrivial eigenvalues of our matrices are 0, even though the matrices are highly nonexpanding. We further show that this bound is in the correct range (up to the exponent of n), by showing that for any doubly stochastic matrix A, As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of in lower bounding φ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices R with nonnegative entries, to obtain a two-sided gapped refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such R, there is a nonnegative eigenvalue r such that all eigenvalues of R lie within the closed disk of radius r about 0. Further, if R is irreducible, which means φ(R) > 0 (for suitably defined φ), then r is positive and all other eigenvalues lie within the open disk, so (with eigenvalues sorted by real part), Re λ2(R) < r. An extension of Fiedler's result provides an upper bound and our result provides the corresponding lower bound on φ(R) in terms of r – Re λ2(R), obtaining a two-sided quantitative version of the Perron-Frobenius theorem.

Let f be a Boolean function on n variables, rho a random p-restriction that independently keeps each variable unset (or free) with probability p and otherwise uniformly sets it to 0 or 1, and DT_{depth}(f) denote the depth of the smallest depth decision tree for f. Let R_d(f|rho) be the resilience of f to rho for depth d, defined as R_d(f|rho)=Pr_{rho < - rho}[DT_{depth}(f|rho)>= d]. If d >> pn, all functions have resilience close to 0 since less than d variables would remain unset with high probability. For d << pn, most functions f on n variables have resilience close to 1, and some functions, like AND and OR, have resilience close to 0. Håstad's Switching Lemma states that for t-DNFs, the resilience R_d(f|rho) is upper bounded by (5pt)^d, and from known upper bounds on the size of constant depth circuits computing the parity function, it follows that there exist t-DNFs whose resilience is close to the bound obtained by Håstad. However, the exact bounds for such maximally resilient DNFs or their structure is unclear, and moreover, the argument is non-constructive. In this work, we give an explicit construction of functions called Tree Tribes parameterized by an integer t and denoted Xi_t (on n variables), such that R_d(Xi_t|rho)<=(4p2^t)^d, and more importantly, the resilience is also lower bounded by the same quantity up to constants, R_d(Xi_t|rho)>=(c_0 p2^t)^d, for 0 <= p <= c_p 2^-t and 0 <= d <= c_d * (log n)/(2^t * t log t) (where c_0,c_p,c_d are universal constants). As a result, for sufficiently large n and small d, this gives a hierarchy of functions with strictly increasing resilience, and covers the entire region between the two extremes where functions have resilience (close to) 0 or 1.