BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Incompressibility and Next-Block Pseudoentropy  - Noam Mazor (Tel-
 Aviv University)
DTSTART:20240521T100000Z
DTEND:20240521T110000Z
UID:TALK217039@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Abstract: A distribution is k-incompressible\, Yao [FOCS ’82
 ]\, if no efficient compression scheme compresses it to less than k bits. 
 While being a natural measure\, its relation to other computational analog
 s of entropy such as pseudoentropy (Hastad\, Impagliazzo\, Levin\, and Lub
 y [SICOMP 99])\, and to other cryptographic hardness assumptions\, was unc
 lear.\n\nWe advance towards a better understating of this notion\, showing
  that a k-incompressible distribution has (k-2) bits of next-block pseudoe
 ntropy\, a refinement of pseudoentropy introduced by Haitner\, Reingold\, 
 and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that 
 is (H(X) + 2)-incompressible\, implies the existence of one-way functions.
 \n\nJoint work with Iftach Haitner and Jad Silbak.
LOCATION:Computer Laboratory\, William Gates Building\, Room FS07
END:VEVENT
END:VCALENDAR