Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions
Speaker
Host
Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs
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.
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.