On memoryless provers and insincere verifiers

DOI10.1080/09528130903119328zbMath1183.68592OpenAlexW1965051705MaRDI 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 walkChebyshev's inequalitybinary Boolean constraintsProver-Verifier modeltype 3 certificates

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

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

This page was built for publication: On memoryless provers and insincere verifiers