Mathematics Problem Archive

Suppose $G$ and $H$ are Cayley, or vertex-transitive, expanders on the same number of vertices and can be matched with asymptotically vanishing edge d...

If $G$ is a finite vertex-transitive expander, must every almost automorphism of $G$ be close to an automorphism?...

For a locally convergent sequence $(G_n)$ of bounded-degree integer-labeled graphs, does the normalized rank modulo $p$ of the adjacency matrix conver...

Let $(G_n)$ be a locally convergent graph sequence and let $\mu_n$ be the probability distribution of the roots of the chromatic polynomial of $G_n$. ...

Let $G$ be a $d$-regular Cayley graph with spectral measure $\mu$. Is $\mu$ a weak limit of spectral measures of finite $d$-regular graphs?...

Let $\Gamma$ have property (T), and let $(G_n)$ be a sofic approximation of a Cayley graph of $\Gamma$. Can $(G_n)$ be changed by an asymptotically va...

Can free spanning forests be used to prove basic properties of the first $L^2$ Betti number, such as multiplicativity upon passage to a finite-index s...

Does every infinite Cayley graph $G$ admit a $G$-invariant proper coloring with $\chi(G)$ colors?...

Let $X$ be the space of $k$-regular Cayley graphs with the local-convergence topology and let $T\subset X$ be the closed subset of transient graphs. I...

Let $G$ be a bounded-degree expander, or strongly ergodic, graphing that weakly contains a finite graph $H$. Does $G$ factor onto $H$?...

Does every higher-rank semisimple real lattice have rank gradient zero?...

Does every residually finite property-(T) group have rank gradient zero?...

Can the Euclidean minimum spanning tree (MST) of $n$ points in $\mathbb{R}^d$ be computed in time close to the lower bound of $\Omega(n \log n)$?...

Is the Yao-Yao Graph a $t$-spanner for constant $t$? A geometric graph is a $t$-spanner (or just a spanner) if, for every pair of nodes, the shortest ...

Can one decide in deterministic polynomial time whether an integer $n$ is squarefree?...

Let $C_{10}$ find $x$ satisfying $x^e\equiv a\pmod n$ under $\gcd(e,\varphi(n))=\gcd(a,n)=1$. Is complete integer factorization randomized polynomial-...

Given a prime $p$ and degree $d$, can an irreducible polynomial of degree $d$ over $\mathbb{F}_p$ be constructed in deterministic polynomial time?...

Is complete integer factorization deterministically polynomial-time reducible to discrete logarithms modulo composites?...

Is complete integer factorization deterministically polynomial-time reducible to computing $\varphi(n)$?...

Given $a,b$ and a prime $p$ with nonsingular curve $y^2=x^3+ax+b$, can a point on the curve modulo $p$ be found in deterministic polynomial time?...

Does there exist a constant $c$ for which one can find in deterministic polynomial time a nonzero lattice vector of length at most $n^c$ times the min...

Given $f\in\mathbb{Q}[x]$, can the degree of its splitting field, equivalently the order of its Galois group, be computed in deterministic polynomial ...

Given $d\in\mathbb{N}$, can the class number $h(-d)$ of binary quadratic forms of discriminant $-d$ be computed in deterministic polynomial time?...

Can $\gcd(a,b)$ be computed in the parallel complexity class $NC$?...

Can two positive integers $a,b$ be multiplied using $O(\log(ab))$ bit operations?...

Determine the least positive integer $n_1$ and the greatest negative integer $n_2$ for which a $D(n_i)$-quintuple exists....

If $a$ and $b$ are two positive integers with $a<b$ and $R(a)=R(b)$ then there is a prime $p$ with $a< p< b$....

Let $\tau\in\mathbb{C}$ have positive imaginary part. Assume that $\tau$ is not quadratic. Set $q=e^{2i\pi\tau}$. Then at least $4$ of the $5$ numbers...

For each integer $n\ge 1$ there exists a positive constant $c(n)$ such that, for any algebraic subvariety $V$ of $\mathbb{G}_m^n$ which is defined ove...

There exists a positive constant $c$, depending only on $A$ and $\mathcal{L}$, such that for any $P\in A(\overline{\mathbb{Q}})$ which has infinite or...

Let $n \ge 2$. Denote by $\mathrm{ZH}_n$ the set of real numbers $\xi$ with the following property: there exists $c_1(\xi) >0$ and $c_2(\xi)>0$ such t...

Let $(n_i)_{i\ge 0}$ be an increasing sequence of positive integers. Assume there is a prime number $p$ such that the power series $$ \sum_{i\ge 0}z^{...

Given an elliptic curve $E/\mathbb{F}_q$ and $P\in E(\mathbb{F}_q)$, characterize maps or isogenies $\psi:E\to E'$ for which $\psi(P)$ can be evaluate...

Find bilinear structures that are useful for cryptographic constructions....

Find orders $\mathcal{O}$ whose Picard groups contain $\mathbb{Z}/\ell$, admit compact element representations, and allow group composition in $O(\log...

Make the proposed realization of existing finite-field discrete-logarithm systems inside class groups explicit for practical systems....

Determine whether Weil descent compromises the security of the proposed class-group realization of finite-field discrete-logarithm systems....

Explicitly construct global algebras or Brauer classes with prescribed local data, especially when the local splitting fields are dihedral....

Determine whether natural de Rham cup-product pairings can be used to improve zeta-function computations....

Remove the imaginary-hyperelliptic and $p\ne2$ restrictions from the complexity bound stated in the slides....

Test and analyze whether deleting extra points and fixing the lift $x\mapsto x^p$ improves Frobenius lifts for nondegenerate curves....

Develop the higher-dimensional analogue of the nondegenerate-curve Frobenius-lift method....

Find useful deformations of nondegenerate curves together with easy starting matrices for Frobenius computation....

Work out effective zeta-function computations for nondegenerate surfaces in toric threefolds....

Factor $N=p^rq^s$ with $r\approx s$ using fewer known bits of the factors than existing methods require....

Develop methods to factor an integer when the known bits of its factors are nonconsecutive....

For large $N$, efficiently find the required short five-term geometric progressions modulo $N$ that avoid first- and second-order recurrence, thereby ...

Study the distribution of group structures $E(\mathbb{F}_q)$ as elliptic curves $E/\mathbb{F}_q$ vary; in particular, determine the correct nonuniform...

Is the exponent $e_q(E)$ of $E(\mathbb{F}_q)$ typically close to $q$?...

How often is the group of a random elliptic curve over $\mathbb{F}_q$ cyclic?...