Compbook.Draft History
Hide minor edits - Show changes to markup
December 19, 2011, at 03:47 PM
by 65.215.1.12 -
Changed line 202 from:
See also these lecture notes of Avi Wigderson on lower bounds for constant depth and monotone circuits.
to:
December 07, 2010, at 02:23 PM
by 65.88.88.216 -
Added lines 283-285:
Very recently, Ryan Williams showed that NEXP is not contained in ACC0, thus resolving Forntier 2.1 from Chapter 14 of the book. We will add this exciting result to future versions of our book. In the meantime added this web appendix containing a full proof of the result (building on results presented in previous chapters) so people can teach it in courses based on the book.
December 07, 2010, at 02:12 PM
by 65.88.88.216 -
Added lines 72-73:
Added lines 280-281:
Changed lines 283-284 from:
to:
December 07, 2010, at 02:09 PM
by 65.88.88.216 -
Added lines 277-280:
August 20, 2009, at 04:19 PM
by 157.130.251.86 -
Added lines 198-200:
See also these lecture notes of Avi Wigderson on lower bounds for constant depth and monotone circuits.
April 15, 2009, at 07:20 PM
by 75.195.67.8 -
Changed line 7 from:
to:
September 17, 2008, at 11:22 AM
by 70.18.196.45 -
Changed lines 179-180 from:
to:
Approximation algorithms are covered in many texts and online lecture notes, including Princeton's COS 521 Advanced Algorithms course (see this page). More resources on the PCP Theorem are linked below in the notes to Chapter 22.
September 17, 2008, at 11:17 AM
by 70.18.196.45 -
Changed line 79 from:
includes Steven Rudich and Manuel Blum,
to:
includes Irit Dinur, Steven Rudich and Manuel Blum,
Changed lines 257-260 from:
For more on PCP and hardness of approximation, see these lecture notes by Guruswami and O'Donnell. Ryan O'Donnell also has online lecture notes for his course on Fourier analysis of Boolean functions, see also lecture notes by
Guy Kindler, Subhash Khot, Irit Dinur and Ehud Friedgut, Nati Linial, Dieter van Melkebeek, and Elchanan Mossel.
to:
For more on PCP and hardness of approximation, see these lecture notes by Guruswami and O'Donnell and these notes by Irit Dinur. Ryan O'Donnell also has online lecture notes for his course on Fourier analysis of Boolean functions, see also lecture notes by
Guy Kindler, Subhash Khot, Irit Dinur and Ehud Friedgut, Nati Linial, Dieter van Melkebeek, and Elchanan Mossel.
June 23, 2008, at 10:12 AM
by 70.208.202.247 -
Changed lines 162-164 from:
to:
Many relevant links can be found from the web page of Boaz's cryptography course. Some early drafts of Goldreich's book are available here. Judging from the authors and table of contents, the upcoming book by Boneh and Shoup looks extremely good.
June 22, 2008, at 11:00 PM
by 24.215.197.138 -
Changed lines 2-3 from:
Textbook by Sanjeev Arora and Boaz Barak
to:
Textbook by Sanjeev Arora and Boaz Barak, Cambridge University Press.
June 22, 2008, at 10:44 PM
by 24.215.197.138 -
Changed lines 84-87 from:
[[ http://www.cs.sfu.ca/~kabanets/710/#lec
Valentine Kabanets ]] , Muli Safra
to:
Valentine Kabanets , Dieter van Melkebeek, Muli Safra
Changed lines 90-92 from:
to:
There are several important topics connected to computational complexity that we cover in the book only briefly or not at all. One area that is completely missing is computational learning theory. See this course by Avrim Blum and this text by Kearns and Vazirani for more.
Changed lines 110-111 from:
NP optimaization problems compendium
to:
See the NP optimization problems compendium for the NP-completeness status of many important optimization problems.
See also David Johnson's classical columns on NP completeness.
Changed lines 255-257 from:
Guy Kindler, Subhash Khot, Irit Dinur and Ehud Friedgut, Nati Linial, and Elchanan Mossel.
to:
Guy Kindler, Subhash Khot, Irit Dinur and Ehud Friedgut, Nati Linial, Dieter van Melkebeek, and Elchanan Mossel.
June 22, 2008, at 10:33 PM
by 24.215.197.138 -
Changed line 80 from:
Luca Trevisan, Russel Impagliazzo ,
to:
Luca Trevisan (see also his blog), Russel Impagliazzo ,
Added lines 92-93:
Added line 238:
For more on expander graphs and their applications, see this survey by Hoory, Linial, and Wigderson.
Added lines 250-253:
For more on PCP and hardness of approximation, see these lecture notes by Guruswami and O'Donnell. Ryan O'Donnell also has online lecture notes for his course on Fourier analysis of Boolean functions, see also lecture notes by
Guy Kindler, Subhash Khot, Irit Dinur and Ehud Friedgut, Nati Linial, and Elchanan Mossel.
June 22, 2008, at 10:25 PM
by 24.215.197.138 -
Added lines 73-93:
General resources on complexity theory
Many complexity theorists put their research papers on their home page and/or post them on Internet archives such as the Electronic Colloquium on Computational Complexity (ECCC) or the Arxiv.
There are many excellent lecture notes for complexity theory on the web. A partial list
includes Steven Rudich and Manuel Blum,
Madhu Sudan,
Luca Trevisan, Russel Impagliazzo ,
Chris Umans,
Oded Goldreich (see also his book ), Uri Feige & Ran Raz,
Moni Naor,
[[ http://www.cs.sfu.ca/~kabanets/710/#lec
Valentine Kabanets ]] , Muli Safra
Some surveys on complexity can be found on the bulletin of the EATCS (other sources of surveys include "SIGACT news" and "foundations and trends of theoretical computer science", but they seem not to be freeely available online).
June 22, 2008, at 09:45 PM
by 24.215.197.138 -
Changed lines 3-5 from:
to:
Added lines 8-9:
Changed lines 12-13 from:
- table of contents, preface and introduction of final draft
to:
- Table of contents, preface and introduction of final draft
June 22, 2008, at 09:43 PM
by 24.215.197.138 -
Changed lines 231-232 from:
to:
Appendix A: Mathematical background
June 22, 2008, at 09:42 PM
by 24.215.197.138 -
Changed lines 76-77 from:
to:
Changed lines 84-85 from:
to:
Added lines 91-93:
Added lines 98-99:
Added lines 104-106:
Added lines 111-113:
Added lines 118-119:
Added lines 124-125:
Added lines 131-132:
Changed lines 139-140 from:
to:
Added lines 146-147:
Added lines 152-153:
Changed lines 158-159 from:
to:
Added lines 164-165:
Added lines 171-172:
Added lines 177-181:
Algebraic complexity is a large and beautiful area, and we only mention a few of its results in this chapter. Some more material can be found in these lecture notes of Avi Wigderson.
Added lines 187-188:
Added lines 193-194:
Changed lines 199-200 from:
to:
Changed lines 205-206 from:
to:
Changed lines 211-212 from:
to:
Changed lines 222-223 from:
to:
Changed lines 228-230 from:
to:
June 22, 2008, at 09:38 PM
by 24.215.197.138 -
Changed lines 8-11 from:
table of contents, preface and introduction of final draft
Earlier drafts: January 2007 November 2006
to:
- table of contents, preface and introduction of final draft
- Earlier drafts: January 2007 November 2006
Changed lines 61-62 from:
to:
Changed lines 93-120 from:
to:
Chapter 5: The polynomial hierarchy and alternations
draft (Jan 07)
Chapter 6: Boolean circuits
draft (Jan 07)
Chapter 7: Randomized computation
draft (Jan 07)
Chapter 8: Interactive proofs
draft (Jan 07)
Chapter 9: Cryptography
draft (Jun 08)
Chapter 10: Quantum computation
draft (Jun 08)
Many topics that we did not cover, including quantum error correction, quantum black-box lower bounds, and the ``Quantum Cook-Levin Theorem'', can be found on Umesh Vazirani's lecture notes
Chapter 11: PCP Theorem and hardness of approximation: an introduction
draft (Jun 08)
Chapter 12: Decision trees
draft (Jan 07)
Chapter 13: Communication complexity
draft (Jan 07)
Chapter 14: Circuit lower bounds
draft (Jan 07)
Chapter 15: Proof complexity
draft (Jan 07)
Chapter 16: Algebraic computation models
draft (Jan 07)
Chapter 17: Complexity of counting
draft (Jan 07)
Chapter 18: Average case complexity: Levin's theory
draft (Jan 07)
Chapter 19: Hardness amplification and error correcting codes
draft (Jun 08)
Chapter 20: Derandomization
draft (Jun 08)
Chapter 21: Pseudorandom constructions: expanders and extractors
draft (Jun 08)
Chapter 22: Proofs of PCP theorems and the Fourier transform technique
draft (Jun 08)
One thing we didn't include is a proof of the parallel repetition lemma. The
original proof by Raz was simplified by Holenstein. See also
this writeup of the simplified proof.
Chapter 23: Why are circuit lower bounds so difficult?
draft (Jan 07)
Changed lines 189-190 from:
to:
June 22, 2008, at 09:20 PM
by 24.215.197.138 -
Changed lines 6-9 from:
to:
This page contains early drafts of the book, as well as links to additional relevant material available online. See this page for links to courses using this book.
table of contents, preface and introduction of final draft
Added line 15:
Added line 17:
Added line 19:
Added line 21:
Added line 23:
Added line 25:
Added line 27:
Added line 29:
Added line 31:
Added line 33:
Added line 40:
Added line 42:
Added line 44:
Added line 46:
Added line 52:
Added line 54:
Added line 56:
Added line 58:
Added line 60:
Added line 62:
Changed lines 69-123 from:
to:
June 22, 2008, at 09:10 PM
by 24.215.197.138 -
Added lines 25-49:
June 22, 2008, at 09:05 PM
by 24.215.197.138 -
Added lines 1-24:
|
|
|