Disclaimer: All of these documents have been generated by AI. I make no claims about the correctness of the documents, and have not checked that they cite prior work adequately. Anyone is free to use these documents.
In a finite group, an element that conjugates a subgroup into itself must conjugate it onto itself. The binary Hilbert hotel turns this counting observation into an obstruction to finite approximation. Kun’s expander decomposition and two applications of stationarity explain why the obstruction survives small errors, giving a direct account of nonsoficity for over finite fields.
Suppose a regular graph satisfies a spectral-gap inequality on all functions vanishing on an exceptional set of vertices. How close is it to a disjoint union of expanders? A quantitative form of Kun’s repair argument gives an bound on the fraction of edits at fixed gap . The proof uses resolvent smoothing to find sparse cuts and controls their total cost.
Three shears on triples over define a degree-three graph. For maps from this graph into a uniformly convex space, the mean squared distance across an edge controls the mean squared distance between arbitrary vertices, uniformly in . A companion proof uses finite averaging to establish Banach property (T) for .
Three shears on triples over define a degree-three graph. For maps from this graph into a uniformly convex space, the mean squared distance across an edge controls the mean squared distance between arbitrary vertices, uniformly in . A companion proof uses finite averaging to establish Banach property (T) for .
This exposition follows a recursive-coloring argument for the nonamenability of Thompson’s group . An almost-invariant vector for the two standard tree rotations would force four colors in Hilbert space to form an almost regular tetrahedron. The distance between the midpoints of opposite edges then contracts by a factor the recursion cannot recover. A quantitative version gives the spectral-gap estimate.
Three groups of polynomial shears generate an infinite family of bounded-degree, two-dimensional coset complexes. Counting the roots of linear and quadratic polynomials gives expansion in the vertex links. The same shears act triply transitively and generate a 3-cycle, identifying the ambient permutation group as the full alternating group.
Gilman’s construction gives alternating quotients of unbounded degree for the group of special automorphisms of a free group of rank five. The proof turns on two permutations whose supports meet at a single point. Their commutator is a 3-cycle, and its conjugates generate the alternating group. Property (T) then gives a family of alternating-group expanders.
For each prime power , two subgroups of a matrix group over define a bipartite coset graph with degrees and . As grows, the graphs grow arbitrarily large while their normalized second singular value stays at most . Companion notes give a finite-field tuple construction and a proof of the spectral bound using walks on cosets.
For each prime power , two subgroups of a matrix group over define a bipartite coset graph with degrees and . As grows, the graphs grow arbitrarily large while their normalized second singular value stays at most . Companion notes give a finite-field tuple construction and a proof of the spectral bound using walks on cosets.
For each prime power , two subgroups of a matrix group over define a bipartite coset graph with degrees and . As grows, the graphs grow arbitrarily large while their normalized second singular value stays at most . Companion notes give a finite-field tuple construction and a proof of the spectral bound using walks on cosets.
Does encoding each bit as one of two pure quantum states preserve more relative entropy from uniform than randomly revealing the bits at matched rates? The Heart conjecture says it does not. For equal channel parameters, these notes establish the comparison for three bits with uniform marginals and for four bits under antipodal symmetry. A separate four-bit proof allows all four cubic Walsh coefficients to be present simultaneously in the pure cubic sector.
Does encoding each bit as one of two pure quantum states preserve more relative entropy from uniform than randomly revealing the bits at matched rates? The Heart conjecture says it does not. For equal channel parameters, these notes establish the comparison for three bits with uniform marginals and for four bits under antipodal symmetry. A separate four-bit proof allows all four cubic Walsh coefficients to be present simultaneously in the pure cubic sector.
Does encoding each bit as one of two pure quantum states preserve more relative entropy from uniform than randomly revealing the bits at matched rates? The Heart conjecture says it does not. For equal channel parameters, these notes establish the comparison for three bits with uniform marginals and for four bits under antipodal symmetry. A separate four-bit proof allows all four cubic Walsh coefficients to be present simultaneously in the pure cubic sector.
The total-correlation Heart conjecture compares how much dependence survives two ways of transmitting correlated bits. These notes prove the comparison along perturbations that change only the full parity interaction, and to second order around every product law in every direction preserving the one-bit marginals. Both results allow different channel strengths at different coordinates.
The total-correlation Heart conjecture compares how much dependence survives two ways of transmitting correlated bits. These notes prove the comparison along perturbations that change only the full parity interaction, and to second order around every product law in every direction preserving the one-bit marginals. Both results allow different channel strengths at different coordinates.
How much more can quantum side information tell us about the label of a state if we also receive its canonical purification? A conditional mutual-information inequality bounds this increase. Combined with recovery and Schur–Weyl compression, it gives a direct proof that a rank- state in dimension can be learned to infidelity from copies.
Fix a bipartite graph and put a distinct variable on each edge. Its weighted perfect-matching polynomial has a subexponential-size, depth-four formula over the rationals whenever the maximum degree is , where is the size of each side. Hermite interpolation gives a formula in which the factors at every product gate use disjoint sets of rows.
A computation that revisits large memory blocks may exchange only a few bits between visits. Representing these exchanges as short communication protocols lets a Cook–Mertz evaluator reuse its workspace. For a deterministic computation of time , this gives space bounds of on one tape, on a fixed number of tapes, and on a RAM with logarithmic word size.
A computation that revisits large memory blocks may exchange only a few bits between visits. Representing these exchanges as short communication protocols lets a Cook–Mertz evaluator reuse its workspace. For a deterministic computation of time , this gives space bounds of on one tape, on a fixed number of tapes, and on a RAM with logarithmic word size.
Relative to random oracles with logarithmic-length queries, a Boolean function separates nearly linear-size quantum random-access computations from fixed-wiring quantum circuits of nearly quadratic size. For the traveling salesman problem, the dynamic program has enough structure to specify its memory accesses in advance. The resulting quantum algorithm uses gates and qubits without QRAM.
A bipartite graph has a perfect matching exactly when one explicit matrix has full column rank. A Hall obstruction supplies a kernel vector. In the other direction, a Wronskian bounds how many zeros a space of low-degree polynomials can have. Parallel rank computation then decides perfect matching in deterministic , following the approach of Chatterjee and coauthors and its simplification by Kopparty and Saraf.
A satisfying circuit computation chooses one truth-table row per gate, with neighboring choices agreeing on shared wires. The identity turns an inconsistent pair into terms that disappear when we keep only multilinear monomials. The number of satisfying computations becomes one coefficient of a product of linear forms, hence an integer permanent. This gives an algebraic proof of #P-hardness inspired by Aaronson’s linear-optical argument.
Suppose the permanent had DLOGTIME-uniform, polynomial-size threshold circuits of constant depth. Then counting would give , making succinct descriptions of such circuits evaluable in polynomial time. Applying this to an exponentially scaled permanent reduction would put in , contradicting the time hierarchy theorem. This is the constant-depth case of the Koiran–Perifel lower bound.
Two diagonalizations give circuit lower bounds in different regimes. Li’s postorder inversion of a binary tree identifies a missing truth table and yields a language in requiring more than gates at every sufficiently large length. A separate proof of Vinodchandran’s theorem combines majority-based elimination with the interactive proof for counting to show that, for each fixed , some language in requires more than gates.
Two diagonalizations give circuit lower bounds in different regimes. Li’s postorder inversion of a binary tree identifies a missing truth table and yields a language in requiring more than gates at every sufficiently large length. A separate proof of Vinodchandran’s theorem combines majority-based elimination with the interactive proof for counting to show that, for each fixed , some language in requires more than gates.
Revealing a verifier’s private coins can destroy the soundness of an interactive proof. Goldwasser and Sipser instead have the new verifier check claims about the number of random tapes on which the old verifier would accept. Random hashing lets it check these claims one message at a time. The conversion adds one verifier–prover message pair and preserves completeness and soundness.
If the rows and columns of a table are each close to low-degree polynomials, when must they come from a single bivariate polynomial? The Polishchuk–Spielman gluing theorem answers this question and supplies the soundness argument for the Ben–Sasson–Sudan proof of proximity. For a fixed-rate Reed–Solomon code, the verifier reads only constantly many field symbols from the word and a quasilinear-length proof.
If the rows and columns of a table are each close to low-degree polynomials, when must they come from a single bivariate polynomial? The Polishchuk–Spielman gluing theorem answers this question and supplies the soundness argument for the Ben–Sasson–Sudan proof of proximity. For a fixed-rate Reed–Solomon code, the verifier reads only constantly many field symbols from the word and a quasilinear-length proof.
Arithmetize a verification circuit as quadratic constraints, encode the witness by a multilinear polynomial, and write down the prover’s sum-check replies as a table. This gives every NP language a quasipolynomial-length proof checkable with polylogarithmically many random bits and queries. One additional test, comparing a locally corrected input bit with the actual input, turns the construction into a proof of proximity.
How many nonscalar multiplications are needed to evaluate a polynomial of degree at most n, when linear combinations are free? This note gives an upper bound of √n + O(√n/log n) over every algebraically closed field, matching the leading constant in the known lower bound. The construction combines short multiplication chains, interpolation modulo pairwise coprime polynomials, and an algebraic-geometric argument.