The discrepancy of random rectangular matrices

DOI10.1002/rsa.21054arXiv2101.04036OpenAlexW3211094389MaRDI QIDQ6074695

Jonathan Niles-Weed, Dylan J. Altschuler

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.04036

zbMATH Keywords

Stein's methoddiscrepancysparse random graphsrandom constraint satisfaction

Mathematics Subject Classification ID

Numerical analysis (65-XX) Linear and multilinear algebra; matrix theory (15-XX)

Related Items (2)

The Phase Transition of Discrepancy in Random Hypergraphs ⋮ MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential bounds for the hypergeometric distribution
• ``Integer-making theorems
• The collected works of Wassily Hoeffding. Ed. by N. I. Fisher and P. K. Sen
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Constructive Discrepancy Minimization for Convex Sets
• Integer feasibility of random polytopes
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• On the maximum satisfiability of random formulas
• Six Standard Deviations Suffice
• An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound
• Efficient algorithms for discrepancy minimization in convex sets
• Intersecting random half cubes
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Storage capacity in symmetric binary perceptrons
• On the discrepancy of random matrices with many columns
• On the discrepancy of random low degree set systems
• Capacity lower bound for the Ising perceptron
• On the Beck‐Fiala conjecture for random set systems
• The Gram-Schmidt walk: a cure for the Banaszczyk blues
• A Fourier-Analytic Approach for the Discrepancy of Random Set Systems
• Approximating Hereditary Discrepancy via Small Width Ellipsoids
• An Improvement of the Beck–Fiala Theorem
• The two possible values of the chromatic number of a random graph
• Frozen 1-RSB structure of the symmetric Ising perceptron

This page was built for publication: The discrepancy of random rectangular matrices