% The Chicago Journal of Theoretical Computer Science, Volume 1995, Article 4
% Bibliography

@inproceedings{cj95-04-1,
  author={S. Arora and C. Lund and R. Motwani and M. Sudan and M. Szegedy},
  title={Proof Verification and Hardness of Approximation Problems},
  booktitle={Proceedings of the 33rd Symposium on Foundations of
    Computer Science},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={October},
  year={1992},
  pages={14--23}
}

@inproceedings{cj95-04-2,
  author={S. Arora and S. Safra},
  title={Probabilistic Checking of Proofs},
  booktitle={Proceedings of the 33rd Symposium on Foundations of
    Computer Science},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={October},
  year={1992},
  pages={2--13}
}

@book{cj95-04-3,
  editor={R. Aumann and S. Hart},
  title={Handbook of Game Theory},
  volume={1},
  publisher={North Holland},
  address={Amsterdam},
  year={1992}
}

@article{cj95-04-4,
  author={L. Babai and S. Moran},
  title={{A}rthur-{M}erlin Games: a Randomized Proof System and a
    Hierarchy of Complexity Classes},
  journal={Journal of Computer and System Sciences},
  volume={36},
  number={2},
  month={April},
  year={1988},
  pages={254--276}
}

@inproceedings{cj95-04-5,
  author={A. Cohen and A. Wigderson},
  title={Dispersers, Deterministic Amplification, and Weak Random Sources},
  booktitle={Proceedings of the 30th Symposium on Foundations of
    Computer Science},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={October},
  year={1989},
  pages={14--19}
}

@article{cj95-04-6,
  author={A. Condon},
  title={The Complexity of the Max Word Problem and the Power of
    One-way Interactive Proof Systems},
  journal={Computational Complexity},
  volume={3},
  number={3},
  year={1993},
  pages={292--305}
}

@techreport{cj95-04-7,
  author={A. Condon and J. Feigenbaum and C. Lund and P. Shor},
  title={Probabilistically Checkable Debate Systems and
    Approximation Algorithms for {PSPACE}-Hard Functions},
  institution={Center for Discrete Mathematics and Theoretical
    Computer Science (DIMACS)\discretionary{}{}{}},
  number={93-10},
  month={March},
  year={1993},
  address={Berkeley, CA}		  
}

@inproceedings{cj95-04-8,
  author={A. Condon and J. Feigenbaum and C. Lund and P. Shor},
  title={Probabilistically Checkable Debate Systems and Approximation
    Algorithms for {PSPACE}-Hard Functions (Extended Abstract)},
  booktitle={Proceedings of the 25th ACM Symposium on the Theory of Computing},
  publisher={Association for Computing Machinery},
  address={New York},
  month={May},
  year={1993},
  pages={305--314}
}

@inproceedings{cj95-04-9,
  author={A. Condon and J. Feigenbaum and C. Lund and P. Shor},
  title={Random Debaters and the Hardness of Approximating
    Stochastic Functions},
  booktitle={Proceedings of the 9th Conference on Structure in
  Complexity Theory},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={June},
  year={1994},
  pages={280--293},
  note={Final version to appear in \textit{SIAM Journal on Computing}}
}

@inproceedings{cj95-04-10,
  author={U. Feige and S. Goldwasser and L. Lov\'asz and M. Safra and
    M. Szegedy},
  title={Approximating Clique is Almost {NP}-Complete},
  booktitle={Proceedings of the 32nd Symposium on Foundations of
    Computer Science},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={October},
  year={1991},
  pages={2--12}
}

@book{cj95-04-11,
  author={M. R. Garey and D. S. Johnson},
  title={Computers and Intractibility: A Guide to the Theory of
    {NP}-Completeness},
  publisher={W. H. Freeman and Company},
  address={San Fransisco},
  year={1979}
}

@article{cj95-04-12,
  author={P. Gemmell and M. Sudan},
  title={Highly resilient correctors for polynomials},
  journal={Information Processing Letters},
  volume={43},
  number={4},
  month={June},
  year={1992},
  pages={169--174}
}

@inproceedings{cj95-04-13,
  author={H. {Hunt III} and M. Marathe and R. Stearns},
  title={Generalized {CNF} Satisfiability Problems and
    Non-Efficient Approximability},
  booktitle={Proceedings of the 9th Conference on Structure in
    Complexity Theory},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={June},
  year={1994},
  pages={356--366}
}

@inproceedings{cj95-04-14,
  author={R. Impagliazzo and D. Zuckerman},
  title={How to Recycle Random Bits},
  booktitle={Proceedings of the 30th Symposium on Foundations of
    Computer Science},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={October},
  year={1989},
  pages={248--253}
}

@article{cj95-04-15,
  author={D. S. Johnson},
  title={Approximation algorithms for combinatorial problems},
  journal={Journal of Computer and System Sciences},
  volume={9},
  number={3},
  month={December},
  year=1974,
  pages={256--278}
}

@inproceedings{cj95-04-16,
  author={D. Kozen},
  title={Lower bounds for natural proof systems},
  booktitle={Proceedings of the 18th Symposium on Foundations of Computer Science},
  publisher={IEEE Computer Society Press},
  address={Los Alamitos, CA},
  month={October},
  year={1977},
  pages={254--266}
}

@article{cj95-04-17,
  author={C. Lund and L. Fortnow and H. Karloff and N. Nisan},
  title={Algebraic methods for interactive proof systems},
  journal={Journal of the Association for Computing Machinery},
  volume={39},
  number={4},
  month={October},
  year={1992},
  pages={859--868}
}

@inproceedings{cj95-04-18,
  author={M. Marathe and H. {Hunt III} and R. Stearns and V. Radhakrishnan},
  title={Hierarchical Specifications and Polynomial-Time
    Approximation Schemes for {PSPACE}-Complete Problems},
  booktitle={Proceedings of the 26th ACM Symposium on the Theory of Computing},
  publisher={Association for Computing Machinery},
  address={New York},
  month={May},
  year={1994},
  pages={468--477}
}

@article{cj95-04-19,
  author={C. Papadimitriou},
  title={Games Against Nature},
  journal={Journal of Computer and System Sciences},
  volume={31},
  number={2},
  month={October},
  year={1985},
  pages={288--301}
}

@article{cj95-04-20,
  author={C. Papadimitriou and M. Yannakakis},
  title={Optimization, Approximation, and Complexity Classes},
  journal={Journal of Computer and System Sciences},
  volume={43},
  number={3},
  month={December},
  year={1991},
  pages={425--440}
}

@article{cj95-04-21,
  author={T. J. Schaefer},
  title={On the Complexity of Some Two-Person Perfect-Information Games},
  journal={Journal of Computer and System Sciences},
  volume={16},
  number={2},
  month={April},
  year=1978,
  pages={185--225}
}

@article{cj95-04-22,
  author={A. Shamir},
  title={{IP=PSPACE}},
  journal={Journal of the Association for Computing Machinery},
  volume={39},
  number={4},
  month={October},
  year={1992},
  pages={869--877}
}