University of Cambridge > Talks.cam > Algorithms and Complexity Seminar > Incompressibility and Next-Block Pseudoentropy

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Incompressibility and Next-Block Pseudoentropy

Download to your calendar using vCal

If you have a question about this talk, please contact Tom Gur .

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 analogs of entropy such as pseudoentropy (Hastad, Impagliazzo, Levin, and Luby [SICOMP 99]), and to other cryptographic hardness assumptions, was unclear.

We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k-2) bits of next-block pseudoentropy, 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.

Joint work with Iftach Haitner and Jad Silbak.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

SN08, Computer Laboratory, William Gates Building Arts Picturehouse, 38-39 St. Andrews Street, CB2 3AR Tilley Lecture Theater, Department of Earth Sciences

Other talks

A novel hereditary encephalopathy in four related Labrador Retrievers associated with a missense variant in the ALDH5A1 gene’ Trigger-Level Analysis at ATLAS Title TBC TBC Title to be confirmed Carrollian momenta from anti de Sitter
 

© 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity