Instructions for Final Project were posted
|פורסם ב- 23/6/2019, 08:51:52 Created on 23/6/2019, 08:51:52 Создано 23/6/2019, 08:51:52 تم النشر ب- 23/6/2019, 08:51:52|
|The grades for the second assignment are available online. |
The graded papers will be available at the secretariat next week.
Appeals should be sent to Inbar by e-mail no later than July 7.
|פורסם ב- 21/6/2019, 12:24:45 Created on 21/6/2019, 12:24:45 Создано 21/6/2019, 12:24:45 تم النشر ب- 21/6/2019, 12:24:45|
Problem Set 3 posted
|Please type (preferably using Latex/Lyx) and submit **digitally via webcourse**.|
Submission in singles.
Deadline is June 27th at 4 pm.
|עדכון אחרון ב- 14/6/2019, 08:24:36 Last updated on 14/6/2019, 08:24:36 Последняя модификация 14/6/2019, 08:24:36 تمت الحتلنة الأخيرة ب- 14/6/2019, 08:24:36|
|The update earlier today reintroduced a typo in the parameters in Question 3A - the current version should have them fixed. Thanks Liron and Ohad.|
|פורסם ב- 3/6/2019, 19:47:43 Created on 3/6/2019, 19:47:43 Создано 3/6/2019, 19:47:43 تم النشر ب- 3/6/2019, 19:47:43|
Guideline for Question 3 Part 2
|After input from some students, I made some changes to Question 3 Part 2. Accordingly, I am allowing an automatic extension till Monday June 10th at 4pm.|
1. Added a guideline for how to solve.
2. The number of provers can be poly(q) rather than specifically q^2.
3. I added a simplifying assumption that each *individual* query by itself is uniformly random (although the queries together can be highly correlated).
|פורסם ב- 3/6/2019, 12:21:21 Created on 3/6/2019, 12:21:21 Создано 3/6/2019, 12:21:21 تم النشر ب- 3/6/2019, 12:21:21|
|In question 4 you only need to show that there exists some (sufficiently large) constant c such that if $n = c*k /\eps^2$ then the statement holds.|
|פורסם ב- 26/5/2019, 20:54:14 Created on 26/5/2019, 20:54:14 Создано 26/5/2019, 20:54:14 تم النشر ب- 26/5/2019, 20:54:14|
Corrections to Problem Set 2
|A couple of parameters in Question 3 were wrong and have been corrected - thanks Sivan for pointing these out.|
|פורסם ב- 25/5/2019, 22:54:29 Created on 25/5/2019, 22:54:29 Создано 25/5/2019, 22:54:29 تم النشر ب- 25/5/2019, 22:54:29|
Second problem set has been posted
|Due 6/6/2019 at 4pm. Please submit to Inbar's physical mailbox (#154).|
|פורסם ב- 20/5/2019, 10:11:09 Created on 20/5/2019, 10:11:09 Создано 20/5/2019, 10:11:09 تم النشر ب- 20/5/2019, 10:11:09|
|The grades for the first assignment are available online. |
The graded papers will be available at the secretariat tomorrow.
Appeals should be sent to Inbar by e-mail no later than May 27.
|פורסם ב- 13/5/2019, 12:44:20 Created on 13/5/2019, 12:44:20 Создано 13/5/2019, 12:44:20 تم النشر ب- 13/5/2019, 12:44:20|
|The list of papers for the final project is now available under the syllabus tab of the website. Note that you are welcome (pending my approval) to choose papers that you think are relevant but are not on the list.|
To choose a paper please press the following link and fill out the form (specifying the names of the student and the index of the selected paper):
Important: Please choose a paper that hasn't already been selected. You can look at the following link to see which papers were already selected:
|פורסם ב- 30/4/2019, 15:29:31 Created on 30/4/2019, 15:29:31 Создано 30/4/2019, 15:29:31 تم النشر ب- 30/4/2019, 15:29:31|
|For those who want to read a bit more about promise problems, I recommend Section 2.4.1 (Page 93) here:|
|פורסם ב- 30/4/2019, 13:31:18 Created on 30/4/2019, 13:31:18 Создано 30/4/2019, 13:31:18 تم النشر ب- 30/4/2019, 13:31:18|
Interview of Avi Wigderson
|Here is the link:|
I recommend watching the entire thing but the relevant part about ZK starts at 25:20 and lasts about 4 minutes.
|פורסם ב- 16/4/2019, 12:34:47 Created on 16/4/2019, 12:34:47 Создано 16/4/2019, 12:34:47 تم النشر ب- 16/4/2019, 12:34:47|
A couple of clarifications about Exercise 1
|1. In Question 3.1 you may use (without proving) that every language in PSPACE has an interactive proof with perfect completeness (we saw this in class for coNP and handwaved for PSPACE).|
2. In Question 4, the solution that I have in mind uses the sumcheck protocol as a blackbox.
3. In Question 4: some students were wondering if F is a fixed finite field of a single size (say |F|=17) and if so then it seems that O(n*d/|F|) is bigger than 1 and that doesn't make sense. The answer is that F is *not* fixed but rather the lemma should hold for any sufficiently large field F (as a function of n and d).
|פורסם ב- 15/4/2019, 14:12:58 Created on 15/4/2019, 14:12:58 Создано 15/4/2019, 14:12:58 تم النشر ب- 15/4/2019, 14:12:58|
No class on 9/4
|Reminder: next Tuesday (9/4) is election day so the class is canceled.|
|פורסם ב- 4/4/2019, 09:56:44 Created on 4/4/2019, 09:56:44 Создано 4/4/2019, 09:56:44 تم النشر ب- 4/4/2019, 09:56:44|
First problem set has been posted
|Due 18/4/2019 at 4pm. Please submit to Inbar's physical mailbox (#154).|
|פורסם ב- 3/4/2019, 15:15:19 Created on 3/4/2019, 15:15:19 Создано 3/4/2019, 15:15:19 تم النشر ب- 3/4/2019, 15:15:19|