|HW4 was checked.|
Appeals can be submitted by email to Michal until Sunday, 27.02 (If for some reason you know that you won't be able to check your submission before that date, please contact Michal).
|HW3 was checked.|
Appeals can be submitted by email to Michal until Sunday, 15.02 (If for some reason you know that you won't be able to check your submission before that date, please contact Michal).
The tutorials were updated
|Thanks to your comments, the errors in the tutorials were fixed, and many explanations were added.|
When you read them while studing to the test, we will appreciate if you send us additional errors you find.
Thank you all!
|HW2 was checked.|
Appeals can be submitted by email to Michal until Sunday, 11.02 (If for some reason you know that you won't be able to check your submission before that date, please contact Michal).
Tutorial 13 is now online
Section 3 in Question 4 is canceled
|We are sorry for the inconvenience.|
|Whoever needs a delay in HW4 can submit till Thursday 25/01, 23:59.|
Clarification Regarding HW4
|In the 4th question, third section, the algorithms of "Type" and "In" should be in DL. This section will be considered as bonus.|
HW 4 is online
Clarification Regarding HW3
|In question 2, L1 can be BPP-reduced to L2 if there exists polynimial p(n) and polynomial probabilistic TM, M s.t.:|
for x in L the probability that M(x) is in L2 is at least 0.5+1/p(|x|)
for x not in L the probability that M(x) isn't in L2 is at least 0.5+1/p(|x|)
solutions that use any other function that is not asymptotically greater than any polynomial will be accepted as well (for example, using any constant)
HW 3 is online
|HW1 was checked.|
Appeals can be submitted by email to Michal until Monday, 08.01.
|Whoever needs a delay in HW2 can submit till Tuesday before/after the tutorial. This does not change the submission date for HW3.|
There is an update to the notes of tutorial 7
|HW 2 is now published under the "Assignemnts" section.|
Tutorial 7 is online + Reception hour
|The next reception hour of Michal (04.12, 16:30) is canceled. If you planned to come, please contact Michal to reschedule.|
HW 1 and a clarification on the last tutorial
|HW 1 is now published under the "Assignemnts" section.|
Please note that the proof of the collapse theorem was completed in the last tutorial.
Those who weren't in the last tutorial are welcome to send Michal an email and schedule a reception hour.
The tutorial hours remain in Tuesday 16:30
The notes of tutorial 3 are online
Finding new tutorial hours
|Since the majority of the students find the current time of the tutorial uncomfortable, we will try to find a different hour that will be comfortable for everyone.|
Please answer the following form untill Sunday (5.11):
If you have any questions, please contact Michal.
The notes of the second tutorial are online
|In the first part of the tutorial we prove that TQBF is PSPACE complete. This proof isn't covered in the notes.|
If you attend the office hours of Michal, please inform her by email in advance.
|Welcome to the course.|
Tutorial 0 was uploaded to the website. It contains a short review of "Computability", and it is highly recommended for you to look at it.
We will assume that you already know this material before the first lecture.
The final grade will consist of: 60% for compulsory HW and 40% for a final exam. More details in the first lecture.