Typo in question 1.2

[edo]

Hi Class,
There is a typo in question 1.2
The assumption that Var[A(x)] <= c f(x) is not what I meant.

It should be that:
Var[A(x)] <= c f^2(x)
(the square on f(x) was missing)

Sorry about that, I'll post a corrected assignment Sunday.
Edo

[shlomih]

regarding the question (1.2), are epsilon and delta part of the input
of the algorithm for B2?
i.e, should we get a different algorithm for B2 with different epsilon
and delta?

Shlomi

[Edo Liberty]

you got it right.
Esp and delta are in a sense inputs to B_2

[Yaara]

Hi,
Can we assume different calls to A (with the same x) are i.i.d?
Thanks,
Yaara

On Jan 21, 4:06 pm, Edo Liberty <edo.libe...@gmail.com> wrote:
> you got it right.
> Esp and delta are in a sense inputs to B_2

[Edo Liberty]

They are i.i.d., aren't they?

[shlomih]

can we assume we know the exact value of c?

On 21 ינואר, 19:18, Edo Liberty <edo.libe...@gmail.com> wrote:
> They are i.i.d., aren't they?

> > > > > Edo-הסתר טקסט מצוטט-
>
> -הראה טקסט מצוטט-

[Lior Teller]

Hi,

Regarding question 2 part 3.

According to wikipedia  http://en.wikipedia.org/wiki/Matrix_norm, ||A||fro = ||A||2.

I assume that the numerical rank of a matrix is not always 1..

What am I missing here?

[Edo Liberty]

Hi Lior
I think your are looking at the "entrywize" section....

The 2 norm is the spectral norm which is the largest singular value.
The Fro norm is the square root of the sum of squared entries in the matrix. They are not the same.

Think about the identity matrix.
||I_n||_2 = 1
||I_n||_Fro = sqrt(n)
Hope it helps
Edo