Ketan Mulmuley
- AHU.A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithm, Addison- Wesl.ey, Reading, Mass,, 1974. Google Scholar
Digital Library
- BCP.A. Borodin, S.A. Cook, and N. Pippinger, 'Parallel Computation for Well-endowed Rings and Space Bounded Probabilistic Machines,' Information and Control 58, 1-3 (1983). pp. 113-136. Google ScholarDigital Library
- BGH.A. Borodin, J. von zur Gathen, and J.E. Hopcroft, 'Fast Parallel Matrix and GCD Computations', Twenty Third Annual IEEE Symp. on the Foundations of Computer Science (1982?), pp. 65-71.Google Scholar
- Br.A.Z. Broder, 'How Hard is it to Marry at Random? (On the Approximation of the Permanent)', Eighteenth Annual Symp. on the Theory of Computing, (1986), pp. 50-58. Google ScholarDigital Library
- Co.S.A. Cook, 'A Taxonomy of Problems with Fast Parallel Algorithms,' information and Control, 64, 2-22 (1985). Google ScholarDigital Library
- Cs.L. Csanky, 'Fast Parallel Matrix Inversion Algorithms,' SIAM J. Computing 5, (1976), pp. 618-623.Google ScholarCross Ref
- Ed1.J. Edmonds, 'Paths, Trees and Flowers, ' Canad. J. Math., 17, (1965), pp. 449-467.Google ScholarCross Ref
- Ed2.J. Edmonds, 'Systems of Distinct Representatives and Linear Atgebra,' J. Res. Nat. Bureau of Standards, 71B, 4, (1967), pp 241-245.Google Scholar
- GP.Z. Galil and V. Pan, 'Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC,' Twenty Sixth Annual IEEE Symp. on the Foundations of Computer Science, (1985). pp. 490-495.Google Scholar
- JVV.M.R. Jerrum, L.G. Valiant and V. V. Vazirani, 'Random Generation of Combinatorial Structures from a Uniform Distribution', Theoretical Computer Science 43 (1986) pp. 169-188. , Google ScholarDigital Library
- Ka.H. Karloff, 'A Randomized Parallel Algorithm for the Odd Set Cover Problem,' to appear in Combinatorica.Google Scholar
- KUW1.R.M. Karp, E. Upfal, and A. Wigderson, 'Constructing a Maximum Matching is in Random NC,' Combinatorics, 6( 1), ( 1986) pp. 35-48. Google ScholarDigital Library
- KUW2.R.M. Karp. E. Upfal, and A. Wigderson, 'Are Search and Decision Problems Computationally Equivalent?' Seventeenth Annual Symp. on Theory of Computing, (1985). Google ScholarDigital Library
- KVV.D. Kozen, U.V. Vazirani, and V.V. Vazirani, 'NC Algorithms for Comparability Graphs, Interval graphs, and Testing for Unique Perfect Matching,' Fifth Annual Foundations of Sofhvare Technology and Theoretical Computer Science Conference, (1985), to appear in Theoretical Computer Science. Google ScholarDigital Library
- Lo1.L. Lovasz, 'On Determinants, Matchings and Random Algorithms,' Fundamentals of Computing Theory, edited by L.Budach, Akademia-Verlag, Berlin, (1979).Google Scholar
- Lo2.L. Lovasz, 'Combinatorial Problems and Exercises, ' Akademiai Kaido, Budapest, and, North-Holland, Amsterdam, (1979).Google Scholar
- LP.L. Lovasz and M. Plummer, Matching Theory, Academic Press, Budapest, Hungary, (in press).Google Scholar
- MV.S. Micali and V.V. Vazirani, 'An 0 (4 IVI IE I) Algorithm for Finding Maximum Matching in General Graphs,' Twenty First Annual IEEE Symp. on the Foundations of Computer Science, (1980), pp 17-27.Google Scholar
- Pa.V. Pan, 'Fast and Efficient Algorithms for the Exact Inversion of Integer Matrices, Fifth Annual Foundations of Software Technology and Theoretical Computer Science Conference, (1985). Google ScholarDigital Library
- PY.C.H. Papadimitriou and M. Yannakakis, 'The Complexity of Restricted Spanning Tree Problems, JACM, Vol 29, No. 2, (1982), pp. 285-309. Google ScholarDigital Library
- RV.M.O. Rabin and V.V. Vazirani, 'Maximum Matching in General Graphs Through Randomization,' submitted for publication.Google Scholar
- SV.M. Santha and U.V. Vazirani, 'Generating Quasi-Random Sequences from Semi-Random Sources', JCSS, Vol 33, No 1, Aug 1986, pp. 75-87. Google ScholarDigital Library
- Sc.J. T. Schwartz, 'Fast Probabilistic Algorithms for Verification of Polynomial Identities,' JACM, 27(4), 701-717 (1980). Google ScholarDigital Library
- Tu.W.T. Tutte, 'The Factorization of Linear Graphs, ' J. London Math. Sot. 22, (1947), pp. 107-111.Google ScholarCross Ref
- Va.L.G. Valiant, 'The Complexity of Computing the Perimanent', Theoretical Computer Science 8 (1979) pp. 189-201.Google ScholarCross Ref
- ValVaz.L.G. Valiant and V.V. Vazirani, 'NP is as Easy as Detecting Unique Solutions,' Theoretical Computer Science, 47 (1986), pp. 85-93. Google ScholarDigital Library
- Vaz.U.V. Vazirani, 'Randomness, Adversaries and Computation', Ph.D. Dissertation, University of California, Berkeley (1986). Google ScholarDigital Library
- VV.U.V. Vazirani and V.V. Vazirani, 'The Two-Processor Scheduling Problem is in Random NC,' Seventeenth Annual Symp. on Theory of Computing, (1985), pp. 11-21. Google ScholarDigital Library
Index Terms
- Matching is as easy as matrix inversion
Recommendations
Generalized matrix inversion is not harder than matrix multiplication
Starting from the Strassen method for rapid matrix multiplication and inversion as well as from the recursive Cholesky factorization algorithm, we introduced a completely block recursive algorithm for generalized Cholesky factorization of a given ...
Structures preserved by matrix inversion
In this paper we investigate some matrix structures on $\cee^{n\times n}$ that have a good behavior under matrix inversion. The first type of structure is closely related to low displacement rank matrices. Next, we show that for a matrix having a low ...
Scalable matrix inversion using MapReduce
HPDC '14: Proceedings of the 23rd international symposium on High-performance parallel and distributed computingMatrix operations are a fundamental building block of many computational tasks in fields as diverse as scientific computing, machine learning, and data mining. Matrix inversion is an important matrix operation, but it is difficult to implement in today'...
Comments