# user8477

 Jul 3 comment What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?Well, if as you said, you set $P_{param}(C|p=0)$ to a sufficiently small value instead of 0, then $D_{KL}(P_{data}(.)||P_{param}(.|p=0))$ will be well defined and arbitrarily large. When I gave my example I thought of the $D_{KL}$ as being "infinite" instead of undefined, but by choosing a sufficiently small value for $P_{param}(C|p=0)$ you can get around this problem. Jul 2 comment What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?Now it's clear that you should estimate the value of the parameter p to be 1, not 0, since you have 'C' characters in your data. But if you minimize $D_{KL} (P_{parameter}||P_{data})$ you will choose instead the value 0 for p. Jul 2 comment What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?You will get a set of parameter resulting in a distribution $P_{parameters}$, that, had it been the true distribution, would have made the cost of assuming $P_{data}$ instead of $P_{distribution}$ minimal. An example: suppose you want to estimate the frequency of each character 'A','B' and 'C' in a stream in order to compress it with a Huffman code. if the parameter p has value 1, then $Prob('A') = 0.5, Prob('B') = 0.45, Prob('C') = 0.05$, and if parameter p has value 0, then $Prob('A') =.5, Prob('B') =0.5, Prob('C') = 0$. Also, $P_{data}(A)=0.5, P_{data}(B)=0.499, P_{data}(C) = 0.001$ Jul 2 comment Can decoying provide security against traffic analysis?Now if Eve only identified Alices that are consecutive in the random walk, Eve doesn't have a chance much better than $1/(d-1)$ of identifying the next Alice. If on the other hand, she identified two Alices separated by a single node on the random walk, it will be much easier to find the middle node. In general, given two discovered Alices and the length $l$ of the path between them, the ability of Eve to determine the path between them depends on how many paths of length $l$ exist between these two Alices. This number grows exponentially with $l$. Jul 2 comment Can decoying provide security against traffic analysis?Well, it seems to me that a natural generalization of your scheme is as follows. Construct a regular expander graph of size N. Choose a node at random and assign it to one of the Alices. Then from that node, start a self-avoiding random-walk of size n. Those nodes are assigned to the Alices. The Bobs are randomly assigned to the remaining nodes. Each node talks only to its immediate neighbor in the graph. Obviously the security of this scheme depends on the degree $d$ of the graph. Feb 11 awarded Supporter Feb 9 comment Exponential Speedup in External MemoryI don't have any argument for intermediate values. At a very superficial level, I guess that some backtracking algorithms would have an exponential dependence on the memory size because I/O operations would be required at nodes of lower depth in the search tree. This dependence would apply to intermediate values. This says nothing about the inherent complexity of the problem, of course. Also, if you have $M=\omega(\log N)$, the pigeonhole (cycling) argument given above would still yield a gain of $T(N)/2^M$ where $T(N)$ is the time complexity of the problem. Feb 9 comment Exponential Speedup in External MemoryI don't understand why any problem in external memory is trivial if $M = \Omega(N)$. If $M=N/2$ and the algorithm takes, exponential time, you might be forced to swap back and forth between (so to speak) the two halves of the memory an exponential number of times. Feb 9 awarded Teacher Feb 8 answered Exponential Speedup in External Memory May 22 answered Is 0-1 programming with constant number of constraints polynomially solvable? Apr 26 answered Optimality of Greedy algorithm for minimization Knapsack Problem