%% Theory of Computing
%% File: v009a002.bib
%% Publication date: January 25, 2013
%% Authors: Daniel Gottesman and Sandy Irani
%
%
%
%
@string{acm      = "ACM Press"}
@string{ieee     = "IEEE Comp. Soc. Press"}
@string{springer = "Springer"}

@string{stoc72="Proc. 4th STOC"}
@string{stoc84="Proc. 16th STOC"}
@string{stoc89="Proc. 21st STOC"}
@string{stoc93="Proc. 25th STOC"}
@string{stoc00="Proc. 32nd STOC"}

@string{focs78="Proc. 19th FOCS"}
@string{focs07="Proc. 48th FOCS"}
@string{focs09="Proc. 50th FOCS"}

@string{JACM="J. ACM"}
@string{SIAMJComput="SIAM J. Comput."}

@string{infcont="Inf. Control"}
@string{jcss="J. Comput. System Sci."}
@string{jsl = "J. Symbolic Logic"}

@string{stacs=" Symp. Theoretical Aspects of Comp. Sci."}
@string{stacs07= "Proc. 24th" # stacs  # " (STACS'07)"}
%
@article{js74,
title = {Turing Machines and the Spectra of First-Order Formulas},
author = {Neil D. Jones and Alan L. Selman},
journal = jsl,
number = {1},
volume = {39},
year = {1974},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {139-150},
note = {Available at \href{http://www.jstor.org/stable/2272354}{JSTOR}. Preliminary version in \href{http://dx.doi.org/10.1145/800152.804909}{STOC'72}}
}
%
@inproceedings{js74-conference,
title = {Turing Machines and the Spectra of First-Order Formulas with Equality},
author = {Neil D. Jones and Alan L. Selman},
crossref = {pstoc72},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {157-167},
doi = {10.1145/800152.804909},
}
%
@article{qma1d,
title = {The Power of Quantum Systems on a Line},
author = {Dorit Aharonov and Daniel Gottesman and Sandy Irani and Julia Kempe},
note = {Preliminary version at \href{http://arxiv.org/abs/0705.4077}{arXiv}. Extended abstract in \href{http://dx.doi.org/10.1109/FOCS.2007.46}{FOCS'07}},
journal = {Comm. Math. Physics},
number = {1},
volume = {287},
year = {2009},
pages = {41-65},
doi = {10.1007/s00220-008-0710-3},
} 
%
@inproceedings{qma1d-conference,
title = {The Power of Quantum Systems on a Line},
author = {Dorit Aharonov and Daniel Gottesman and Sandy Irani and Julia Kempe},
crossref = {pfocs2007},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {373-383},
doi = {10.1109/FOCS.2007.46},
}


@inproceedings{jv09,
title = {Periodicity in Tilings},
author = {Jeandel, Emmanuel and Vanier, Pascal},
publisher = springer,
booktitle = {14th Internat. Conf. Developments in Language Theory (DLT'10)},
note = {Preprint at \href{http://arxiv.org/abs/0909.3997}{arXiv}},
year = {2010},
pages = {243-254},
doi = {10.1007/978-3-642-14455-4\_23},
} 
%
@article{deutsch,
title = {{Quantum theory, the Church-Turing principle and the universal quantum computer}},
author = {{Deutsch}, David},
journal = {Proc. Royal Society of London Series A},
volume = {400},
number = {1818},
year = {1985},
pages = {97-117},
doi = {10.1098/rspa.1985.0070},
}
%
@phdthesis{win98,
title = {Algorithmic Self-Assembly of DNA},
author = {Erik Winfree},
school = {California Institute of Technology},
year = {1998},
}

@article{gw83,
title = {Succinct Representations of Graphs},
author = {Hana Galperin and Avi Wigderson},
journal = infcont,
number = {3},
volume = {56},
year = {1983},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {183-198},
doi = {10.1016/S0019-9958(83)80004-7},
}
%
%
@article{kaytranslation,
title = {Computational Power of Symmetric {H}amiltonians},
author = {Alastair Kay},
note = {Preprint at \href{http://arxiv.org/abs/0801.3228}{arXiv}},
journal = {Phys. Rev. A},
volume = {78},
number = {1},
year = {2008},
pages = {012346},
doi = {10.1103/PhysRevA.78.012346},
}
%
@article{oliveira:05a,
title = {The complexity of quantum spin systems on a two-dimensional square lattice},
author = {Roberto Oliveira and Barbara M. Terhal},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0504050}{arXiv}},
journal = {Quantum Information {\&} Computation},
number = {10},
volume = {8},
year = {2008},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {900-924},
eprint = {acm:2016987}
}
%
@book{lp97,
title = {Elements of the Theory of Computation},
author = {Lewis, Harry R. and Papadimitriou, Christos H.},
publisher = {Prentice Hall},
edition = {2},
year = {1997},
eprint = {acm:549820},
}
%
@article{wang61,
title = {Proving theorems by pattern recognition {II}},
author = {Wang, Hao},
journal = {Bell Systems Technical Journal},
volume = {40},
year = {1961},
pages = {1-41},
} 
@article{p66,
title = {On Context-Free Languages},
author = {Rohit Parikh},
journal = JACM,
number = {4},
volume = {13},
year = {1966},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {570-581},
doi = {10.1145/321356.321364},
}


@article{bernsteinVazirani,
title = {Quantum Complexity Theory},
author = {Ethan Bernstein and Umesh Vazirani},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/167088.167097}{STOC'93}},
journal = SIAMJComput,
number = {5},
volume = {26},
year = {1997},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1411-1473},
doi = {10.1137/S0097539796300921},
}
%
@inproceedings{bernsteinVazirani-conference,
title = {Quantum complexity theory},
author = {Ethan Bernstein and Umesh V. Vazirani},
crossref = {pstoc93},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {11-20},
doi = {10.1145/167088.167097},
}
%
%
@article{lcv,
title = {Quantum Computational Complexity of the {$N$}-Representability Problem: {Q}{M}{A} complete},
author = {Yi-Kai Liu and Matthias Christandl and Frank Verstraete},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0609125}{arXiv}},
journal = {Phys. Rev. Lett.},
number = {11},
volume = {98},
year = {2007},
pages = {110503},
doi = {10.1103/PhysRevLett.98.110503},
}
%
%
@article{kmw62,
title = {Entscheidungsproblem Reduced to the {$\forall \exists \forall$} Case},
author = {A. S. Kahr and Edward F. Moore and Hao Wang},
journal = {Proc. Natl. Acad. Sci. USA},
volume = {48},
year = {1962},
number = {3},
pages = {365--377},
note = {\href{http://www.jstor.org/stable/71207}{JSTOR}}
}
%
@inproceedings{boas97,
title = {The convenience of tilings},
author = {Emde Boas, Peter van},
publisher = {Marcel Dekker Inc},
booktitle = {Complexity, Logic, and Recursion Theory},
editor = {Andrea Sorbi},
year = {1997},
pages = {331--363},
}
%
@inproceedings{bcg89-original,
title = {On the Theory of Average Case Complexity},
author = {Shai Ben-David and Benny Chor and Oded Goldreich and Michael Luby},
crossref = {pstoc89},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {204-216},
doi = {10.1145/73007.73027},
}
%
@article{bcg89,
title = {On the Theory of Average Case Complexity},
author = {Shai Ben-David and Benny Chor and Oded Goldreich and Michael Luby},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/73007.73027}{STOC'89}},
journal = jcss,
number = {2},
volume = {44},
year = {1992},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {193-219},
doi = {10.1016/0022-0000(92)90019-F},
}
%
@inproceedings{focsversion,
title = {The Power of Quantum Systems on a Line},
author = {Dorit Aharonov and Daniel Gottesman and Sandy Irani and Julia Kempe},
crossref = {pfocs07},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {373-383},
doi = {10.1109/FOCS.2007.46},
}
%
%
@misc{arxiv-version,
title = {The Quantum and Classical Complexity of Translationally Invariant Tiling and {H}amiltonian Problems},
author = {Daniel Gottesman and Sandy Irani},
url = {http://arXiv.org/abs/0905.2419},
eprint = {arXiv:0905.2419},
pages = {1-67},
note = {Conference version in \href{http://dx.doi.org/10.1109/FOCS.2009.22}{FOCS'09}},
year = {2009},
} 
%
@inproceedings{arxiv-version-conference,
title = {The Quantum and Classical Complexity of Translationally Invariant Tiling and {H}amiltonian Problems},
author = {Daniel Gottesman and Sandy Irani},
crossref = {pfocs09},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {95-104},
doi = {10.1109/FOCS.2009.22},
}


@article{levin86,
title = {Average Case Complete Problems},
author = {Leonid A. Levin},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/800057.808713}{STOC'84}},
journal = SIAMJComput,
number = {1},
volume = {15},
year = {1986},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {285-286},
doi = {10.1137/0215020},
}
%
@inproceedings{levin86-conference,
  author    = {Leonid A. Levin},
  title     = {Problems, Complete in ``Average'' Instance},
  crossref  = {pstoc84},
  pages     = {465},
  doi       = {10.1145/800057.808713},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{lewis78,
title = {Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus},
author = {Harry R. Lewis},
crossref = {pfocs78},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {35-47},
doi = {10.1109/SFCS.1978.9},
}
%
@article{lewis78-journal,
  author    = {Harry R. Lewis},
  title     = {Complexity Results for Classes of Quantificational Formulas},
  journal   = jcss,
  volume    = {21},
  number    = {3},
  year      = {1980},
  pages     = {317-353},
  doi       = {10.1016/0022-0000(80)90027-6},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1978.9}{FOCS'78}},
}
%
%
@article{nwtranslation,
title = {Hamiltonian Quantum Cellular Automata in One Dimension},
author = {Daniel Nagaj and Pawel Wocjan},
note = {Preprint at \href{http://arxiv.org/abs/0802.0886}{arXiv}},
journal = {Phys. Rev. A},
number = {3},
volume = {78},
year = {2008},
pages = {032311},
doi = {10.1103/PhysRevA.78.032311},
}
%
@article{jwztranslation,
title = {A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation},
author = {Dominik Janzing and Pawel Wocjan and Shengyu Zhang},
note = {Preprint at \href{http://arxiv.org/abs/0710.1615}{arXiv}},
journal = {New J. Phys.},
number = {9},
volume = {10},
year = {2008},
pages = {093004},
doi = {10.1088/1367-2630/10/9/093004},
}

@article{bgl09,
title = {The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases},
author = {Alberto Bertoni and Massimiliano Goldwurm and Violetta Lonati},
note = {Preliminary version in \href{http://dx.doi.org/10.1007/978-3-540-70918-3_33}{STACS'07}},
journal = {Fundam. Inform.},
number = {2},
volume = {91},
year = {2009},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {231-249},
doi = {10.3233/FI-2009-0042},
}
%
@inproceedings{bgl09-conference,
  author    = {Alberto Bertoni and
               Massimiliano Goldwurm and
               Violetta Lonati},
  title     = {On the Complexity of Unary Tiling-Recognizable Picture Languages},
  booktitle = {STACS},
  year      = {2007},
  pages     = {381-392},
  doi       = {10.1007/978-3-540-70918-3\_33},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{rothwin00,
title = {The program-size complexity of self-assembled squares},
author = {Paul W. K. Rothemund and Erik Winfree},
crossref = {pstoc00},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {459-468},
doi = {10.1145/335305.335358},
}
%
@incollection{furer83,
title = {The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)},
author = {Martin F{\"u}rer},
booktitle = {Logic and Machines: Decision and Complexity},
series = {LNCS},
volume = {171},
publisher = springer,
year = {1984},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {312-319},
doi = {10.1007/3-540-13331-3\_48},
}


@book{papa95,
title = {Computational Complexity},
author = {Christos H. Papadimitriou},
publisher = {Addison-Wesley},
year = {1995},
}
%
@article{berger66,
title = {The Undecidability of the domino problem},
author = {Berger, Robert },
journal = {Memoirs of the Am. Math. Soc.},
volume = {66},
year = {1966},
pages = {1-72},
}

@article{irani09,
title = {Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems},
author = {Sandy Irani},
note = {Preprint at \href{http://arxiv.org/abs/0901.1107}{arXiv}},
journal = {J. Math. Phys.},
number = {2},
volume = {51},
year = {2010},
pages = {022101},
doi = {10.1063/1.3254321},
}

@article{kempekitaevregev06,
title = {The Complexity of the Local {H}amiltonian Problem},
author = {Julia Kempe and Alexei Kitaev and Oded Regev},
note = {Preliminary version in \href{http://dx.doi.org/10.1007/978-3-540-30538-5_31}{FSTTCS'04}},
journal = SIAMJComput,
number = {5},
volume = {35},
year = {2006},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1070-1097},
doi = {10.1137/S0097539704445226},
}
%
@inproceedings{kempekitaevregev06-conference,
title = {The Complexity of the Local Hamiltonian Problem},
author = {Julia Kempe and Alexei Kitaev and Oded Regev},
booktitle = {24th Internat. Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS'04)},
publisher = springer,
year = {2004},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {372-383},
doi = {10.1007/978-3-540-30538-5\_31},
}
%
@article{ingham,
title = {On the difference between consecutive primes},
author = {Albert E. Ingham},
journal = {Quarterly Journal of Mathematics (Oxford Series)},
volume = {8},
number = {1},
year = {1937},
pages = {255--266},
doi = {10.1093/qmath/os-8.1.255},
}
%
@book{kitaev:book,
title = {Classical and Quantum Computation},
author = {Alexei Kitaev and Alexander H. Shen and Michael N. Vyalyi},
publisher = {AMS},
year = {2002},
eprint = {acm:863284},
}
%
@article{bm94,
title = {Self Induced Quenched Disorder: A Model for the Glass Transition},
author = {Jean-Philippe Bouchaud and Marc M{\'e}zard},
note = {Preprint at \href{http://arxiv.org/abs/cond-mat/9405075}{arXiv}},
journal = {J. Phys. I France},
number = {8},
volume = {4},
year = {1994},
pages = {1109-1114},
doi = {10.1051/jp1:1994240},
}

@article{gradel89,
title = {Dominoes and the Complexity of Subclasses of Logical Theories},
author = {Erich Gr{\"a}del},
journal = {Ann. Pure Appl. Logic},
number = {1},
volume = {43},
year = {1989},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1-30},
doi = {10.1016/0168-0072(89)90023-7},
}


@article{py86,
title = {A Note on Succinct Representations of Graphs},
author = {Christos H. Papadimitriou and Mihalis Yannakakis},
note = {},
journal = infcont,
number = {3},
volume = {71},
year = {1986},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {181-185},
doi = {10.1016/S0019-9958(86)80009-2},
}


@article{valiant79,
title = {The Complexity of Enumeration and Reliability Problems},
author = {Leslie G. Valiant},
journal = SIAMJComput,
number = {3},
volume = {8},
year = {1979},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {410-421},
doi = {10.1137/0208032},
}


@proceedings{pstoc72,
booktitle = stoc72,
publisher = acm,
year = {1972}
}
@proceedings{pstoc84,
booktitle = stoc84,
publisher = acm,
year = {1984}
}
@proceedings{pstoc89,
booktitle = stoc89,
publisher = acm,
year = {1989}
}
@proceedings{pstoc93,
booktitle = stoc93,
publisher = acm,
year = {1993}
}
@proceedings{pstoc00,
booktitle = stoc00,
publisher = acm,
year = {2000}
}

@proceedings{pfocs78,
booktitle = focs78,
publisher = ieee,
year = {1978}
}
@proceedings{pfocs07,
booktitle = focs07,
publisher = ieee,
year = {2007}
}
@proceedings{pfocs09,
booktitle = focs09,
publisher = ieee,
year = {2009}
}
