Chicago Journal of Theoretical Computer Science

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.

  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
[back] Volume 2017 [back] Published articles
[CJCTS home]

Janos Simon