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
1994
The power of adaptiveness and additional queries in random-self-reductions
Feigenbaum J, Fortnow L, Lund C, Spielman D. The power of adaptiveness and additional queries in random-self-reductions. Computational Complexity 1994, 4: 158-174. DOI: 10.1007/bf01202287.Peer-Reviewed Original Research