Yao’s XOR lemma states that for every function
f
:
{
0
,
1
}
k
→
{
0
,
1
}
, if
f
has hardness 2/3 for
P
/
poly
(meaning that for every circuit
C
in
P
/
poly
,
Pr
C
(
X
)
=
f
(
X
)
≤
2
/
3
on a ...uniform input
X
), then the task of computing
f
(
X
1
)
⊕
…
⊕
f
(
X
t
)
for sufficiently large
t
has hardness
1
2
+
ϵ
for
P
/
poly
.
Known proofs of this lemma cannot achieve
ϵ
=
1
k
ω
(
1
)
, and even for
ϵ
=
1
k
, we do not know how to replace
P
/
poly
by AC
0
parity
(the class of constant depth circuits with the gates {
and, or, not, parity
} of unbounded fan-in).
Grinberg, Shaltiel and Viola (FOCS 2018) (building on a sequence of earlier works) showed that these limitations cannot be circumvented by
black-box reductions
. Namely, by reductions
Red
(
·
)
that given oracle access to a function
D
that violates the conclusion of Yao’s XOR lemma, implement a circuit that violates the assumption of Yao’s XOR lemma.
There are a few known reductions in the related literature on worst-case to average-case reductions that are
non-black-box
. Specifically, the reductions of Gutfreund, Shaltiel and Ta-Shma (Computational Complexity 2007) and Hirahara (FOCS 2018)) are “class reductions” that are only guaranteed to succeed when given oracle access to an oracle
D
from some efficient class of algorithms. These works seem to circumvent some black-box impossibility results.
In this paper, we extend the previous limitations of Grinberg, Shaltiel and Viola to several types of class reductions, giving evidence that class reductions cannot yield the desired improvements in Yao’s XOR lemma. To the best of our knowledge, this is the first limitation on reductions for hardness amplification that applies to class reductions.
Our technique imitates the previous lower bounds for black-box reductions, replacing the inefficient oracle used in that proof, with an efficient one that is based on limited independence, and developing tools to deal with the technical difficulties that arise following this replacement.
A stochastic code is a pair of encoding and decoding procedures (Enc, Dec) where
Enc
:
{
0
,
1
}
k
×
{
0
,
1
}
d
→
{
0
,
1
}
n
. The code is (
p, L
)-list decodable against a class
C
of “channel ...functions”
C
:
{
0
,
1
}
n
→
{
0
,
1
}
n
if for every message
m
∈
{
0
,
1
}
k
and every channel
C
∈
C
that induces at most
pn
errors, applying Dec on the “received word”
C
(Enc(
m,S
)) produces a list of at most
L
messages that contain
m
with high probability over the choice of uniform
S
←
{
0
,
1
}
d
. Note that both the channel
C
and the decoding algorithm Dec do not receive the random variable
S
, when attempting to decode. The rate of a code is
R
=
k
/
n
, and a code is explicit if Enc, Dec run in time poly(
n
).
Guruswami and Smith (Journal of the ACM, 2016) showed that for every constants
0
<
p
<
1
2
,
ϵ
>
0
and
c
>
1
there exist a constant
L
and a Monte Carlo explicit constructions of stochastic codes with rate
R
≥
1
-
H
(
p
)
-
ϵ
that are (
p, L
)-list decodable for size
n
c
channels. Here, Monte Carlo means that the encoding and decoding need to share a public uniformly chosen
poly
(
n
c
)
bit string
Y
, and the constructed stochastic code is (
p, L
)-list decodable with high probability over the choice of
Y
.
Guruswami and Smith pose an open problem to give fully explicit (that is not Monte Carlo) explicit codes with the same parameters, under hardness assumptions. In this paper, we resolve this open problem, using a minimal assumption: the existence of poly-time computable pseudorandom generators for small circuits, which follows from standard complexity assumptions by Impagliazzo and Wigderson (STOC 97).
Guruswami and Smith also asked to give a fully explicit unconditional constructions with the same parameters against
O
(
log
n
)
-space online channels. (These are channels that have space
O
(
log
n
)
and are allowed to read the input codeword in one pass.) We also resolve this open problem.
Finally, we consider a tighter notion of explicitness, in which the running time of encoding and list-decoding algorithms does not increase, when increasing the complexity of the channel. We give explicit constructions (with rate approaching
1
-
H
(
p
)
for every
p
≤
p
0
for some
p
0
>
0
) for channels that are circuits of size
2
n
Ω
(
1
/
d
)
and depth
d
. Here, the running time of encoding and decoding is a polynomial that does not depend on the depth of the circuit.
Our approach builds on the machinery developed by Guruswami and Smith, replacing some probabilistic arguments with explicit constructions. We also present a simplified and general approach that makes the reductions in the proof more efficient, so that we can handle weak classes of channels.
We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial
compression algorithms
for “easy” Boolean functions from the corresponding circuit classes. The ...compression problem is defined as follows: given the truth table of an
n
-variate Boolean function
f
computable by some
unknown small circuit
from a
known class
of circuits, find in deterministic time poly(2
n
) a circuit
C
(no restriction on the type of
C
) computing
f
so that the size of
C
is less than the trivial circuit size
2
n
/
n
. We get non-trivial compression for functions computable by AC
0
circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known.
These compression algorithms rely on the structural characterizations of “easy” functions, which are useful both for proving circuit lower bounds and for designing “meta-algorithms” (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the “shrinkage under random restrictions” results by Subbotovskaya (Doklady Akademii Nauk SSSR 136(3):553–555,
1961
) and Håstad (SIAM J Comput 27:48–64,
1998
), strengthened to the “high-probability” version by Santhanam (Proceedings of the Fifty-First Annual IEEE Symposium on Foundations of Computer Science, pp 183–192,
2010
), Impagliazzo, Meka & Zuckerman (Proceedings of the Fifty-Third Annual IEEE Symposium on Foundations of Computer Science, pp 111–119,
2012b
), and Komargodski & Raz (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 171–180,
2013
). We give a new, simple proof of the “high-probability” version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about
n
2
. We also use this shrinkage result to get an alternative proof of the result by Komargodski & Raz (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 171–180,
2013
) of the average-case lower bound against small (de Morgan) formulas.
Finally, we show that the existence of any non-trivial compression algorithm for a circuit class
C
⊆
P
/
poly
would imply the circuit lower bound
NEXP
⊈
C
; a similar implication is independently proved also by Williams (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 21–30,
2013
). This complements the result by Williams (Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, pp 231–240,
2010
) that any non-trivial Circuit-SAT algorithm for a circuit class
C
would imply a superpolynomial lower bound against
C
for a language in NEXP.
Codes for poly-size circuits: Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits 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 (BSC), but weaker than Hamming’s channels which are computationally unbounded. The goal of this direction is to construct explicit codes (namely, codes with poly-time encoding and decoding algorithms) with rate R(p)=1−H(p) (matching the capacity of the BSC, and beating the capacity of codes for Hamming’s channels). This goal implies circuit lower bounds, and specifically that E=DTIME(2O(n)) does not have poly-size circuits (and therefore explicit constructions need to be based on hardness assumptions). We give the first explicit construction of such codes for poly-size channels. Specifically, for every 0 ≤ p < 1/4, there are explicit codes with rate R(p)=1−H(p), assuming E does not have size 2Ω(n) nondeterministic circuits. This hardness assumption was introduced in the context of hardness vs. randomness tradeoffs, and is by now standard in complexity theory. Our result builds on, and improves the previous work of Guruswami and Smith, and Shaltiel and Silbak (FOCS 2022). (These works gave a randomized Monte-Carlo construction, rather than explicit codes). Functions that are hard to sample on low entropy distributions: A key component in our codes (that may be of independent interest) is a new complexity theoretic notion of hard to sample functions (HTS): We say that a function f on n bits is an HTS for circuits of size nc, if there exists a constant c′>c, such that for every randomized circuit A of size nc that samples a distribution (X,Y) with (X) ≥ c′ · logn, it holds that PrY=f(X) ≤ 1/nc. This is inspired by works by Viola on the complexity of distributions (SICOMP 2012, 2020), in which X is the uniform distribution. Here, we allow A to choose any distribution X (except for distributions X with very low min-entropy) and note that a circuit A of size nc, may be hardwired with ≈ nc outputs of f, and therefore, can easily produce pairs (X,f(X)) for a distribution X, with (X) ≈ c logn. Building on classical works on “hardness amplification” (and using many additional tools and ideas from pseudorandomness) we show that if E does not have size 2Ω(n) nondeterministic circuits, then for every constant c, there is an HTS that is computable in time (nc). Our codes are obtained by using our HTS (as well as additional tools and ideas) to achieve explicit constructions (under the hardness assumption) of several components in the code of Shaltiel and Silbak, replacing previously obtained randomized Monte-Carlo constructions of these components. We then need to revisit the codes of Shaltiel and Silbak, and significantly modify the construction and analysis, so that they work with the weaker components that we are able to explicitly construct.
The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of ...“typically-correct” deterministic simulations, which are allowed to err on few inputs. In this paper, we further the study of typically-correct derandomization in two ways.
First, we develop a generic approach for constructing typically-correct derandomizations based on seed-extending pseudorandom generators, which are pseudorandom generators that reveal their seed. We use our approach to obtain both conditional and unconditional typically-correct derandomization results in various algorithmic settings. We show that our technique strictly generalizes an earlier approach by Shaltiel based on randomness extractors and simplifies the proofs of some known results. We also demonstrate that our approach is applicable in algorithmic settings where earlier work did not apply. For example, we present a typically-correct polynomial-time simulation for every language in BPP based on a hardness assumption that is (seemingly) weaker than the ones used in earlier work.
Second, we investigate whether typically-correct derandomization of BPP implies circuit lower bounds. Extending the work of Kabanets and Impagliazzo for the zero-error case, we establish a positive answer for error rates in the range considered by Goldreich and Wigderson. In doing so, we provide a simpler proof of the zero-error result. Our proof scales better than the original one and does not rely on the result by Impagliazzo, Kabanets, and Wigderson that NEXP having polynomialsize circuits implies that NEXP coincides with EXP.
We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for "easy" Boolean functions from the corresponding circuit classes. The ...compression problem is defined as follows: given the truth table of an n-variate Boolean function f computable by some unknown small circuit from a known class of circuits, find in deterministic time poly(2 n ) a circuit C (no restriction on the type of C) computing f so that the size of C is less than the trivial circuit size 2 n /n. We get nontrivial compression for functions computable by AC 0 circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known. These compression algorithms rely on the structural characterizations of "easy" functions, which are useful both for proving circuit lower bounds and for designing "meta-algorithms" (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the "shrinkage under random restrictions" results 52, 21, strengthened to the "high-probability" version by 48, 26, 33. We give a new, simple proof of the "high-probability" version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about n 2 . We also use this shrinkage result to get an alternative proof of the recent result by Komargodski and Raz 33 of the average-case lower bound against small (de Morgan) formulas. Finally, we show that the existence of any non-trivial compression algorithm for a circuit class C ⊆ P/poly would imply the circuit lower bound NEXP ⊈ C. This complements Williams's result 55 that any non-trivial Circuit-SAT algorithm for a circuit class C would imply a superpolynomial lower bound against C for a language in NEXP1.
this paper studies the complexity of black-box proofs of hardness amplification. A class of circuits D proves a hardness amplification result if for any function h that agrees with Amp(f) on a ... ...fraction of the inputs there exists an oracle circuit ... such that Dh agrees with f on a 1 - δ fraction of the inputs. The researchers focus on the case where every ... makes nonadaptive queries to h. This setting captures most hardness amplification techniques. They prove two main results: (1) The circuits in D "can be used" to compute the majority function on ... bits. In particular, when ... cannot consist of oracle circuits that have unbounded fan-in, size poly(n), and depth O(1). (2) The circuits in D must make ... oracle queries. Both their bounds on the depth and on the number of queries are tight up to constant factors.
Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits 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 (BSC), but weaker than Hamming's channels which are computationally unbounded. Guruswami and Smith gave an explicit Monte-Carlo construction of codes with optimal rate of R(p) = 1 − H(p) that achieve list-decoding in this scenario. Here, "explicit Monte-Carlo" means that both encoding and decoding algorithms run in polynomial time. However, the encoding and decoding algorithms also receive a uniformly chosen string of polynomial length (which is chosen and published, once and for all, in a pre-processing stage) and their correctness is guaranteed w.h.p. over this random choice. Guruswami and Smith asked whether it is possible to obtain uniquely decodable codes for poly-size channels with rate that beats the Gilbert-Varshamov bound R^{GV}(p)=1-H(2p). We give an affirmative answer, Specifically:*For every 0\leq p\lt\frac{1}{4}, we give an explicit Monte-Carlo construction of uniquely-decodable codes with optimal rate R(p) = 1 − H(p). This matches the rate achieved by Guruswami and Smith for the easier task of list-decoding, and also matches the capacity of binary symmetric channels. Moreover, this rate is strictly larger than that of codes for the standard coding scenario (namely, uniquely-decodable codes for Hamming channels).*Even ignoring explicitness, our result implies a characterization of the capacity of poly-size channels, which was not previously understood.Our technique builds on the earlier list-decodable codes of Guruswami and Smith, achieving unique-decoding by extending and modifying the construction so that we can identify the correct message in the list. For this purpose we use ideas from coding theory and pseudorandomness, specifically:*We construct codes for binary symmetric channels that beat the Gilbert-Varshamov bound, and are "evasive" in the sense that a poly-size circuit that receives a random (or actually pseudorandom) string, cannot find a codeword within relative distance 2p. This notion of evasiveness is inspired by the recent work of Shaltiel and Silbak (STOC 2021) on codes for space bounded channels.*We develop a methodology (that is inspired by proofs of t-wise independent tail inequalities, and may be of independent interest) to analyze random codes, in scenarios where the success of the channel is measured in an additional random experiment (as in the evasiveness experiment above).*We introduce a new notion of "small-set non-malleable codes" that is tailored for our application, and may be of independent interest.
We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming ...(adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a p fraction of the bits of the codeword.
(1) Explicit uniquely decodable codes for space bounded channels: Our main result is that for every 0 ≤ p < 1/4, there exists a constant δ>0 and a uniquely decodable code with rate 1−H(p) for channels with space nδ. This code is explicit (meaning that encoding and decoding are in poly-time). This improves upon previous explicit codes by Guruswami and Smith, and Kopparty, Shaltiel and Silbak (FOCS 2019). Specifically, we obtain the same space and rate as earlier works, even though prior work gave only list-decodable codes (rather than uniquely decodable codes).
(2) Complete characterization of the capacity of space bounded channels: Together with a result by Guruswami and Smith showing the impossibility of unique decoding for p ≥ 1/4, our techniques also give a complete characterization of the capacity R(p) of space n1−o(1) channels, specifically: For 0≤p<1/4 R(p)=1-H(p) and for p ≥1/4 R(p)=0. This capacity is strictly larger than the capacity of Hamming channels for every 0 < p < 1/4, and matches the capacity of list decoding, and binary symmetric channels in this range. Curiously, this shows that R(·) is not continuous at p=1/4.
Our results are incomparable to recent work on casual channels (these are stronger channels that read the codeword in one pass, but there is no space restriction). The best known codes for casual channels, due to Chen, Jaggi and Langberg (STOC 2015), are shown to exist by the probabilistic method, and no explicit codes are known.
A key new ingredient in our construction is a new notion of “evasiveness” of codes, which is concerned with whether a decoding algorithm rejects a word that is obtained when a channel induces few errors to a uniformly chosen (or pseudorandom) string. We use evasiveness (as well as several additional new ideas related to coding theory and pseudorandomness) to identify the “correct” message in the list obtained by previous list-decoding algorithms.
PDF
