We prove local and global inverse theorems for general $3$-wise correlations over pairwise-connected distributions. Let $\mu$ be a distribution over $\Sigma \times \Gamma \times \Phi$ such that the supports of $\mu_{xy}$, $\mu_{xz}$, and $\mu_{yz}$ are all connected, and let $f: \Sigma^n \to \mathbb{C}$, $g: \Gamma^n \to \mathbb{C}$, $h: \Phi^n \to ... more >>>

This paper studies the \emph{refuter} problems, a family of decision-tree $\mathrm{TFNP}$ problems capturing the metamathematical difficulty of proving proof complexity lower bounds. Suppose $\varphi$ is a hard tautology that does not admit any length-$s$ proof in some proof system $P$. In the corresponding refuter problem, we are given (query ... more >>>

We prove that for every odd $q\geq 3$, any $q$-query binary, possibly non-linear locally decodable code ($q$-LDC) $E:\{\pm 1\}^k \rightarrow \{\pm 1\}^n$ must satisfy $k \leq \tilde{O}(n^{1-2/q})$. For even $q$, this bound was established in a sequence of works (Katz and Trevisan (2000), Goldreich, Karloff, Schulman, and Trevisan (2002), and ... more >>>