% The Chicago Journal of Theoretical Computer Science, Volume 1997, Article 1
% Bibliography

@Article{cj97-01-01,
  title =        {Fixed-parameter tractability and completeness {IV}: On
                 completeness for {${W[\complexityclass{P}]}$} and
                 {${\complexityclass{PSPACE}}$} analogues},
  author =       {K. Abrahamson and R. Downey and M. Fellows},
  pages =        {235--276},
  journal =      {Annals of Pure and Applied Logic},
  month =        jun,
  year =         {1995},
  volume =       {73},
  number =       {3}
}

@InProceedings{cj97-01-02,
  author =       {K. Abrahamson and J. Ellis and M. Fellows and
                 M. Mata},
  title =        {On the complexity of fixed-parameter problems},
  year =         {1989},
  pages =        {210--215},
  booktitle =    {Proceedings of the 30th IEEE Symposium on Foundations
                 of Computer Science},
  publisher =    {IEEE Computer Society Press},
  address =      {Washington, DC}
}

@Article{cj97-01-03,
  author =       {N. Alon and R. Yuster and U. Zwick},
  title =        {Color coding},
  year =         {1995},
  pages =        {844--856},
  journal =      {Journal of the ACM},
  volume =       {42},
  number =       {4},
  month =        jul
}

@InProceedings{cj97-01-04,
  author =       {R. Beigel and D. Eppstein},
  title =        {3-Coloring in time {${\orderle{1.3446^{n}}}$}: a
                 no-{MIS} algorithm},
  year =         {1995},
  pages =        {444--452},
  booktitle =    {Proceedings of the 36th IEEE Symposium on Foundations
                 of Computer Science},
  publisher =    {IEEE Computer Society Press},
  address =      {Washington, DC}
}

@Article{cj97-01-05,
  author =       {J. Buss and J. Goldsmith},
  title =        {Nondeterminism within {${\complexityclass{P}}$}},
  year =         {1993},
  pages =        {560--572},
  journal =      {SIAM Journal on Computing},
  volume =       {22},
  number =       {3},
  month =        jun
}

@InProceedings{cj97-01-06,
  title =        {On the Amount of Nondeterminism and the Power of
                 Verifying (Extended Abstract)},
  author =       {L. Cai and J. Chen},
  editor =       {Andrzej M. Borzyszkowski and Stefan Sokolowski},
  booktitle =    {Mathematical Foundations of Computer Science 1993, 18th
                 International Symposium},
  year =         1993,
  series =       {Lecture Notes in Computer Science},
  volume =       711,
  publisher =    {Springer-Verlag},
  address =      {Berlin},
  comment =      {ISBN 3-540-57182-5},
  pages =        {311--320}
}

@Article{cj97-01-07,
  author =       {D. Coppersmith and S. Winograd},
  title =        {Matrix multiplication via arithmetic progression},
  year =         {1990},
  pages =        {251--280},
  journal =      {Journal of Symbolic Computation},
  volume =       {9},
  number =       {3}
}

@InProceedings{cj97-01-08,
  author =       {R. Downey and M. Fellows},
  title =        {Fixed-parameter intractability},
  year =         {1992},
  pages =        {36--49},
  booktitle =    {Proceedings of the 7th Annual Symposium on Structure
                 in Complexity Theory}
}

@InCollection{cj97-01-09,
  author =       {R. Downey and M. Fellows},
  title =        {Parameterized computational feasibility},
  year =         {1995},
  pages =        {219--244},
  booktitle =    {Feasible Mathematics II},
  editor =       {P. Clote and J. B. Remmel},
  publisher =    {Birkhauser}
}

@Book{cj97-01-10,
  author =       {J. P. Buhler and H. W. Lenstra and Carl Pomerance},
  title =        {The development of the number field sieve},
  year =         {1994},
  series =       {Lecture Notes in Mathematics},
  volume =       {1554},
  publisher =    {Springer-Verlag},
  address =      {Berlin}
}

@Article{cj97-01-11,
  author =       {U. Feige and S. Goldwasser and L. Lov\'asz and
                 S. Safra and M. Szegedy},
  title =        {Interactive proofs and the hardness of approximating
                 cliques},
  year =         {1996},
  pages =        {268--292},
  journal =      {Journal of the ACM},
  volume =       {43},
  number =       {2}
}

@Article{cj97-01-12,
  author =       {O. Goldreich and R. Ostrovsky},
  title =        {Software protection and simulation on oblivious
                 {RAM}s},
  year =         {1996},
  pages =        {431--473},
  journal =      {Journal of the ACM},
  volume =       {43},
  number =       {3}
}

