Optimal search with checkable proofs.
Find the fewest questions needed to identify an answer, even when some replies are wrong. Then give an independent checker a proof that the question count is optimal.
An answer you can check.
A certified learning problem
Ask fewer questions, even with wrong answers.
An adaptive learner chooses its next question from earlier answers. A fixed design chooses every question in advance.
Exact formulas for the manuscript’s 16-hypothesis, four-variable monotone-conjunction example with all 16 Boolean inputs allowed. They do not describe arbitrary search problems. Source: the certified concept-learning example and isolation-family proposition in the Theory of Computing Systems manuscript.
What the study shows.
Find a result. Verify its proof.
A producer builds a strategy and a matching lower-bound certificate. An independent verifier checks that the strategy succeeds and that no better query count is possible for the declared model.
Stronger witnesses cover more cases.
Isolation witnesses raise compact coverage from 25 to 69 of 101 sweep tables. Combined portable and expanded evidence certifies 302 of 303 sweep cells; one remains unresolved.
Adapt the next question to the answer.
For four-variable monotone conjunctions with up to two corrupted answers, the exact adaptive cost is 14 queries. A fixed non-adaptive design needs 20.
Scope & details.
Proof-Carrying Optimality for Finite Identification under Bounded Adversarial Answer Errors
DOI 10.21203/rs.3.rs-11052076/v1CC BY 4.0
The guarantees concern explicit finite behavior tables and their declared queries. Proof construction and proof size remain practical costs. The 256-table additional evaluation is a separate population and is not pooled with the original sweep.
Read the abstract
Exact learning from queries is a model of machine learning in which a learner actively identifies an unknown hypothesis. We study its finite, realizable form when queries come from a declared alphabet and an adversary may corrupt a bounded number of answers. For this setting we develop independently checkable certificates of exact worst-case query complexity. Portable certificates combine a noiseless strategy with a lower witness to prove an affine identity for every error budget, without expanding the corrupted-answer game. An isolation witness consists of classes on which each permitted probe agrees on all but at most one class. We prove its exact value for arbitrary residual error budgets and match it to a known robustification bound. Expanded strategy and adversary certificates handle individual budgets; separate distance and rational-dual certificates establish non-adaptive optima. Isolation witnesses increase compact coverage from 4 to 9 of 15 primary tables and from 25 to 69 of 101 sweep tables. Combined evidence certifies 302 of 303 sweep cells at budgets zero, one, and two. An additional 256-table evaluation increases compact coverage from 71 to 161; constructed certificates reach 256 classes. As a learning example, identifying a monotone conjunction of four variables with two corrupted answers requires exactly 14 adaptive queries versus 20 non-adaptive queries.
Citation
@unpublished{lex2026proof,
title={Proof-Carrying Optimality for Finite Identification under Bounded Adversarial Answer Errors},
author={Lex, Vikram},
year={2026},
doi={10.21203/rs.3.rs-11052076/v1},
url={https://doi.org/10.21203/rs.3.rs-11052076/v1},
note={Manuscript under review at Theory of Computing Systems}
}