### Volume 2017 Abstracts

1. Quantum Algorithms for Matrix Products over Semirings by François Le Gall, and Harumichi Nishimura
May 11, 2017

In this paper we construct quantum algorithms for matrix products over several algebraic structures called semirings, including the (max,min)-matrix product, the distance matrix product and the Boolean matrix product. In particular, we obtain the following results.

• We construct a quantum algorithm computing the product of two $n\times n$ matrices over the (max,min) semiring with time complexity $O(n^{2.473})$. In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity $O(n^{2.687})$.
• We construct a quantum algorithm computing the $\ell$ most significant bits of each entry of the distance product of two $n\times n$ matrices in time $O(2^{0.64\ell} n^{2.46})$. In comparison, the best known classical algorithm for the same problem, by Vassilevska and Williams (STOC'06) and Yuster (SODA'09), has complexity $O(2^{\ell}n^{2.69})$.
• The above two algorithms are the first quantum algorithms that perform better than the $\tilde O(n^{5/2})$-time straightforward quantum algorithm based on quantum search for matrix multiplication over these semirings. We also consider the Boolean semiring, and construct a quantum algorithm computing the product of two $n\times n$ Boolean matrices that outperforms the best known classical algorithms for sparse matrices.
2. -

3. Unique reconstruction threshold for random jigsaw puzzles by Rajko Nenadov, Pascal Pfister and Angelika Steger
June 30, 2017

A random jigsaw puzzle is constructed by arranging $n^2$ square pieces into an $n \times n$ grid and assigning to each edge of a piece one of $q$ available colors uniformly at random, with the restriction that touching edges receive the same color. We show that if $q = o(n)$ then with high probability such a puzzle does not have a unique solution, while if $q \ge n^{1 + \varepsilon}$ for any constant $\varepsilon > 0$ then the solution is unique. This solves a conjecture of Mossel and Ross (Shotgun assembly of labeled graphs, arXiv:1504.07682).

Volume 2016 Abstracts
Volume 2017 Published articles

Janos Simon