2006
Smoothed Analysis of Algorithms and Heuristics
Spielman D, Teng S. Smoothed Analysis of Algorithms and Heuristics. 2006, 274-342. DOI: 10.1017/cbo9780511721571.010.Peer-Reviewed Original ResearchSmoothed analysisAnalysis of algorithmsNumber of iterationsMathematical programmingCombinatorial optimizationComputational geometryApproximation algorithmIterative algorithmApproximation ratioRandomized algorithmDiscrete inputsPerturbation modelRandom bitsScientific computingError probabilityTime complexityCompetitive ratioNumber of callsAlgorithmOnline algorithmNumber of bitsOpen questionHeuristicsIterationComputation
2001
Min–max-boundary domain decomposition
Kiwi M, Spielman D, Teng S. Min–max-boundary domain decomposition. Theoretical Computer Science 2001, 261: 253-266. DOI: 10.1016/s0304-3975(00)00143-2.Peer-Reviewed Original ResearchDistributed-memory parallel computersK-SubgraphParallel computing techniquesDomain decompositionAmount of computationMin-maxComputing techniquesParallel computersLarge communicationGraph decompositionNumber of edgesSubgraphsAlgorithmPartitionComputerComputationCommunicationSpecial caseDecomposition amountGraph GMemory loadBoundary sizeDecompositionNumerical system
1998
Min-Max-Boundary Domain Decomposition
Kiwi M, Spielman D, Teng S. Min-Max-Boundary Domain Decomposition. Lecture Notes In Computer Science 1998, 1449: 137-147. DOI: 10.1007/3-540-68535-9_17.Peer-Reviewed Original ResearchDistributed-memory parallel computersParallel computing techniquesDomain decompositionAmount of computationComputing techniquesSubgraphs G1Parallel computersMemory requirementsPartitioning problemGraph decompositionNumber of edgesMin-maxAlgorithmSubgraphsPartitionComputerComputationCommunicationRequirementsSpecial caseDecomposition amountGraph GBoundary sizeDecompositionNumerical systemModels of computation in coding theory
Spielman D. Models of computation in coding theory. 2013 IEEE Conference On Computational Complexity 1998, 120. DOI: 10.1109/ccc.1998.694597.Peer-Reviewed Original Research
1996
Highly fault-tolerant parallel computation
Spielman D. Highly fault-tolerant parallel computation. 2011 IEEE 52nd Annual Symposium On Foundations Of Computer Science 1996, 154-163. DOI: 10.1109/sfcs.1996.548474.Peer-Reviewed Original ResearchParallel computationComputational devicesReed-Solomon codesFault-tolerant computationError-correcting codesSmall overheadWrong outputValid inputsW processorsProcessorsMachineComputationSequential timeFaulty machineConstant factorCodeConstant probabilityFault-tolerant machineOverheadTime stepInputDevicesFailure probabilityOutputModel