Stellar Course Management System

No Lecture Wed

There will be no lecture this Wed, May 17.

There will be regularly scheduled recitation on Thursday. You should feel free to bring your questions about any of the material in the class or the final logistics to recitation.

Here is a (rough) list of all of the parts of the book you should know.

Chapter 1: It's expected that you know the term "NFA". You should also know that NFAs are equivalent to DFAs. However, you don't need to know the proof of this fact or any other details about NFAs.

Chapter 3: Again, you don't need to know the proof that non-deterministic Turing machines are equivalent to regular Turing machines. Understanding the concept of nondeterminism is a good idea, but will not be required to solve any of the problems on the final. You should know about enumerators.

Chapter 4: You should know all of chapter 4 except those parts that reference CFGs (from chapter 2).

Chapter 5: You need to know that part of 5.1 that does not refer to CFGs or LBA. You need to know and understand all of 5.3. You don't need to know 5.2.

Chapter 6: You need to know 6.1

Chapter 7: You need to know all of the main concepts in chapter 7, again with the exception of nondeterminism. Obviously, you need to understand P and NP extremely thoroughly. You only need to know those problems and reductions that were covered (either in class, recitation or the homework).

Chapter 8: You need to know chapter 8 through 8.3. You don't need to know the proof of Savitch's theorem, although you should know the fact that NPSPACE=PSPACE.

Chapter 9: You should know the proof of the Space Hierarchy Theorem, and the proof that EQ_REX! (arrow in the book) is EXPSPACE hard. You should also know section 9.2 on relativization (covered today).

Chapter 10: You should know chapter 10.2 as well as any number theory that we talked about in class. Keep in mind that the proof of PRIMES in BPP done in the book is *not* identical to the one done in class. Also, please use the definition of RP from the book.
You should know chapter 10.4. You don't need to know the proof that IP=PSPACE.

Additional material: You should have a basic conception of Zero Knowledge Proofs and why they might be useful.
Wikipedia has a decent basic overview of Zero Knowledge Proofs. http://en.wikipedia.org/wiki/Zero-knowledge_proof
In addition, you should know that the way that we show a proof is "Zero-Knowledge" is to take any cheating verifier V' and construct a polynomial time simulator S that can generate a transcript identical to the transcript of the conversation between P and V' *if* the statement being proved is in fact true. This is equivalent to saying that any additional information V' gets from the conversation, it could have gotten by staying at home and flipping coins itself - so it's not really learning anything from P.

I will send out some practice questions for the recent material in a few days.

-Alice

Announced on 15 May 2006  1:35  p.m. by Alissa Reyzin

4:00 recitation moved

Today's (and only today's) 4:00 recitation has been moved
to 36-156.

Announced on 27 April 2006  7:33  a.m. by Alissa Reyzin

Quiz 2 results

Very few people got the correct answer for problem 3. Therefore, this problem will be considered "extra credit." If you got it, congratulations - if you didn't, don't worry about it. With that said, the test was out of 75 points. The average on the test (not including problem 3) was 50, with a standard deviation of 18. The (approximate) grade breakup is as follows:

60-75: A
45-60: B
30-45: C
0-30: D/F

Tests will be returned tomorrow in recitation. However, if you are seriously considering dropping the class, you can email me to ask for your test grade, and I will try to respond as quickly as I can. Please do not email me just because you want to know your grade a few hours early.

Announced on 26 April 2006  10:34  p.m. by Alissa Reyzin

Quiz 1 Results

The average on Quiz 1 was 66 and the standard deviation was 24. The grade breakup is (approximately) as follows:

A:(80-100): 12
B:(60-79): 10
C:(45:59): 9
D/F:(0:44): 6

You can get your quiz from me tomorrow after lecture or in recitation on Thursday. If you got below a 45, you should come talk to me about what you can do to improve your understanding of the material.

Announced on 14 March 2006  1:12  p.m. by Alissa Reyzin

10am recitation cancelled

The 10am recitation is cancelled for the remainder of the term. Please come to the 1pm or 4pm recitations.

Announced on 13 February 2006  8:58  a.m. by Alissa Reyzin