Hi,

we were asked to solve t queries in time O(klogt)*(2^k+t). However, it seems that a trivial algorithm can solve this in time O(t * 2^k) by brute-forcing each challenge. What am I missing?

HW 2 Q2A

*Instructor:*- Nir Bitansky
*Lectures:*- Dach, Wednesday 15:00 - 18:00
*Teaching assistant:*- Eliad Tsfadia
*Recitations:*- Holtzblat, Sunday 11:00 - 12:00, 12:00 - 13:00

*Assignment 5 due*: June 12*Exam*: June 28*Moed B*: September 26

**Example Exam - revised version and solutions**

*Edited Q1a and Q2c*

(23 Jun 2019 07:19)

**Example Exam**

*Solutions will be posted by Monday next week.*

(20 Jun 2019 19:09)

**Exam header**

*So that you don't need to waste time on instructions during the exam.*

(11 Jun 2019 18:45)

2.b. In an expected number of 10 rounds the attacker will be the leader. At this point, it can...

(by nbitansky 28 Jun 2019 00:37, posts: 2)

(by nbitansky 28 Jun 2019 00:37, posts: 2)

- $3$-message protocols (without any repetition) has soundness $1/2$. Doesn't have FS. (This is...

(by nbitansky 27 Jun 2019 13:34, posts: 5)

(by nbitansky 27 Jun 2019 13:34, posts: 5)

Hi, can you please give us an answer sketch for HW 5 Q2 section b, and for Q3 section a?
I asked...

(by daniel (guest) 27 Jun 2019 11:23, posts: 2)

(by daniel (guest) 27 Jun 2019 11:23, posts: 2)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License