Information-Theoretic Cryptography
Statements tagged with the information-theoretic area. This is a generated view, not a home directory – a statement can belong to several areas at once. See all statements for the full index, or the schema for what each column means.
| Status | Statement | Tags |
|---|---|---|
|
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) | |
|
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) | |
|
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) | |
|
Polynomial Compatibility Conjecture Open in the inverse-polynomial regime. Proved for exponentially small influences by the paper that introduced it, and false for influences at or above 1/(2d); everything between is what the quantum separations depend on. 5 open |
qromassumptionresearch-opennew-idea (ai) |
No matching items