Some independence results in complexity theory†

DOI10.1080/00207168508803454zbMATH Open0611.68017OpenAlexW2110207657MaRDI QIDQ3751002FDOQ3751002

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

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

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)

Cites Work

• Title not available (Why is that?)
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• 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

Cited In (3)

• An Independence Result in Several Complex Variables
• Title not available (Why is that?)
• Title not available (Why is that?)

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)