:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Ghasemi, Fatemeh, Gross, Gal, Kopparty, Swastik
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Combinatorics Probability 68Q17 (Primary) 15A15, 15B33, 15B52 (Secondary) F.1.m
Online Access:	https://arxiv.org/abs/2512.03221
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The rank evolution of block bidiagonal matrices over finite fields
by: Mészáros, András
Published: (2025)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

A study of distributional complexity measures for Boolean functions
by: Köhler-Schindler, Laurin, et al.
Published: (2024)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

Global law of conjugate kernel random matrices with heavy-tailed weights
by: Guionnet, Alice, et al.
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Fisher information approximation of random orthogonal matrices by Gaussian matrices
by: Chen, Yutong, et al.
Published: (2025)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Asymptotic behavior of eigenvalues of large rank perturbations of large random matrices
by: Afanasiev, Ievgenii, et al.
Published: (2025)

Border rank bounds for $GL(V)$-invariant tensors arising from matrices of constant rank
by: Wu, Derek
Published: (2024)

On the spectral edge of non-Hermitian random matrices
by: Campbell, Andrew, et al.
Published: (2024)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Quantitative Tracy-Widom laws for sparse random matrices
by: Bucht, Teodor, et al.
Published: (2025)

Universality laws for random matrices via exchangeable counterparts
by: Tropp, Joel A.
Published: (2026)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

Local laws and spectral properties of deformed sparse random matrices
by: Lee, Ji Oon, et al.
Published: (2025)

A New Proof of the Abstract Random Tensor Estimate by Deng, Nahmod, and Yue
by: Kaneshiro, Claire
Published: (2025)

On $r$-to-$p$ norms of random matrices with nonnegative entries: Asymptotic normality and $\ell_\infty$-bounds for the maximizer
by: Dhara, Souvik, et al.
Published: (2020)

Cholesky decomposition for symmetric matrices over finite fields
by: Vishwakarma, Prateek Kumar
Published: (2025)

On the singularity probability of random circulant Bernoulli matrices
by: Miller, Niklas
Published: (2024)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Convergence of high dimensional Toeplitz and related matrices with correlated inputs
by: Adhikari, Kartick, et al.
Published: (2023)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Concise tensors of minimal border rank
by: Jelisiejew, Joachim, et al.
Published: (2022)

Monotonicity of the logarithmic energy for random matrices
by: Chafaï, Djalil, et al.
Published: (2022)

Patterned matrices with random walk entries
by: Bose, Arup, et al.
Published: (2025)

On semidefinite programming characterizations of the numerical radius and its dual norm for quaternionic matrices
by: Friedland, Shmuel
Published: (2023)

Revisiting Toeplitz and Hankel random matrices via $*$-convergence of circulant-type matrices
by: Bose, Arup, et al.
Published: (2026)

Eigenvalue collisions for periodic matrix families associated with Ginibre matrices
by: Vargas, Carlos
Published: (2025)

Optimal decay of eigenvector overlap for non-Hermitian random matrices
by: Cipolloni, Giorgio, et al.
Published: (2024)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

A pluricomplex error-function kernel at the edge of polynomial Bergman kernels
by: Molag, L. D.
Published: (2026)

Barriers for rectangular matrix multiplication
by: Christandl, Matthias, et al.
Published: (2020)

Weingarten calculus for centered random permutation matrices
by: Collins, Benoît, et al.
Published: (2025)

Eigenvalue distribution of the Hadamard product of sample covariance matrices in a quadratic regime
by: Assaly, Sebastien Abou, et al.
Published: (2025)

The Self-Replication Phase Diagram: Mapping Where Life Becomes Possible in Cellular Automata Rule Space
by: Yin, Don
Published: (2026)

Extremal random matrices with independent entries and matrix superconcentration inequalities
by: Brailovskaya, Tatiana, et al.
Published: (2024)