37 problems

Omega linear-complexity conjecture.

Let $\mathcal{F}'$ be the modified oracle using the truncated CCL process with $l=\log N$, an oracle $\mathsf{RND}_3$ making $k$ calls to a permutation oracle, and parameters as de…

Let $S_N$ be the symmetric group on $N$ elements. A random cyclus is a uniformly random permutation in $S_N$ with a prescribed cycle structure, as obtained by conjugating a fixed f…

Let $T_{r,\alpha}$ be the generalized Gauss continued-fraction map, and let $\lambda(r,\alpha)$ be the Lyapunov exponent of the orbit of $x_0\in[0,1]$ under $T_{r,\alpha}$. Let…

Let $n,d,r\in\mathbb{N}$, and consider distributions on $\mathbb{F}_2^n$ generated by distributions of bounded $\operatorname{rank}_d\leqslant r$. The sampling distance is measured…

For powers-of-two moduli $2^k$, consider the modular Ackermann map $A_{2^k}(m,n)$ and its output distribution on $\mathbb Z_{2^k}$ as the recursion level $m$ varies. Hierarchy mixi…

Expected exponential linear complexity symmetry gap conjecture. The difference $E_N^{lin-exp}-E_N^{lin-exp-sym}$ is of order of magnitude $2^{N/2}$.

Expected rational complexity symmetry gap conjecture. The difference $E_N^{rat}-E_N^{rat-sym}$ is at least of order of magnitude $2^{N/2}$.

Let $E_{f,g,h}$ denote the sequence produced by the construction from three polynomials $f$, $g$, and $h$, whose pseudorandom properties are measured by the associated quantities s…

Polylogarithmic-depth symmetric PRU conjectural construction. Under the conjecture that no subexponential-time quantum algorithm can solve LWE, random quantum circuits over $n$ qub…

Translation-invariant symmetric PRU conjectural construction. Under the conjecture that no subexponential-time quantum algorithm can solve LWE, one-dimensional translation-invarian…

Extremely low-depth symmetric PRU conjectural construction. Under the conjecture that no subexponential-time quantum algorithm can solve LWE, symmetric PRUs on $n$ qudits with secu…

Symmetric PRU existence conjecture. Under the conjecture that no subexponential-time quantum algorithm can solve learning with errors (LWE), symmetric pseudorandom unitaries with s…

Let $\mathcal{S}$ be a binary sequence, and let $\lambda_{\mathcal{S}}(N)$ denote the binary logarithm of the least rational complexity of its first $N$ elements, equivalently the…

Let $p\equiv \pm1\bmod 8$ be prime, let ${\cal L}_p$ denote the Legendre sequence of modulus $p$, and let $L({\cal L}_p,N)$ be its $N$th linear complexity. Expected-deviation conje…

Let $n$ be the number of qubits, and consider random quantum circuits over these qubits in either a 1D or an all-to-all architecture. Let $d$ denote the circuit depth, and let LWE…

Legendre-symbol conjecture. The Legendre symbol can be used to construct deterministic matrices satisfying the restricted isometry property.

Golomb's conjecture. If $w$ has the R-3 property, then $w$ can be generated by an LFSR.

Radius-of-convergence conjecture. The bound $\lambda\leq 0.27$ is not the optimal radius of convergence for the generalized sticky random walk.

Legendre 2-adic-complexity conjecture.

Expansion-complexity conjecture for the four sequences. The numerical data suggests that all four sequences have expansion complexity of order of magnitude $N^{1/2}$, with the rest…

Omega correlation conjecture.

Correlation-measure conjecture for the square subsequence.

The Sato–Tate independence conjecture. For every integer $s\geq1$, the sequence $\{X_k\}_{k\geq1}$ is uniformly distributed with respect to $\mu_{ST}^{[s]}$; equivalently,

Fix $x>1$ and consider the sequence $(\{x^n\})_{n\geq 1}$ of fractional parts. Knuth's pseudorandomness conjecture. For almost all $x>1$, this sequence should be a good candidate t…