2005
Improved Smoothed Analysis of the Shadow Vertex Simplex Method
Deshpande A, Spielman D. Improved Smoothed Analysis of the Shadow Vertex Simplex Method. 2005, 349-356. DOI: 10.1109/sfcs.2005.44.Peer-Reviewed Original ResearchSmoothed complexityShadow vertex simplex methodParameter of perturbationNumber of constraintsSmoothed analysisGeometric resultsNumber of variablesLinear programVertex methodLinear programmingSimple proofSimplex methodRunning timeMultiplicative factorExponentSpielmanPolytopeProofComplexityVerticesPerturbations
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