On memoryless provers and insincere verifiers

DOI10.1080/09528130903119328zbMath1183.68592MaRDI QIDQ3639202

K. Subramani and Vahan Mkrtchyan

Publication date: 29 October 2009

Published in: Journal of Experimental & Theoretical Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/09528130903119328

zbMATH Keywords

random walk; Chebyshev's inequality; binary Boolean constraints; Prover-Verifier model; type 3 certificates

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

Cites Work

• Symmetric space-bounded computation
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Introduction to set constraint-based program analysis
• An analysis of totally clairvoyant scheduling
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• A theory of the learnable
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• A randomized linear-time algorithm to find minimum spanning trees
• A new approach to dynamic all pairs shortest paths
• CASCADING RANDOM WALKS