Re: Irregular review procedures for IACR sponsored conferences

Kristian Gjøsteen <kristiag+news@xxxxxxxxxxxx>:

The second says that if you apply the map to an arbitrary but sufficiently
long string, substrings of the image are uniformly distributed. This
can obviously not be true, since the map is a bijection and there must
be a string that maps to the all-zeros string.

This appears to be a misunderstanding. The theorem is not about
looking at different substrings of a fixed output, as you seem to
assume. Instead, we have to consider the output as a random variable,
and look at the substring found at a fixed position within this
output.

(The theorem still can't be true as claimed. If the input has a
biased distribution, then an appropriate post-processing algorithm can
achieve close-to-uniform distribution for such substrings, but in
general not a perfectly uniform distribution because in general the
input probability space may not have a partition into events of the
appropriate probability.)
.

Relevant Pages

  • Re: Irregular review procedures for IACR sponsored conferences
    ... long string, substrings of the image are uniformly distributed. ... since the map is a bijection and there must ... The uniform distribution of the substrings in the output ...
    (sci.crypt)
  • Re: Irregular review procedures for IACR sponsored conferences
    ... long string, substrings of the image are uniformly distributed. ... there exists an n (depending on the input distribution) ... general not a perfectly uniform distribution because in general the ...
    (sci.crypt)
  • Re: Less is not More
    ... not produce an increase in the string's KC toward its maximum upper ... You are implying that larger substrings have constant or ... digits of computable constant X" with n as an argument, ... 24 ways I can concatenate them once each into a single string, ...
    (talk.origins)
  • Re: (?{..}) and lexical scoping issues.
    ... > @_ is most definitely a package variable. ... > (You are counting how many substrings of each string are also substrings ... > all substrings of a string. ... it will be hard to beat with a Perl program. ...
    (comp.lang.perl.misc)
  • Re: Einlesen einer GROSSEN Textdatei
    ... In Wirklichkeit gibt es knapp 50 Substrings, ... muss ich den String vorher leeren. ... zeilenBean = new MeineZeilenBean; ... anzahlVorkommen = errorCount1; ...
    (de.comp.lang.java)