Some independence results in complexity theory†

DOI10.1080/00207168508803454MaRDI QIDQ3751002zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Shlomo Moran

Publication date 1985

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207168508803454

zbMATH Keywords

matrix multiplicationrank of a matrixoraclealgebraic functionstraight-line programtransitive closure of a graphmaximum bipartite matchingset of independent rows and columns in a matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of approximating the independent set problem
• Relativized circuit complexity
• On the complexity of approximating the independent set problem (extended abstract)
• The complexity of parallel search
• Some computational problems in linear algebra as hard as matrix multiplication

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3228674 (Why is no real title available?)
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Berechnung und Programm. II
• Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication
• Gaussian elimination is not optimal

Cited in

(3)

• An Independence Result in Several Complex Variables
• scientific article; zbMATH DE number 786176 (Why is no real title available?)
• scientific article; zbMATH DE number 3885886 (Why is no real title available?)

This page was built for publication: Some independence results in complexity theory^†

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751002)