Interactive and probabilistically checkable proofs in real number models

• Applicant: Professor Dr. Klaus Meer
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 195586166

The project analyzes the strength of interactive protocolsand probabilistically checkable proofs in the frameworkof real number models of computation.In those scenarios, a particular randomized algorithm calledverifier tries to verify the correctness of a mathematicalstatement. Different rules specifying how the verifier should workare important. Interactive proofs allow a communicationbetween the verifier and a so called prover; the latter in principle is unrestricted with respect to its computationalpower. Following a protocol verifier and prover exchange information.At the end the verifier has to come up with the decision whetheror not it accepts the information provided by the prover as correct proof of the statement under consideration.In contrast, probabilistically checkable proofs do not allowfor any interaction. Instead, the verifier gets a potentialproof and then within polynomial randomized time has to come upwith its decision.The central question for the project is for which problemsa verifier in the above scenarios succeeds inmaking the correct decision in relation to the resourcesit is allowed to use.A main goal is to characterize important real numbercomplexity classes by classifying verifiers that can deal with problems of the respective classes. That waya deeper understanding of those classes is aimed for.Another aspect of this approach is the study of efficient approximation algorithms. Knowledge about the(non-)existence of such algorithms might be extractablefrom such characterizations. This is ofimportance in relation to a practical treatment of computationally difficult problems.

• DFG Programme: Research Grants