BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Brute force searching\, the typical set and Guesswork
DTSTART:20130620T100000
DTEND:20130620T110000
DTSTAMP:20261001T173711Z
UID:7c70473d34db1e4ce8a82bed32a1067e0ed662e2c24ebe7e94ec08ba
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Ken Duffy\, National University of Ireland Maynooth\nTh
 e talk explores murky water between computational security\, probability a
 nd information theory. If an object is selected from a finite list and an 
 inquisitor can ask "is the object X"\, in cryptography it is deemed to be 
 computationally secure so long as the list is large enough. Implicit in th
 is is there is no prior information known to the inquisitor about the dist
 ribution of the object that selected.\nThe two questions this talk address
 es are: if the object was selected stochastically with probabilistic prope
 rties known to the inquisitor\, what is the distribution for how many atte
 mpts it takes them to correctly guess the object? If the object is selecte
 d from a source subject to typical set coding\, does the Asymptotic Equipa
 rtition Property mean we can assume it was uniformly distributed?\nBuildin
 g on curious work that began with J. Massey in '94 and E.\nArikan in '96 (
 with a significant contribution from EPFL's Charles Pfister\, in collabora
 tion with W. Sullivan in '04)\, answering the first question gives a surpr
 ising estimate\, related to stochastic orders\, based on a Legendre-Fenche
 l transform of a function of Renyi entropy. Worryingly\, the second answer
  transpires to be negative:\nthe uniform AEP ansatz leads to a guessing pr
 oblem that's exponentially harder in word length than the true typical set
  guesswork problem.\nThis talk is based on work with M. Christiansen (NUIM
 )\, as well as with F. du Pin Calmon & M. Medard (MIT).
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR