Cover Image

Simple Norm Bounds for Polynomial Random Matrices via Decoupling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Tulsiani, Madhur, Wu, June
Format:	Preprint
Published:	2024
Subjects:	Probability Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
by: Guruswami, Venkatesan, et al.
Published: (2021)

Equidistribution of Zeros of Random Polynomials and Random Polynomial mappings on $\mathbb{C}^m$
by: Günyüz, Ozan
Published: (2022)

Explicit Codes approaching Generalized Singleton Bound using Expanders
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
by: Srivastava, Shashank, et al.
Published: (2025)

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
by: Williamson, Christopher
Published: (2026)

Lines in Every Direction with No ee-Random Points
by: Lutz, Neil, et al.
Published: (2025)

Equidistribution for Random Polynomials and Systems of Random Holomorphic Sections
by: Günyüz, Ozan
Published: (2024)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

Pseudorandom Permutations from Random Reversible Circuits
by: He, William, et al.
Published: (2024)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
by: Gamarnik, David, et al.
Published: (2023)

Polynomial-time sampling despite disorder chaos
by: Ma, Eric, et al.
Published: (2025)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
by: Li, Rupert, et al.
Published: (2025)

Perfect sampling from rapidly mixing Markov chains
by: Göbel, Andreas, et al.
Published: (2024)

The Probability Spaces of QuickSort
by: Nadareishvili, George, et al.
Published: (2025)

Rigorous Implications of the Low-Degree Heuristic
by: Hsieh, Jun-Ting, et al.
Published: (2026)

Inconsistency Probability of Sparse Equations over F2
by: Horak, P., et al.
Published: (2026)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

A Polynomial Rate of Convergence for the Dirichlet Problem on Orthodiagonal Maps
by: Pechersky, David
Published: (2025)

On the Induced Norms of Matrices and Grothendieck problems
by: Truong, Lan V., et al.
Published: (2026)

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
by: Xu, Jeff
Published: (2024)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Permanents of random matrices over finite fields
by: Hunter, Zach, et al.
Published: (2026)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

Algorithmic Randomness and Probabilistic Laws
by: Barrett, Jeffrey A., et al.
Published: (2023)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

Probabilistic Zero Bounds of Certain Random Polynomials
by: Sheikh, Sajad A., et al.
Published: (2026)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
by: Li, Cheuk Ting
Published: (2024)

Computational lower bounds for multi-frequency group synchronization
by: Kireeva, Anastasia, et al.
Published: (2024)

Matrix Chaos Inequalities and Chaos of Combinatorial Type
by: Bandeira, Afonso S., et al.
Published: (2024)

Separating complexity classes of LCL problems on grids
by: Berlow, Katalin, et al.
Published: (2025)

Critical window for approximate counting in dense Ising models
by: Galanis, Andreas, et al.
Published: (2026)

A deterministic proof of Loewner energy reversibility via local reversals
by: Sung, Jinwoo
Published: (2024)

Interplay between Loewner and Dirichlet energies via conformal welding and flow-lines
by: Viklund, Fredrik, et al.
Published: (2019)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
by: Kızıldağ, Eren C.
Published: (2023)

Asymptotic Mass Distribution of Random Holomorphic Sections
by: Bayraktar, Turgay, et al.
Published: (2025)