Model: standard

Statements with model: standard. This page only exists because at least one statement currently uses this value – if you add a statement with a new model value not listed under Problems, copy this page as the starting point for its facet page (see CONTRIBUTING.md).

Status	Statement	Tags
	Best-first search trees Open, with no bound of any kind proved for the best-first algorithm on any class of query distributions. Exact optimality is already refuted by the paper’s own exhaustive search, so only the approximation ratio remains, and a workload on which greedy is off by an unbounded factor would settle it. 5 open	standardtight-boundresearch-opennew-idea (ai)
	Optimal martingale gap finders Open for small mu. Settled when mu is bounded away from zero, where the Cleve-Impagliazzo gap finder already gives the conjectured product; for general mu the known bound is a factor mu short and the paper states it does not know the answer. 5 open	standardlower-boundresearch-opennew-idea (ai)
	Generalized mirror theory The fully generalized Mirror Theory bound for arbitrary cycle-consistent multi-graphs up to the information-theoretic limit is open; current techniques only reach component size O(N^{1/4}). 2 open	standardlower-boundresearch-opennew-idea (ai)
	Level-optimal beyond disjunctions Open beyond disjunctive queries, and the authors state it as a conjecture without naming the broader class – identifying one is part of the problem. Proved for every distribution supported on disjunctions, where the log n factor is also shown necessary. Wide open for conjunctive queries, where the paper’s proof technique demonstrably fails. 5 open	standardtight-boundresearch-opennew-idea (ai)
	Logarithmic independence implies PRP Open at independence order log n. The same implication is refuted at order 4 and at every constant order by an explicit construction; the logarithmic-order form is untouched, and no unconditional proof of it can be expected. 5 open	standardcharacterizationresearch-opennew-idea (ai)
	RBE needs Ω(log n) updates Open. The number of updates for fixed-update-time schemes with polylogarithmic public parameters is known to lie between Omega(log n / log log n) and O(log n); this statement picks the upper endpoint, and the paper’s own tool is proved tight, so it cannot decide the question. 5 open	standardlower-boundresearch-opennew-idea (ai)
	No 2-element split NILPs Open: whether a 2-element split NILP can be statistically sound against affine provers for any hard relation generator, the information-theoretic core of whether Groth16’s 3-element proof size is optimal. 2 open	standardimpossibilityresearch-opennew-idea (ai)
	OWF minimality, non-black-box reductions Open when the classical security implication is not witnessed by a black-box reduction between the two games. Settled affirmatively whenever it is, for uniform and non-uniform quantum adversaries alike, with the implementation reduction left arbitrary. 5 open	standardequivalenceresearch-opennew-idea (ai)
	Censoring can only hurt Open. The censored side is proved at essentially optimal round count with matching lower bounds; what is missing is the transfer of any such bound to uncensored AES at the same round count. 5 open	standardlower-boundresearch-opennew-idea (ai)
	RBE update bound, key-dependent schedules Open exactly when the update schedule may depend on the sampled public keys, which is the standard on-demand completeness notion. Proved when the schedule is any fixed function of registration times (Theorem 4.1) or of the registered identity names and the CRS (Theorem 4.12). 5 open	standardlower-boundresearch-openadaptation (ai)