Mathematics Problem Archive

For an infinite $d$-regular Ramanujan graph, does random-walk neighborhood sampling converge to the $d$-regular tree?...

For each $d\geq3$, does the independence ratio of a uniformly random $d$-regular graph converge in probability as the number of vertices tends to infi...

Let $G$ be an infinite Cayley graph of a group that is not virtually cyclic. Prove that there exists $p<1$ for which Bernoulli $p$-edge percolation on...

Does every infinite connected Cayley graph admit an invariant random perfect matching?...

For a nonamenable group $\Gamma$, does the Bernoulli shift $\{0,1\}^{\Gamma}$ factor onto $\{0,1,2\}^{\Gamma}$?...

Can every $d$-regular graphing without multiple edges be properly edge-colored by $d+1$ colors?...

Does every $n$-vertex planar graph have a 3D grid drawing with $O(n)$ volume? A 3D grid drawing of a graph is a placement of the vertices at distinct ...

Does every planar graph have $O(1)$ queue-number? A queue layout of a graph consists of a linear order of the vertices and a partition of the edges in...

For a full-rank integer lattice, is finding a nonzero vector of minimum Euclidean norm NP-hard?...

Under the promise that $b^2-4ac$ is not a square, is deciding whether $ax^2+bxy+cy^2+dx+ey+f=0$ has an integral solution NP-hard?...

Is the same binary quadratic Diophantine solvability problem NP-hard under randomized reductions?...

Develop a fast algorithm to compute the Tate–Lichtenbaum pairing $T_n$....

Factor $N=pqr$ from fewer known bits of its prime factors....

Given integers $n$ and a prime power $q$, construct, when possible, an elliptic curve $E/\mathbb{F}_q$ with $\#E(\mathbb{F}_q)=n$....

Speed up the computation of cryptographic pairings....

Give the cited pairing-based signature constructions and their security proofs without relying on distortion maps....

Construct efficient pseudorandom generators from ideal-lattice problems....

Construct efficient digital-signature schemes from ideal-lattice problems....

Base cryptographic constructions directly on worst-case hardness assumptions from algebraic number theory....

Construct an efficient ideal-lattice version of Regev's quantum-SVP-based cryptosystem....

Prove that every bounded-degree transient hyperbolic graph contains a transient subtree....