Fetching the paper…
Reading the bibliography…
In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over $\mathbb{Q}$ is invertible or not.
Units in group rings
Graham Higman · 1940
Earlier work this paper cites.
A theorem on independence relations
R. Rado · 1942
Earlier work this paper cites.
Sur une généralisation du groupe orthogonal à quatre variables
J. Dieudonné · 1949
Earlier work this paper cites.
Some properties of a sfield
Loo-Keng Hua · 1949
Earlier work this paper cites.
Minimal identities for algebras
S. A. Amistur and J. Levitzki · 1950
Earlier work this paper cites.
Recursive unsolvability of group theoretic problems
Michael O. Rabin · 1958
Earlier work this paper cites.
Theorie der Normalflachen
Wolfgang Haken · 1961
Earlier work this paper cites.
A relationship between arbitrary positive matrices and doubly stochastic matrices
R. Sinkhorn · 1964
Earlier work this paper cites.
Rational identities and applications to algebra and geometry
Shimshon Amitsur · 1966
Earlier work this paper cites.
Systems of distinct representatives and linear algebra
Jack Edmonds · 1967
Earlier work this paper cites.
Submodular functions, matroids, and certain polyhedra
Jack Edmonds · 1969
Earlier work this paper cites.
The embedding of firs in skew fields
P. M. Cohn · 1971
Earlier work this paper cites.
The word problem for free fields
P. M. Cohn · 1973
Earlier work this paper cites.
Vermeidung von Divisionen
V. Strassen · 1973
Earlier work this paper cites.
Trace identities of full matrix algebras over a field of characteristic zero
Ju. P. Razmyslov · 1974
Earlier work this paper cites.
Completely positive linear maps on complex matrices
M. Choi · 1975
Earlier work this paper cites.
The word problem for free fields: A correction and an addendum
P. M. Cohn · 1975
Earlier work this paper cites.
The invariant theory of n×n matrices
C. Procesi · 1976
Earlier work this paper cites.
A prime matrix ideal yields a skew field
P. Malcolmson · 1978
Earlier work this paper cites.
On the parallel evaluation of multivariate polynomials
Laurent Hyafil · 1979
Earlier work this paper cites.
On determinants, matchings, and random algorithms
Laszlo Lovasz · 1979
Earlier work this paper cites.
The complexity of computing the permanent
Leslie Valiant · 1979
Earlier work this paper cites.
Large spaces of matrices of bounded rank
M. D. Atkinson and S. Lloyd · 1980
Earlier work this paper cites.
Spaces of matrices with several zero eigenvalues
M. D. Atkinson · 1980
Earlier work this paper cites.
Selecting independent lines from a family of lines in a space
Laszlo Lovasz · 1980
Earlier work this paper cites.
Polynomial identities in ring theory
Louis Halle Rowen · 1980
Earlier work this paper cites.
The constructive theory of invariants
Vladimir L Popov · 1982
Cited alongside, same era.
On computing the determinant in small parallel time using a small number of processors
Stuart J. Berkowitz · 1984
Cited alongside, same era.
Generating the ring of matrix invariants
Edward Formanek · 1986
Cited alongside, same era.
Nullspaces of spaces of matrices of bounded rank
L. B. Beasley · 1987
Cited alongside, same era.
Vector spaces of matrices of low rank
David Eisenbud and Joe Harris · 1988
Cited alongside, same era.
Singular spaces of matrices and their application in combinatorics
Laszlo Lovasz · 1989
Cited alongside, same era.
Lower bounds for non-commutative computation
Derandomizing polynomial identity tests means proving circuit lower bounds
Valentine Kabanets and Russell Impagliazzo · 2004
Later among the works it cites.
More on noncommutative polynomial identity testing
Andrej Bogdanov and Hoeteck Wee · 2005
Later among the works it cites.
Deterministic polynomial identity testing in non commutative models
Ran Raz and Amir Shpilka · 2005
Later among the works it cites.
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
Z. Dvir and A. Shpilka · 2006
Later among the works it cites.
Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications
Leonid Gurvits · 2006
Later among the works it cites.
Ideals, Varieties, and Algorithms
D. Cox, J. Little, and D. O’Shea · 2007
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Noam Nisan · 1991
Cited alongside, same era.
Skew Fields, Theory of General Division Rings
P. M. Cohn · 1995
Cited alongside, same era.
Classical invariant theory, a primer
H. Kraft and C. Procesi · 1996
Cited alongside, same era.
Inversion height in free fields
Christophe Reutenauer · 1996
Cited alongside, same era.
The deflation-inflation method for certain semidefinite programming and maximum determinant completion problems
Leonid Gurvits and Peter N. Yianilos · 1998
Cited alongside, same era.
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Nati Linial, Alex Samorodnitsky, and Avi Wigderson · 1998
Cited alongside, same era.
Later among the works it cites.
Polynomial identity testing for depth 3 circuits
N. Kayal and N. Saxena · 2007
Later among the works it cites.
A geometric approach to the kronecker problem ii : rectangular shapes, invariants of n × n matrices, and a generalization of the artin-procesi theorem
Bharat Adsul, Suresh Nayak, and K. V. Subrahmanyam · 2010
Later among the works it cites.
Relationless completeness and separations
Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff · 2010
Later among the works it cites.
Noncommutative rational functions, their difference-differential calculus and realizations
D. S. Kaliuzhnyi-Verbovetskyi and Victor Vinnikov · 2010
Later among the works it cites.
Arithmetic Circuits: A Survey of Recent Results and Open Questions
Amir Shpilka and Amir Yehudayoff · 2010
Later among the works it cites.
Non-commutative circuits and the sum-of-squares problem
Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff · 2011
Later among the works it cites.
Black-box identity testing of depth 4 multilinear circuits
S. Saraf and I. Volkovich · 2011
Later among the works it cites.
Geometric complexity theory v: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of noether’s normalization lemma
Ketan Mulmuley · 2012
Later among the works it cites.
Explicit noether normalization for simultaneous conjugation via polynomial identity testing
Michael Forbes and Amir Shpilka · 2013
Later among the works it cites.
Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs
Michael Forbes and Amir Shpilka · 2013
Later among the works it cites.
Non-commutative arithmetic circuits with division
Pavel Hrubes and Avi Wigderson · 2014
Later among the works it cites.
Generalized Wong sequences and their applications to edmonds’ problems
Gabor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha · 2015
Closest in time.
Lower bounds for non-commutative skew circuits
Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan · 2015
Closest in time.
Bipartite perfect matching is in quasi-nc
Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf · 2016
Closest in time.
Greedy strikes again: A deterministic ptas for commutative rank of matrix spaces
Markus Bläser, Gorav Jindal, and Anurag Pandey · 2017
Closest in time.
Polynomial degree bounds for matrix semi-invariants
Harm Derksen and Visu Makam · 2017
Closest in time.
Non-commutative Edmonds’ problem and matrix semi-invariants
Gábor Ivanyos, Youming Qiao, and KV Subrahmanyam · 2017
Closest in time.
Algorithmic and optimization aspects of brascamp-lieb inequalities, via operator scaling
Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson · 2018
Closest in time.
Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics
Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam · 2018
Closest in time.