296 problems
Problem. Prove or disprove that one-way functions exist.
Problem. Prove or disprove that one-way permutations exist.
For every integer , every Boolean function , and every noise parameter , let be uniformly distributed on , let…
For every integer , energy , and noise standard deviation , let satisfy for all , and let the signa…
Consider the real additive white Gaussian noise sequence channel … where the noise coordinates are independent . An code has equiprobable messages,…
The Hellinger conjecture. Under these assumptions,
Prove or disprove that every language decidable by a probabilistic Turing machine using O(log n) workspace, polynomial time, and bounded two-sided error is decidable by a determini…
2403.10985 introduced the notion of reversible capacity of a graph and showed that it is at most the Shannon capacity. It is conjectured there that the two values are equal. At the…
For every group and all finite nonempty subsets , where , one has…
The supplied sources identify two standing problems for down-up walks on matroids: Alaniz Pintos's degree-one conjecture, concerning the classification of extremal eigenfunctions o…
For every integer , every balanced Boolean function satisfying , and every correlation , one has … where…
For every pair of sequences of finite graphs and , if and , must…
For and , let denote the multiset of all length- subsequences of a word , counted with multiplicity. Define to be the least…
For every , does there exist a constant , independent of the dimension and of the mixing distributions, such that for every and every pair of pro…
Determine the set of all normalized graph parameters on finite graphs such that ,…
For every artificial-intelligence mechanism , its certainty and scope satisfy a universal tradeoff of the form , where is a constant independent…
Let be independent Bernoulli random variables with parameters , let , and write . Determine t…
For every integer , let be a centered Gaussian vector satisfying for every . Let be independent standar…
Let independent arms have distributions , with and a unique optimal arm . Write for ,…
Let and be independent identically distributed real-valued random variables with a common log-concave density and finite differential entropy. Define …
Let be the class of admissible waveforms without a cyclic prefix, let denote conventional OFDM, and let…
Given arbitrary nonempty families of finite-dimensional quantum channels and , characterize the optimal asymptotic Stein exponent for discriminating…
Determine the exact average-error Shannon capacity Cdel(d), in bits per input bit, of the binary deletion channel for every real d with 0<d<1. Each input bit is independently delet…
Let be jointly Gaussian with and correlation coefficient . The exact common information of is conjectured to satisfy…
This entry tracks Eskenazis–Nayar–Tkocz cube-projection entropy conjecture. It confirms the proposed extremal directions over a broad high-dimensional range. Latest development The…