Perturbed Identity Matrices Have High Rank: Proof and Applications

DOI10.1017/S0963548307008917zbMath1190.15002MaRDI QIDQ3557502

Noga Alon

Publication date: 23 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

geometryprobabilityrankcoding theorypseudo-randomnessperturbed matrixextremal finite set theorycross-intersecting pairnearly min-wise independent permutation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Linear codes (general theory) (94B05) Combinatorial probability (60C05) Extremal set theory (05D05) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items (33)

Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Near invariance of the hypercube ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ On the number of ordinary lines determined by sets in complex space ⋮ Ranks of matrices with few distinct entries ⋮ Around the log-rank conjecture ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Kolmogorov width and approximate rank ⋮ Equiangular lines and spherical codes in Euclidean space ⋮ Perfect and nearly perfect separation dimension of complete and random graphs ⋮ Nearly orthogonal vectors and small antipodal spherical codes ⋮ Polynomial approximation on disjoint segments and amplification of approximation ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Smaller Gershgorin disks for multiple eigenvalues of complex matrices ⋮ Orthonormal representations of \(H\)-free graphs ⋮ On deterministic sketching and streaming for sparse recovery and norm estimation ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ Approximating sparse binary matrices in the cut-norm ⋮ Some upper and lower bounds on PSD-rank ⋮ Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. ⋮ Fractional \(L\)-intersecting families ⋮ Fractional Sylvester–Gallai theorems ⋮ On (ε,k)‐min‐wise independent permutations ⋮ Unnamed Item ⋮ Sets of unit vectors with small subset sums ⋮ On subsets of the hypercube with prescribed Hamming distances ⋮ Lower bounds for local versions of dimension reductions ⋮ Fooling Pairs in Randomized Communication Complexity ⋮ Digital almost nets ⋮ Why Are Big Data Matrices Approximately Low Rank? ⋮ Upper bounds on communication in terms of approximate rank ⋮ SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY ⋮ IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM

Cites Work

• Problems and results in extremal combinatorics. I.
• Min-wise independent permutations
• Some structural properties of low-rank matrices related to computational complexity
• Measures of Pseudorandomness for Finite Sequences: Minimal Values
• On restricted min‐wise independence of permutations
• On finite pseudorandom binary sequences VII: The measures of pseudorandomness
• Symmetrized Chebyshev polynomials
• On (ε,k)‐min‐wise independent permutations

This page was built for publication: Perturbed Identity Matrices Have High Rank: Proof and Applications