Higher Moments of Random Determinants and Pseudorandomness for Structured Computation

This dissertation develops results in two research directions at the intersection of theoretical computer science, probability, and combinatorics. The first part studies moments of determinants of random matrices, with an emphasis on the combinatorial and analytic structures underlying their exact and asymptotic evaluation. The second part studies pseudorandomness for restricted models of computation, including branching programs and decision-tree-like models, with the goal of reducing the amount of randomness required to approximate or reproduce their behavior.

Although the two parts address different mathematical questions, they share a common methodological perspective. In both settings, an apparently complicated global quantity is understood by decomposing it into structured combinatorial components. For random determinants, this involves organizing the terms arising from determinant expansions and analyzing the resulting generating functions. For pseudorandomness, it involves identifying structural properties of computational models that allow truly random inputs to be replaced by distributions generated from short random seeds.

Let $A$ be a random matrix. This dissertation studies exact formulas, generating functions, and asymptotic expansions for moments of its determinant. The central combinatorial object is a permutation table obtained by expanding several copies of the determinant simultaneously. The moment becomes a signed, weighted enumeration of these tables, and the dependence on the entry distribution is encoded by column types.

The first part develops an analytic-combinatorial method for this enumeration. Rather than count complete permutation tables one at a time, the method decomposes them into simpler components and uses exponential generating functions to count all ways of assigning labels and assembling those components. This gives a short derivation of the known second and fourth moments and a compact presentation of the sixth moment for mean-zero entries. For the centered sixth moment, the baseline consists of tables in which the six positions of every column are grouped into three pairs of equal entries; the signed enumeration of these paired tables equals the sixth determinant moment for standard Gaussian entries. The paired part therefore provides a distribution-independent core. The remaining dependence on the third, fourth, and sixth entry moments is carried by explicit repeated-entry patterns that form isolated columns, closed cycles, or chains ending at pairs in the core.

The second part removes the mean-zero assumption. Write $A_n=B_n+m_1\mathbf 1\mathbf 1^{\mathsf T}$, where the entries of $B_n$ are centered. Applying the matrix determinant lemma to each of the six determinant factors produces marked permutation tables in which each table row, one for each determinant factor, contains at most one mark; a mark records the choice of the scalar term $m_1$. Thus a table contains at most six marks, and the calculation treats separately every possible number of marks from zero through six. In a contributing column, each unmarked centered entry must occur at least twice, so the repeated entries form pairs, triples, or larger equality blocks. An inclusion--exclusion replacement separates the ordinary pairings from the corrections contributed by higher central moments.

A reduction then contracts arbitrarily long chains and leaves a finite shell containing the marks and exceptional columns, a compatible core containing only pairs, and closed components disjoint from the shell. The resulting shell formula combines local column weights, the complete centered sixth-moment series, symmetry factors that prevent duplicate counting, determinant signs, and a finite signed count of the smallest pair-only cores that complete the shell. To reuse calculations for the same row-support pattern, the implementation compares all $6!=720$ relabelings of the six table rows and assigns row-equivalent patterns a common cache key. When a cached calculation is reused, a separately computed relative inversion parity determines whether it enters with the same or the opposite sign.

Finally, the same analytic-combinatorics viewpoint is applied to random symmetric, Wigner, and Hermitian matrices. In these ensembles, permutation tables are replaced by weighted multigraph structures that account for the dependence between transposed entries. This yields explicit second-moment generating functions and places the classical symmetric result in a unified framework.

The second part of this dissertation studies pseudorandomness under strong structural restrictions. The first part concerns pseudorandom generators for space-bounded computation, with an emphasis on constant-width standard-order read-once branching programs. The second part concerns pseudorandom generators for adaptive local computation, most notably decision trees and related models.

The technical core of the dissertation consists of two chapters based on joint work with William M.~Hoza. In the first, we investigate a new ``XOR of INW'' paradigm: starting from the Impagliazzo--Nisan--Wigderson generator, we analyze the bitwise XOR of several independent copies, prove that this construction fools constant-width branching programs, and establish matching limitations showing that this approach alone cannot break the classical $O(\log^2 n)$ seed-length barrier. In the second, we introduce the notion of $k$-wise probable uniformity, construct generators with seed length essentially $(1+\alpha)k$, and use them to fool near-maximal decision trees. Also, we build hitting sets for linear-algebraic and circuit classes.

Taken together, these results illustrate a common theme: useful pseudorandomness can be obtained by exploiting the exact structure of the target model rather than relying only on generic primitives such as small-bias spaces. The introduction and preliminaries are written to present both chapters as part of a single narrative about derandomization for restricted computation.

Although the two parts concern different mathematical objects, they share a common methodological perspective: complex global behavior is analyzed by identifying and exploiting underlying combinatorial structure.