Form: tight bound

Statements with form: tight-bound. This page only exists because at least one statement currently uses this value – if you add a statement with a new form 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)
	Split-source decomposition Open for a query budget of two or more: whether a random oracle decomposes into bit-fixing mixtures when the advice is produced by two sources that never communicate. Proved and tight at q = 0, and proved at q = 1 under an extra hypothesis. 4 open	romtight-boundresearch-opennew-idea (ai)
	6-round Feistel indifferentiability Whether 6-round Feistel is fully indifferentiable from a random permutation is open, bridging the proven r=5 attack and the proven r>=8 construction. 2 open	othertight-boundresearch-opennew-idea (ai)
	Groth16 optimality (pure GGM) Open: whether every sound, non-interactive, publicly verifiable pairing-based argument in the pure generic group model needs at least three group elements, matching Groth16. 2 open	ggmtight-boundresearch-opennew-idea (ai)
	LHL extraction, public seed Proven, and the statement is now formalized in Lean with an AI match check: the public-seed bound holds with a concrete constant, but the proof itself is still only informal (PDF), unreviewed, and unformalized. 4 open	romtight-boundresearch-solvedadaptation (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)
	3-way collision, oblivious sequential curve Open: closing the factor-root-S gap between the proved oblivious lower bound and a matching table-and-hunt algorithm for finding a 3-way collision with an oblivious sequential branching program. 2 open	romtight-boundresearch-openadaptation (ai)
	Tight \(k\)-collision time-space tradeoff The exact tight time-space tradeoff for k>=3 collisions under preprocessing is open; only the k=2 case has a matching upper and lower bound. 2 open	romtight-boundresearch-opennew-idea (ai)