Probabilistic rank and matrix rigidity
From MaRDI portal
Publication:4978010
DOI10.1145/3055399.3055484zbMath1369.68212arXiv1611.05558OpenAlexW2553219432MaRDI QIDQ4978010
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.05558
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (14)
Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Matrix and tensor rigidity and \(L_p\)-approximation ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Predicate encryption from bilinear maps and one-sided probabilistic rank ⋮ Arithmetic circuits, structured matrices and (not so) deep learning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Fourier and circulant matrices are not rigid ⋮ Lower bounds for matrix factorization ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle
This page was built for publication: Probabilistic rank and matrix rigidity
