BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-11402@webedit.cs.cornell.edu
DTSTAMP:20201214T212000Z
DTSTART:20201214T212000Z
DTEND:20201214T222000Z
SUMMARY:Concentration Bounds for Almost k-wise Independence with Applications to Non-Uniform Security
DESCRIPTION:Siyao Guo, NYU Shanghai. Concentration Bounds for Almost k-wise Independence with Applications to Non-Uniform Security (via Zoom)Abstract: We prove a few concentration inequalities for the sum of n binary random variables under weaker conditions than k-wise independence. Namely, we consider two standard conditions that are satisfied in many applications: (a) direct product conditions (b) XOR condition. Both conditions are weaker than mutual independence and both imply strong concentration bounds (similar to Chernoff-Hoeffding) on the tail probability of the sum of bounded random variables ([Impagliazzo and Kabanets, APPROX-RANDOM 10], [Unger, FOCS 09]). Our inequalities can be stated as the implication of threshold direct product theorems from either k-wise direct product conditions, or the k-wise XOR condition. By proving optimality of our inequalities, we show a clear separation for k≪n between k-wise product conditions and XOR condition as well as a stark contrast between k-wise and n-wise...https://webedit.cs.cornell.edu/content/concentration-bounds-almost-k-wise-independence-applications-non-uniform-security
LOCATION:Streaming via Zoom
END:VEVENT
END:VCALENDAR