@Article{cj97-01-13,
  author =       {A. Itai and M. Rodeh},
  title =        {Finding a minimum circuit in a graph},
  year =         {1978},
  pages =        {413--423},
  journal =      {SIAM Journal on Computing},
  volume =       {7},
  number =       {4}
}

@Article{cj97-01-14,
  author =       {J. Nesetril and S. Poljak},
  title =        {On the complexity of the subgraph problem},
  year =         {1985},
  pages =        {415--419},
  journal =      {Commentationes Mathematicae Universitatis Carolinae},
  volume =       {26},
  number =       {2}
}

@Book{cj97-01-15,
  author =       {C. Papadimitriou},
  title =        {Computational Complexity},
  year =         {1995},
  publisher =    {Addison-Wesley},
  address =      {Reading, MA}
}

@Article{cj97-01-16,
  author =       {N. Pippenger and M. Fischer},
  title =        {Relation among complexity measures},
  year =         {1979},
  pages =        {361--381},
  journal =      {Journal of the ACM},
  volume =       {26},
  number =       {2}
}

@InProceedings{cj97-01-17,
  author =       {W. Paul and N. Pippenger and E. Szemeredi and
                 W. Trotter},
  title =        {On determinism versus nondeterminism and related
                 problems},
  year =         {1983},
  pages =        {429--438},
  booktitle =    {Proceedings of the 24th IEEE Symposium on Foundations
                 of Computer Science},
  publisher =    {IEEE Computer Society Press},
  address =      {Washington, DC}
}

@InProceedings{cj97-01-18,
  author =       {A. Polishchuk and D. Spielman},
  title =        {Nearly-linear size holographic proofs},
  year =         {1994},
  pages =        {194--203},
  booktitle =    {Proceedings of the 26th ACM Symposium on Theory of
                 Computing},
  publisher =    {ACM Press},
  address =      {New York}
}

@InProceedings{cj97-01-19,
  author =       {J. Plehn and B. Voigt},
  title =        {Finding minimally weighted subgraphs},
  year =         {1990},
  pages =        {18--29},
  booktitle =    {Proceedings of the 16th Workshop on Graph Theoretic
                 Concepts in Computer Science},
  publisher =    {Springer-Verlag},
  address =      {Berlin}
}

@Article{cj97-01-20,
  title =        {On Limited Nondeterminism and the Complexity of the
                 {VC} {D}imension},
  author =       {C. Papadimitriou and M. Yannakakis},
  pages =        {161--170},
  journal =      {Journal of Computer and System Sciences},
  year =         {1996},
  month =        oct,
  volume =       {53},
  number =       {2},
  source =       {http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}

@Article{cj97-01-21,
  author =       {N. Robertson and P. Seymour},
  title =        {Graph minors. {II}. {A}lgorithmic aspects of
                 tree-width},
  year =         {1986},
  pages =        {309--322},
  journal =      {Journal of Algorithms},
  volume =       {7},
  number =       {3}
}

@Article{cj97-01-22,
  author =       {N. Robertson and P. Seymour},
  title =        {Graph minors. {XIII}. {T}he disjoint paths problem},
  year =         {1995},
  pages =        {65--110},
  journal =      {Journal of Combinatorial Theory, Series B},
  volume =       {63}
}

@InProceedings{cj97-01-23,
  author =       {R. Schroeppel and A. Shamir},
  title =        {{${T\cdot{S}^{2}=\orderle{2^{n}}}$} time/space
                 tradeoff for certain {${\complexityclass{NP}}$}-complete
                 problems},
  year =         {1979},
  pages =        {328--336},
  booktitle =    {Proceedings of the 20th IEEE Symposium on Foundations
                 of Computer Science},
  publisher =    {IEEE Computer Society Press},
  address =      {Washington, DC}
}

@Article{cj97-01-24,
  author =       {R. Tarjan and A. Trojanowski},
  title =        {Finding a maximum independent set},
  year =         {1977},
  pages =        {537--546},
  journal =      {SIAM Journal on Computing},
  volume =       {6},
  number =       {3}
}

@Article{cj97-01-25,
  title =        {On Unapproximable Versions of
                 {${\complexityclass{NP}}$}-Complete Problems},
  author =       {D. Zuckerman},
  pages =        {1293--1304},
  journal =      {SIAM Journal on Computing},
  month =        dec,
  year =         {1996},
  volume =       {25},
  number =       {6}
}