We generalize the ``indirect learning'' technique of Furst et al. (1991) to reduce from learning a concept class over a samplable distribution $\mu$ to learning the same concept class over the uniform distribution. The reduction succeeds when the sampler for $\mu$ is both contained in the target concept class and efficiently invertible in the sense of Impagliazzo and Luby (1989). We give two applications. We show that $\mathsf{AC}^0[q]$ is learnable over any succinctly-described product distribution. $\mathsf{AC}^0[q]$ is the class of constant-depth Boolean circuits of polynomial size with AND, OR, NOT, and counting modulo $q$ gates of unbounded fanins. Our algorithm runs in randomized quasi-polynomial time and uses membership queries. If there is a strongly useful natural property in the sense of Razborov and Rudich (1997) — an efficient algorithm that can distinguish between random strings and strings of non-trivial circuit complexity — then general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time, given membership queries to the target function.

A k-LIN instance is a system of m equations over n variables of the form si1 + · · · + sik = 0 or 1 modulo 2 (each involving k variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are different. In a noisy planted instance, the right-hand side is obtained by evaluating the system on a random planted solution and adding independent noise with some constant bias to each equation; whereas in a random instance, the right-hand side is uniformly random. Alekhnovich (FOCS 2003) conjectured that the two are hard to distinguish when k = 3 and m = O(n). We give a sample-efficient reduction from solving noisy planted k-LIN instances (a sparse-equation version of the Learning Parity with Noise problem) to distinguishing them from random instances. Suppose that m-equation, n-variable instances of the two types are efficiently distinguishable with advantage ε. Then, we show that O(m · (m/ε)2/k)-equation, n-variable noisy planted k-LIN instances are efficiently solvable with probability exp –Õ((m/ε)6/k). Our solver has worse success probability but better sample complexity than Applebaum's (SICOMP 2013). We extend our techniques to show that this can generalize to (possibly non-linear) k-CSPs. The solver is based on a new approximate local list-decoding algorithm for the k-XOR code at large distances. The k-XOR encoding of a function F: ∑ → {–1, 1} is its k-th tensor power Fk(x1, …, xk) = F(x1) · · · F(xk). Given oracle access to a function G that µ-correlates with Fk, our algorithm, say for constant k, outputs the description of a message that Ω(µ1/k)-correlates with F with probability exp(–Õ(µ−4/k)). Previous decoders, for such k, have a worse dependence on µ (Levin, Combinatorica 1987) or do not apply to subconstant µ1/k. We also prove a new XOR lemma for this parameter regime. The decoder and its analysis rely on a new structure-versus-randomness dichotomy for general Boolean-valued functions over product sets, which may be of independent interest.

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires n^{epsilon k} time, for some constant epsilon>1/2, to count (note that these conjectures are significantly weaker than the usual ones made on these problems) on randomized machines for all but finitely many input lengths, then we have the following derandomizations: - BPP can be decided in polynomial time using only n^alpha random bits on average over any efficient input distribution, for any constant alpha>0 - BPP can be decided in polynomial time with no randomness on average over the uniform distribution This answers an open question of Ball et al. (STOC '17) in the positive of whether derandomization can be achieved from conjectures from fine-grained complexity theory. More strongly, these derandomizations improve over all previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible. Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions about specific problems like k-CLIQUE imply quantitative and qualitative relationships between randomized and deterministic time. This can be either viewed as a barrier to proving some of the main conjectures of fine-grained complexity theory lest we achieve a major breakthrough in unconditional derandomization or, optimistically, as route to attain such derandomizations by working on very concrete and weak conjectures about specific problems.

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure.