Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions

Speaker: Jad Silbak

Date: Friday, December 15, 2023

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G-882, Hewlett Room

Event Type: Seminar

Room Description:

Host: Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs

Contact:

Relevant URL: https://toc.csail.mit.edu/node/428

Speaker URL: https://sites.google.com/view/jadsilbak/home

Speaker Photo:

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions

Guruswami and Smith (J. ACM 2016) considered codes for channels that are computationally bounded which modify at most a p-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon’s binary symmetric channel which flips each bit independently with probability p, but weaker than Hamming’s channels which may flip any p-fraction of bits and are computationally unbounded.

Recently, there has been a growing body of work that aims to construct codes against channels that are computationally bounded (e.g., bounded memory channels, channels that are poly-size circuits). In this work, we consider bounded size channels and construct codes that:
- Achieve an optimal rate of 1-H(p) (matching the rate of binary symmetric channels, and beating the rate of Hamming channels).
- Are explicit, assuming E does not have a size 2^Ω(n) nondeterministic circuits.

Achieving these codes implies circuit lower bounds (and therefore explicit constructions need to be based on hardness assumptions). This result builds on the recent result by Shaltiel and Silbak (FOCS 2022) that gave a randomized Monte-Carlo construction, rather than explicit codes.

A key component in our codes (that we believe to be of independent interest) is a new complexity theoretic notion of hard to sample functions (HTS).
Loosely speaking, a function f is HTS for circuits of size n^c, if for every randomized circuit A of size n^c that samples a distribution (X,Y) such that X has sufficiently large min-entropy, it holds that Pr[Y=f(X)] is small.
This notion is inspired by a related notion introduced by Viola (SICOMP 2012) in which X is the uniform distribution and is similar in flavor to the definition of multi-collision-resistant hash functions. Building on classical works on “hardness amplification” (and using many additional tools and ideas from pseudorandomness) we construct HTS functions under hardness assumptions.

This is a joint work with Ronen Shaltiel.

Research Areas:

Impact Areas:

See other events that are part of the CIS Seminar Series 2023 - 2024.

Created by Megan F Farmer at Friday, December 08, 2023 at 9:32 AM.