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)
	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)
	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)
	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)