Sampling a non degenerate (that is, invertible) square matrix over a finite field is easy, draw a random square matrix and discard if the determinant is zero. We address the problem in higher dimensions, and sample non degenerate boundary format tensors, which generalise square matrices. Testing degeneracy is conjectured to be hard in more than two dimensions [Hillar and Lim, 2013], precluding the "draw a random tensor and discard if degenerate" recipe. The difficulty is in computing hyperdeterminants, higher dimensional analogues of determinants. Instead, we start with a structured random non degenerate tensor and scramble it by infusing more randomness while still preserving non degeneracy. We propose two kinds of scrambling. The first is multiplication in each dimension by random invertible matrices, which preserves dimension and format. Assuming pseudo randomness of this action, which also underlies tensor isomorphism based cryptography, our samples are computationally indistinguishable from uniform non degenerate tensors. The second scrambling employs tensor convolution (that generalises multiplication by matrices) and can increase dimension. Inspired by hyperdeterminant multiplicativity, we devise a recursive sampler that uses tensor convolution to reduce the problem from arbitrary to three dimensions. Our sampling is a candidate solution for drawing public keys in tensor isomorphism based cryptography, since non degenerate tensors elude recent weak key attacks targeting public key tensors either containing geometric structures such as "triangles" [Lars Ran and Simona Samardjiska, 2024] or being deficient in tensor rank [Gilchrist et al., 2024]. To accommodate our sampling, tensor isomorphism based schemes need to be instantiated in boundary formats such as (2k+1) × (k+1) × (k+1), away from the more familiar k × k × k cubic formats. Our sampling (along with the recent tensor trapdoor one-way functions [Anand Kumar Narayanan, 2025]) makes an enticing case to transition tensor isomorphism cryptography to boundary formats tensors, which are true analogues of square matrices.

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudlák's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudlák and Cohen-Haeupler-Schulman's constructions.

Tree codes, introduced by Schulman [26, 27], are combinatorial structures essential to coding for interactive communication. An infinite family of tree codes with both rate and distance bounded by positive constants is called asymptotically good. Rate being constant is equivalent to the alphabet size being constant. Schulman proved that there are asymptotically good tree code families, yet their explicit construction remains an outstanding open problem. In a major breakthrough, Cohen, Haeupler and Schulman [12] constructed explicit tree code families with constant distance, but over an alphabet polylogarithmic in the length. Our main result is a randomized polynomial time decoding algorithm for these codes making novel use of the polynomial method. The number of errors corrected scales roughly as the block length to the three-fourths power, falling short of the constant fraction error correction guaranteed by the constant distance. We further present number theoretic variants of Cohen-Haeupler-Schulman codes, all correcting a constant fraction of errors with polylogarithmic alphabet size. Towards efficiently correcting close to a constant fraction of errors, we propose a speculative convex optimization approach inspired by compressed sensing.

We construct explicit algebraic geometry codes built from the Garcia-Stichtenoth function-field tower beating the Gilbert-Varshamov bound for alphabet sizes at least 192. Messages are identified with functions in certain Riemann- Roch spaces associated with divisors supported on multiple places. Encoding amounts to evaluating these functions at degreeone places. By exploiting algebraic structures particular to the Garcia-Stichtenoth tower, we devise an intricate deterministic ω/2 <; 1.19 runtime exponent encoding and 1 + ω/2 <; 2.19 expected runtime exponent randomized (unique and list) decoding algorithms. Here ω <; 2.373 is the matrix multiplication exponent. If ω = 2, as widely believed, the encoding and decoding runtimes are respectively nearly linear and nearly quadratic. Prior to this work, encoding time of code families beating the Gilbert-Varshamov bound were quadratic or worse.

The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes ~O(n^{3/2}*log(q)+n*log^2(q)) time to factor polynomials of degree n over the finite field F_q with q elements. A significant open problem is if the 3/2 exponent can be improved. We study a collection of algebraic problems and establish a web of reductions between them. A consequence is that an algorithm for any one of these problems with exponent better than 3/2 would yield an algorithm for polynomial factorization with exponent better than 3/2.

We use recently developed convex programming techniques to reconstruct arbitrary sparse signals observed through projections onto a small-dimensional space in background noise in order to estimate and remove impulsive noise in an OFDM system. We develop deterministic construction of projection matrices that provably guarantee reconstruction with high probability. Finally, we compare the achievable rate using our novel method with some simple capacity lower and upper bounds and with the recently obtained capacity of the Gaussian erasure channel. For practical impulse probability the proposed scheme appears to be competitive. This scheme may find some application in DSL and powerline communications, where transmission is typically affected by intersymbol interference, Gaussian noise and impulsive noise.