A taxonomy of problems with fast parallel algorithms

References

Page 1

	Year	Citations
Combinatorial Optimization: Algorithms and Complexity. David Johnson, Christos H. Papadimitriou, Kenneth Steiglitz American Mathematical Monthly Mathematical ProgrammingEngineeringAlgorithm DesignLocal Search HeuristicsCombinatory Analysis	1984	6K
A new polynomial-time algorithm for linear programming Narendra Karmarkar COMBINATORICA Mathematical ProgrammingEngineeringOptimization ProblemComputational ComplexityComputer Science	1984	4.8K
Combinatorial optimization:Algorithms and complexity L. R. Rabiner IEEE Transactions on Acoustics Speech and Signal Processing EngineeringCombinatorial ProblemComputational ComplexityComputer ScienceDiscrete Mathematics	1984	3.6K
Fast Probabilistic Algorithms for Verification of Polynomial Identities Jacob T. Schwartz Journal of the ACM	1980	1.7K
Alternation Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer Journal of the ACM	1981	1.2K
The Synthesis of Two-Terminal Switching Circuits Claude E. Shannon Bell System Technical Journal Circuit ComplexityInverse ProblemElectrical EngineeringLogic SynthesisEngineering	1949	758
Computational Complexity of Probabilistic Turing Machines John Gill SIAM Journal on Computing Partial FunctionEngineeringAbstract ComplexityKolmogorov ComplexityAutomated Reasoning	1977	694
Completeness classes in algebra Leslie G. Valiant	1979	477
On uniform circuit complexity Walter L. Ruzzo Journal of Computer and System Sciences Circuit ComplexityEngineeringComputational ComplexityCommunication ComplexityTime Complexity	1981	433
Fast Parallel Matrix Inversion Algorithms L. Csanky SIAM Journal on Computing Numerical AnalysisEngineeringSame Growth RateParallel Complexity TheoryParallel Processing	1976	399

Page 1