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
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
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