Campus Event Calendar
Event Entry
What and Who
Lower Bounds via Sampling Algorithms
Chinmoy Dutta
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 29 September 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We discuss how lower bounds can be obtained for noisy
computation models by simulating the noise with "sampling algorithms".
Using this method, we obtain elementary proofs of the Evans-Pippenger
lower bounds on the depth of noisy decision trees. We also prove tight
lower bounds on the number of broadcasts needed to compute functions
like parity and majority in a wireless sensor network.
Contact
Chinmoy Dutta
--email hidden
passcode not visible
logged in users only
Chinmoy Dutta, 09/28/2009 10:47
Chinmoy Dutta, 09/28/2009 10:20 -- Created document.
Chinmoy Dutta, 09/28/2009 10:20 -- Created document.