Zero Knowledge and the Chromatic Number
- 1 October 1998
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 57 (2) , 187-199
- https://doi.org/10.1006/jcss.1998.1587
Abstract
No abstract availableKeywords
This publication has 24 references indexed in Scilit:
- Free bits, PCPs and non-approximability-towards tight resultsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Interactive proofs and the hardness of approximating cliquesJournal of the ACM, 1996
- Derandomized graph productscomputational complexity, 1995
- Randomized graph products, chromatic numbers, and Lovasz j-functionPublished by Association for Computing Machinery (ACM) ,1995
- Improved non-approximability resultsPublished by Association for Computing Machinery (ACM) ,1994
- Efficient probabilistically checkable proofs and applications to approximationsPublished by Association for Computing Machinery (ACM) ,1993
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Probabilistic checking of proofs; a new characterization of NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992