2014
An efficient parallel solver for SDD linear systems
Peng R, Spielman D. An efficient parallel solver for SDD linear systems. 2014, 333-342. DOI: 10.1145/2591796.2591832.Peer-Reviewed Original ResearchSystem of equationsEfficient parallel solverLinear systemsLinear equationsLow-stretch spanning treesSDD matrixDominant matricesParallel solverInput matrixSparse matricesFast algorithmPolylogarithmic timeParallel algorithmEquationsFirst parallel algorithmSpanning treeLinear workAlgorithmMatrixSparsifiersSolverInverseSystem
2004
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Spielman D, Teng S. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. 2004, 81-90. DOI: 10.1145/1007352.1007372.Peer-Reviewed Original Research
2000
Alternation in interaction
Kiwi M, Lund C, Spielman D, Russell A, Sundaram R. Alternation in interaction. Computational Complexity 2000, 9: 202-246. DOI: 10.1007/pl00001607.Peer-Reviewed Original ResearchInteractive proof systemsProof systemOne-round proof systemsPolynomial hierarchyMulti-prover interactive proof systemsFirst exact characterizationCheckable proofsProversVerifierSystem capturesMain contributionLimited randomnessQuantifier alternationsNPsRepetition techniqueCommunicationLanguageSystemHierarchyExact characterizationRandomnessTraditional studiesSetProof