This paper studies the incompressibility and spectral gaps of random circuits. It proves that the spectral gap for random reversible circuits is Ω(n⁻³) for all t ≥ 1, and for random quantum circuits it is Ω(n⁻³) for t ≤ Θ(2ⁿ/²). These gaps are independent of t in their respective regimes. The results are further improved to n⁻¹/polylog(n,t) for t ≤ 2Θ(n), which is tight up to polylog factors in n and t. The spectral gap results have several consequences, including that random reversible circuits with O(n⁴t) gates form multiplicative-error t-wise independent (even) permutations for all t ≥ 1, and that random quantum circuits with O(n⁴t) gates form multiplicative-error unitary t-designs for t ≤ Θ(2ⁿ/²). The paper also proves that the robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, resolving the Brown–Susskind conjecture. The results are proven by reducing random quantum circuits to a more structured walk, using a modified "PFC ensemble" and an expander on the alternating group. The spectral gap bounds are proven using tools from the study of frustration-free Hamiltonians. The paper also discusses the implications of these results for t-designs, circuit complexity, and the mixing rates of random circuits.This paper studies the incompressibility and spectral gaps of random circuits. It proves that the spectral gap for random reversible circuits is Ω(n⁻³) for all t ≥ 1, and for random quantum circuits it is Ω(n⁻³) for t ≤ Θ(2ⁿ/²). These gaps are independent of t in their respective regimes. The results are further improved to n⁻¹/polylog(n,t) for t ≤ 2Θ(n), which is tight up to polylog factors in n and t. The spectral gap results have several consequences, including that random reversible circuits with O(n⁴t) gates form multiplicative-error t-wise independent (even) permutations for all t ≥ 1, and that random quantum circuits with O(n⁴t) gates form multiplicative-error unitary t-designs for t ≤ Θ(2ⁿ/²). The paper also proves that the robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, resolving the Brown–Susskind conjecture. The results are proven by reducing random quantum circuits to a more structured walk, using a modified "PFC ensemble" and an expander on the alternating group. The spectral gap bounds are proven using tools from the study of frustration-free Hamiltonians. The paper also discusses the implications of these results for t-designs, circuit complexity, and the mixing rates of random circuits.