Another clarification | |
| 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 |
HW1 Grades | |
| 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 |
Final Project | |
| 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): https://docs.google.com/forms/d/e/1FAIpQLSdhn3vrSEkVRn3ZfAZW3Rf1fjJ3rH-NVyS0lz7U6d4AboIaXw/viewform?usp=sf_link 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: https://docs.google.com/spreadsheets/d/1Gl-OFPaR4SO_GwN76zbO2vlBmLK4ojivpQDhJvzq88c/edit?usp=sharing |
| פורסם ב- 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 |
Promise problems | |
| For those who want to read a bit more about promise problems, I recommend Section 2.4.1 (Page 93) here: http://www.wisdom.weizmann.ac.il/~oded/CC/r1.pdf |
| פורסם ב- 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: https://www.youtube.com/watch?v=-GQnK6ys6C0&t=1774s 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 |