[1]   Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe: The power of quantum systems on a line. In Proc. 48th FOCS, pp. 373–383. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.46]

[2]   Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe: The power of quantum systems on a line. Comm. Math. Physics, 287(1):41–65, 2009. Preliminary version at arXiv. Extended abstract in FOCS’07. [doi:10.1007/s00220-008-0710-3]

[3]   Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby: On the theory of average case complexity. J. Comput. System Sci., 44(2):193–219, 1992. Preliminary version in STOC’89. [doi:10.1016/0022-0000(92)90019-F]

[4]   Robert Berger: The undecidability of the domino problem. Memoirs of the Am. Math. Soc., 66:1–72, 1966.

[5]   Ethan Bernstein and Umesh Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921]

[6]   Alberto Bertoni, Massimiliano Goldwurm, and Violetta Lonati: The complexity of unary tiling recognizable picture languages: Nondeterministic and unambiguous cases. Fundam. Inform., 91(2):231–249, 2009. Preliminary version in STACS’07. [doi:10.3233/FI-2009-0042]

[7]   Jean-Philippe Bouchaud and Marc Mézard: Self induced quenched disorder: A model for the glass transition. J. Phys. I France, 4(8):1109–1114, 1994. Preprint at arXiv. [doi:10.1051/jp1:1994240]

[8]   David Deutsch: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Royal Society of London Series A, 400(1818):97–117, 1985. [doi:10.1098/rspa.1985.0070]

[9]   Peter van Emde Boas: The convenience of tilings. In Andrea Sorbi, editor, Complexity, Logic, and Recursion Theory, pp. 331–363. Marcel Dekker Inc, 1997.

[10]   Martin Fürer: The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). In Logic and Machines: Decision and Complexity, volume 171 of LNCS, pp. 312–319. Springer, 1984. [doi:10.1007/3-540-13331-3_48]

[11]   Hana Galperin and Avi Wigderson: Succinct representations of graphs. Inf. Control, 56(3):183–198, 1983. [doi:10.1016/S0019-9958(83)80004-7]

[12]   Daniel Gottesman and Sandy Irani: The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems, 2009. Conference version in FOCS’09. [arXiv:0905.2419]

[13]   Erich Grädel: Dominoes and the complexity of subclasses of logical theories. Ann. Pure Appl. Logic, 43(1):1–30, 1989. [doi:10.1016/0168-0072(89)90023-7]

[14]   Albert E. Ingham: On the difference between consecutive primes. Quarterly Journal of Mathematics (Oxford Series), 8(1):255–266, 1937. [doi:10.1093/qmath/os-8.1.255]

[15]   Sandy Irani: Ground state entanglement in one dimensional translationally invariant quantum systems. J. Math. Phys., 51(2):022101, 2010. Preprint at arXiv. [doi:10.1063/1.3254321]

[16]   Dominik Janzing, Pawel Wocjan, and Shengyu Zhang: A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation. New J. Phys., 10(9):093004, 2008. Preprint at arXiv. [doi:10.1088/1367-2630/10/9/093004]

[17]   Emmanuel Jeandel and Pascal Vanier: Periodicity in tilings. In 14th Internat. Conf. Developments in Language Theory (DLT’10), pp. 243–254. Springer, 2010. Preprint at arXiv. [doi:10.1007/978-3-642-14455-4_23]

[18]   Neil D. Jones and Alan L. Selman: Turing machines and the spectra of first-order formulas. J. Symbolic Logic, 39(1):139–150, 1974. Available at JSTOR. Preliminary version in STOC’72.

[19]   A. S. Kahr, Edward F. Moore, and Hao Wang: Entscheidungsproblem reduced to the ∀∃∀ case. Proc. Natl. Acad. Sci. USA, 48(3):365–377, 1962. JSTOR.

[20]   Alastair Kay: Computational power of symmetric Hamiltonians. Phys. Rev. A, 78(1):012346, 2008. Preprint at arXiv. [doi:10.1103/PhysRevA.78.012346]

[21]   Julia Kempe, Alexei Kitaev, and Oded Regev: The complexity of the local Hamiltonian problem. SIAM J. Comput., 35(5):1070–1097, 2006. Preliminary version in FSTTCS’04. [doi:10.1137/S0097539704445226]

[22]   Alexei Kitaev, Alexander H. Shen, and Michael N. Vyalyi: Classical and Quantum Computation. AMS, 2002. [ACM:863284]

[23]   Leonid A. Levin: Average case complete problems. SIAM J. Comput., 15(1):285–286, 1986. Preliminary version in STOC’84. [doi:10.1137/0215020]

[24]   Harry R. Lewis: Complexity of solvable cases of the decision problem for the predicate calculus. In Proc. 19th FOCS, pp. 35–47. IEEE Comp. Soc. Press, 1978. [doi:10.1109/SFCS.1978.9]

[25]   Harry R. Lewis and Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 2 edition, 1997. [ACM:549820]

[26]   Yi-Kai Liu, Matthias Christandl, and Frank Verstraete: Quantum computational complexity of the N-representability problem: QMA complete. Phys. Rev. Lett., 98(11):110503, 2007. Preprint at arXiv. [doi:10.1103/PhysRevLett.98.110503]

[27]   Daniel Nagaj and Pawel Wocjan: Hamiltonian quantum cellular automata in one dimension. Phys. Rev. A, 78(3):032311, 2008. Preprint at arXiv. [doi:10.1103/PhysRevA.78.032311]

[28]   Roberto Oliveira and Barbara M. Terhal: The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Information & Computation, 8(10):900–924, 2008. Preprint at arXiv. [ACM:2016987]

[29]   Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, 1995.

[30]   Christos H. Papadimitriou and Mihalis Yannakakis: A note on succinct representations of graphs. Inf. Control, 71(3):181–185, 1986. [doi:10.1016/S0019-9958(86)80009-2]

[31]   Rohit Parikh: On context-free languages. J. ACM, 13(4):570–581, 1966. [doi:10.1145/321356.321364]

[32]   Paul W. K. Rothemund and Erik Winfree: The program-size complexity of self-assembled squares. In Proc. 32nd STOC, pp. 459–468. ACM Press, 2000. [doi:10.1145/335305.335358]

[33]   Leslie G. Valiant: The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410–421, 1979. [doi:10.1137/0208032]

[34]   Hao Wang: Proving theorems by pattern recognition II. Bell Systems Technical Journal, 40:1–41, 1961.

[35]   Erik Winfree: Algorithmic Self-Assembly of DNA. Ph. D. thesis, California Institute of Technology, 1998.