AvAlg HW2

\begin{equation} 2^{n+1}/2=2^{n}\\ \rightarrow\textrm{Two parts of size }2^{n}\\ \textrm{i.e.:}\\ 1.\{1,...,2^{n}\}\\ 2.\{2^{n}+1,...,2^{n+1}\}\\ \textrm{Shift the ranges one step down and we get:}\\ 1.\{0,...,2^{n}-1\}\\ 2.\{2^{n},...,2^{n+1}-1\}\\ \\ \end{equation}

Actually, we can express Theorem 1.2 in terms of Theorem 1.1:

\begin{equation} x_{1},y_{1}\textrm{from Theorem 1.1; }x_{2},y_{2}\textrm{ from Theorem 1.2}\ \\ x_{2},y_{2}\in\{2^{n},...2^{n+1}-1\}\textrm{ & }\ x_{1},y_{1}\in\{0,...,2^{n}-1\}\\ \rightarrow x_{2}=x_{1}+2^{n}\textrm{ & }\ y_{2}=y_{1}+2^{n}\\ \rightarrow x_{2}=y_{2}\rightarrow x_{1}+2^{n}=y_{1}+2^{n}\rightarrow\textrm{proceed to break out }2^{n}\textrm{ in the relation based on Theorem 1.1.}\\ \\ \end{equation}

This also means that the range of possible values of the modulo operator in f will also range the same as in Theorem 1.1; which therefore follows (as multiplying by the argument of previously same range, results in a linear raise of the codomain) the codomain of f in Theorem 1.2.

We can therefore state that for Theorem 1.2 in relation to Theorem 1.1 that sense:

  • The range for x and y is of the same size and the new range is still linear.
  • Sense the range for x and y is of the same size and still linear, mod p will have the same codomain as in Theorem 1.1.
  • The codomain of f is linearly transformed from Theorem 1.1 to 1.2 by the change in range for x and y.
  • As we have shown that that instances of Theorem 1.2 can always be described as a instance of Theorem 1.1; 1.2 will inherent the properties of Theorem 1.1.
  • As we are primarily concerned with the relationship between the values of x and y rather than their actual numerical, we can state that Theorem 1.2 must be true on the same basis of why Theorem 1.1 is true. Our expression of 1.2 doesn't affect that; hence Theorem 1.2 will have the same properties as Theorem 1.1.

\begin{equation} f(x) = x\textrm{ }mod \textrm{ }{p} \end{equation}


Consider the streaming algorithm for the 1-sparse recovery problem in a non-negative dynamic stream we discussed in class. Show that the same algorithm does not work for case of dynamic stream (give an explicit input stream where the algorithm does not work). Remark: Recall that a stream is 1-sparse as long as 1 number remains, regardless of the sign. For example, stream (4,-) is 1-sparse. Stream (1, -), (1, -) is also 1-sparse.

Let's first define the terms of 1-sparse recovery as defined in the lectures and in DD2440 – Summary of algorithms by Arvid Fahlström Myrman:

  • Given: m items
  • For each item in the stream, calculate a bitsum according to the sign in the items.
  • Add 1 + /log n counters for each bit present during the stream. Also include one counter c_0 for the entire stream that increment and decrement respectively for each sign encountered. When calculating the bitsum the counters will be incremented or decremented together with their respective bit.
  • In the end of the stream, if all bit counters are either c or 0, return the number whose binary representation corresponds to the counters after dividing all counters by c. Otherwise, return not 1-sparse. The goal is that only *one** of the values should be left in the stream should return a value if the stream is 1-sparse.

We can consider c0 to be a counter that helps distinguish values from their bit representation as a whole or as a combination of multiple values; example: $(1,0,1){2} = (1,0,0){2} + (0,0,1){2} || (1,1,1){2} - (0,1,0){2} || ... $ This is done by tracking of the bitsum is changed by each item in the stream. However, if this is used on a dynamic stream (i.e. not a non-negative dynamic stream), the possible combinations for a value, positive or negative, becomes to many to be accounted by a single variable when calculating the bitsum. The result becomes that when a given stream is given and the bitsum is calculated, when given an non-dynamic stream, sense the bitsum can be generated with any combination of addition/subtraction, the current model can't ensure to keep track of that change through a single variable. A example of such a stream would be: . If we use this on a dynamic stream we can see that sense there are no restraint that when reading from the stream, no amount of