Google Scholar

Thursday, August 04, 2005

Use of PCP theorem

As it was proved by Khanna, Linial and Safra in 2000, it is NP-hard to color 3-colorable graph using 4-colors. That proof used PCP-theorem.
Last year they found an elegant proof of the same result which does not rely on PCP theorem. See
V. Guruswami, S. Khanna, On the hardness of 4-coloring of 3-colorable graph, SIAM Journal on Discrete Mathematics, 18, 1 (2004)
But PCP theorem is still needed to prove NP-hardness of 4-colorability of 3-colorable graph for bounded degree graphs.
I have found that a classical book
Flatland
A romance of many dimensions
With Illustrations by the Author, A SQUARE
(Edwin A. Abbott 1838-1926)

is published online.
As far as I remember, the first time I read about Flatland in one of Martin Gardner's books,
Another good classical book published online is
"Symmetry Groups and Their Applications
by Willard Miller
Academic Press, New York, 1972 "
(out of print, published online by its author). The book is written from application point of view (mostly application to physics) and it contains quite a good material on the theory of finite groups.
It costs 374 USD at amazon.com on August 4 2005
Enjoy!