Miscellaneous (problem 2)

Let $X,Y \in \{0,1\}$ have joint distribution

p_{X,Y}(x,y) = \begin{bmatrix} \frac{1}{2}(1- \alpha) & \frac{1}{2}\alpha \\ \frac{1}{2}\alpha & \frac{1}{2}(1- \alpha) \\ \end{bmatrix},

then $I(X;Y) = 1 - h(\alpha)$ for $0 \leq \alpha \leq 1/2$ where $h(\alpha) \triangleq -\alpha \log_2 \alpha - (1 - \alpha) \log_2 (1 - \alpha).$ Note that $I(X;Y) \triangleq D(p_{X,Y} || p_X p_Y)$ .

The conjecture, often referred to as the “Courtade-Kumar Conjecture” or the “Most Informative Function Conjecture”, is the following. Let $(X_i, Y_i)$ for $1 \leq i \leq n$ be i.i.d. $\overset{d}{=} (X,Y)$ , then

I(f(X_1^n); Y_1^n) \leq 1 - h(\alpha)

for any function $f:\{0,1\}^n \rightarrow \{0,1\}.$ We note that there is prior work on special cases.

Equivalent formulations 8Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Miscellaneous (problem 2)
Does HHL break crypto? (See recent paper.)

Understand condition number over $\mathbb C$ of matrix of coefficients of $f_1, f_2, \dots$ (original equations), $xf_1, xyf_2, \dots$ (only monomial terms).
source: AimPL: Quantum algorithms for analysis of public-key crypto (posed by Michele Mosca)
Miscellaneous (problem 2)
Among all Polish ${\mathbb{Q}}$ -vector spaces ordered by continuous ${\mathbb{Q}}$ -linear injectability, is there anything between $\ell^1({\mathbb{Q}})$ and ${\mathbb{R}}$ ?
source: AimPL: Descriptive graph theory
Miscellaneous (problem 2)
Develop a heuristic for twisted moments, e.g.
$\int_0^T \left( \frac{m}{n}\right)^{it} |\zeta(\tfrac{1}{2}+it)|^{2k}\,dt.$
source: AimPL: Moments of zeta and correlations of divisor sums (posed by M. Radziwill)
Miscellaneous (problem 2)
\begin{enumerate} \item What are the automorphisms of cohesive powers $\prod_C F$ for finite algebraic extensions $F$ of $\mathbb Q$ ? \item Are there any that do not arise from automorphisms of $F$ ? \end{enumerate}
source: AimPL: Definability and decidability problems in number theory (posed by Rumen Dimitrov)
Miscellaneous (problem 2)
Prove the H"aggstr"om-Pemantle conjecture that the two-type Richardson model has almost surely a single surviving type for $\lambda_1\neq\lambda_2$ .
source: AimPL: First passage percolation (posed by Christopher Hoffman)
Miscellaneous (problem 2)
Let $\mathcal{C}$ be a symmetric tensor category. Develop duality theory for polynomial functors. Can this be applied to representations of symmetric groups?
source: AimPL: Finite tensor categories: their cohomology and geometry (posed by Guillermo Sanmarco)
Miscellaneous (problem 2)
Are there examples of pairs $(n,k)$ with $n>k\ge2$ such that for any parallelizable $n$ manifold, there exists a $k$ -plane field $\mathcal{D}\subset TM$ with maximal growth vector?
source: AimPL: Engel structures
Miscellaneous (problem 2)
Let $B_w\in$ SBim $_n$ be the indecomposable Soergel bimodule associated to $w\in S_n$ . Compute Ext $_{R-R \text{ bimod}}(B_v,B_w)$ and develop its diagrammatics.
source: AimPL: Algebra, geometry, and combinatorics of link homology

References

Primary source

AimPL: Entropy power inequalities (posed by Thomas Courtade)

InAIM Problem Lists

Posted 1 month ago

Miscellaneous (problem 2)