2003
Exponential algorithmic speedup by a quantum walk
Childs A, Cleve R, Deotto E, Farhi E, Gutmann S, Spielman D. Exponential algorithmic speedup by a quantum walk. 2003, 59-68. DOI: 10.1145/780542.780552.Peer-Reviewed Original ResearchQuantum algorithmsQuantum walkBlack-box settingGraph traversal problemTime quantum walkQuantum Fourier transformPrevious quantum algorithmsClassical computersQuantum computerTraversal problemContinuous-time quantum walkClassical algorithmsBox settingSubexponential timeAlgorithmic speedupQuantumAlgorithmComputerSpeedupDifferent techniquesGraphFourier transform
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 system