arXiv:1802.04014

From expanders to hitting distributions and simulation theorems

Alexander Kozachinskiy

Published Feb 12, 2018• 0 citations

Abstract

Recently, Chattopadhyay et al. (\cite{chattopadhyay2017simulation}) proved that any gadget having so called \emph{hitting distributions} admits deterministic "query-to-communication" simulation theorem. They applied this result to Inner Product, Gap Hamming Distance and Indexing Function. They also demonstrated that previous works used hitting distributions implicitly (\cite{goos2015deterministic} for Indexing Function and \cite{wu2017raz} for Inner Product). In this paper we show that any expander in which any two distinct vertices have at most one common neighbor can be transformed into a gadget possessing good hitting distributions. We demonstrate that this result is applicable to affine plane expanders and to Lubotzky-Phillips-Sarnak construction of Ramanujan graphs . In particular, from affine plane expanders we extract a gadget achieving the best known trade-off between the arity of outer function and the size of gadget. More specifically, when this gadget has $k$ bits on input, it admits a simulation theorem for all outer function of arity roughly $2^{k/2}$ or less (the same was also known for $k$-bit Inner Product, (\cite{chattopadhyay2017simulation})). In addition we show that, unlike Inner Product, underlying hitting distributions in our new gadget are "polynomial-time listable" in the sense that their supports can be written down in time $2^{O(k)}$, i.e, in time polynomial in size of gadget's matrix.

DOI: 10.48550/arxiv.1802.04014

Related papers

Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma.

Alexander Kozachinskiy

Feb 12, 20181 citation

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2 more

arXiv:1904.13056SIAM Journal on ComputingJan 1, 202112 citations

Distributional Variants of the Aaronson-Ambainis Conjecture

Uma Girish, Kunal Mittal, Barak Nehoran +1 more

quant-pharXiv:2609.35327Sep 29, 20260 citations

Query-To-Communication Lifting for BPP Using Inner Product

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2 more

Leibniz international proceedings in informaticsJan 1, 20193 citations

Improved Decoding of Tanner Codes

Zhaienhe Zhou, Zeyu Guo

arXiv:2501.12293IEEE International Symposium on Information Theory (ISIT)Jun 22, 20252 citations

Rectangles Are Nonnegative Juntas

Mika Göös, Shachar Lovett, Raghu Meka +2 more

SIAM Journal on ComputingJan 1, 201650 citations

arXiv:1802.04014

From expanders to hitting distributions and simulation theorems

Alexander Kozachinskiy

Published Feb 12, 2018• 0 citations

arXiv HTML PDF

Abstract

k

bits on input, it admits a simulation theorem for all outer function of arity roughly

2^{k/2}

or less (the same was also known for

k

-bit Inner Product, (\cite{chattopadhyay2017simulation})). In addition we show that, unlike Inner Product, underlying hitting distributions in our new gadget are "polynomial-time listable" in the sense that their supports can be written down in time

2^{O(k)}

, i.e, in time polynomial in size of gadget's matrix.

DOI: 10.48550/arxiv.1802.04014

Related papers

Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma.

Alexander Kozachinskiy

Assume that we have an outer function $f:\{0, 1\}^n \to \{0, 1\}$ and a gadget function $g:A\times B \to\{0, 1\}$ and we want to lower bound deterministic communication complexity of a composed function $f\circ g^n$ , denoted here by $D^{cc}(f\circ g^n)$ , in terms of deterministic query complexity of $f$ , denoted here by $D^{dt}(f)$ . The study of such questions, now usually called \emph{Simulation Theorems}, was initiated in the work of Raz and McKenzie (\cite{raz1997separation}). Recently, Chattopadhyaay et al. (\cite{chattopadhyay2017simulation}) introduced a very convenient tool to study such questions, they called this tool \emph{hitting distributions}. Using this tool, they proved that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$ , where $g$ is either Inner Product or Gap Hamming Distance gadget on $k$ bits, and $f$ is any function depending on at most $2^{ck}$ variables for some absolute constant $c$ . In this work we use hitting distributions to show Simulation Theorem for a new gadget. Our gadget is the following one: Alice holds $a\in \mathbb{F}_{p^2}$ , Bob holds $b\in \mathbb{F}_{p^2}$ and they want to know whether $a - b$ is a square in $\mathbb{F}_{p^2}$ . We show that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$ , where $g$ is our gadget and $f$ is any function depending on at most $p^c$ variables for some constant $c$ (note that this bound is exponential in the size of gadget, which is $O(\log p)$ ). We also investigate hitting distributions for disjointness predicate on $k$ -element subsets of $\{1, 2, \ldots, n\}$ . Finally, we study Thickness Lemma, a combinatorial statement from the proof of Simulation Theorems of G\{o}\{o}s et al and Chattopadhyaay et al., and show that this Lemma can not be improved.Assume that we have an outer function $f:\{0, 1\}^n \to \{0, 1\}$ and a gadget function $g:A\times B \to\{0, 1\}$ and we want to lower bound deterministic communication complexity of a composed function $f\circ g^n$, denoted here by $D^{cc}(f\circ g^n)$, in terms of deterministic query complexity of $f$, denoted here by $D^{dt}(f)$. The study of such questions, now usually called \emph{Simulation Theorems}, was initiated in the work of Raz and McKenzie (\cite{raz1997separation}). Recently, Chattopadhyaay et al. (\cite{chattopadhyay2017simulation}) introduced a very convenient tool to study such questions, they called this tool \emph{hitting distributions}. Using this tool, they proved that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$, where $g$ is either Inner Product or Gap Hamming Distance gadget on $k$ bits, and $f$ is any function depending on at most $2^{ck}$ variables for some absolute constant $c$. In this work we use hitting distributions to show Simulation Theorem for a new gadget. Our gadget is the following one: Alice holds $a\in \mathbb{F}_{p^2}$, Bob holds $b\in \mathbb{F}_{p^2}$ and they want to know whether $a - b$ is a square in $\mathbb{F}_{p^2}$. We show that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$, where $g$ is our gadget and $f$ is any function depending on at most $p^c$ variables for some constant $c$ (note that this bound is exponential in the size of gadget, which is $O(\log p)$). We also investigate hitting distributions for disjointness predicate on $k$-element subsets of $\{1, 2, \ldots, n\}$. Finally, we study Thickness Lemma, a combinatorial statement from the proof of Simulation Theorems of G\{o}\{o}s et al and Chattopadhyaay et al., and show that this Lemma can not be improved.

Feb 12, 20181 citation

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2 more

Lifting theorems are theorems that relate the query complexity of a function $f:\{0,1\}^{n}\to \{0,1\}$ to the communication complexity of the composed function $f\circ g^{n}$ for some “gadget” $g:\{ 0,1\}^{b}\times \{0,1\}^{b}\to \{0,1\}$ . Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget $g$ . We prove a new lifting theorem that works for all gadgets $g$ that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold. Our result has two main motivations: first, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.Lifting theorems are theorems that relate the query complexity of a function $f:\{0,1\}^{n}\to \{0,1\}$ to the communication complexity of the composed function $f\circ g^{n}$ for some “gadget” $g:\{ 0,1\}^{b}\times \{0,1\}^{b}\to \{0,1\}$. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget $g$. We prove a new lifting theorem that works for all gadgets $g$ that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold. Our result has two main motivations: first, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.

arXiv:1904.13056SIAM Journal on ComputingJan 1, 202112 citations

Distributional Variants of the Aaronson-Ambainis Conjecture

Uma Girish, Kunal Mittal, Barak Nehoran +1 more

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$ , where the input bits are independent Bernoulli variables with fixed bias $p$ . We show that for every fixed $p \in (0, 1)$ , quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

quant-pharXiv:2609.35327Sep 29, 20260 citations

Query-To-Communication Lifting for BPP Using Inner Product

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2 more

We prove a new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. [Arkadev Chattopadhyay et al., 2017] and Wu et al. [Xiaodi Wu et al., 2017]. The only query-to-communication lifting result for randomized protocols, due to Göös, Pitassi and Watson [Mika Göös et al., 2017], used the much larger indexing gadget. Our proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as thickness. In contrast, Göös, Pitassi and Watson [Mika Göös et al., 2017] used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way.We prove a new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. [Arkadev Chattopadhyay et al., 2017] and Wu et al. [Xiaodi Wu et al., 2017]. The only query-to-communication lifting result for randomized protocols, due to Göös, Pitassi and Watson [Mika Göös et al., 2017], used the much larger indexing gadget. Our proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as thickness. In contrast, Göös, Pitassi and Watson [Mika Göös et al., 2017] used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way.

Leibniz international proceedings in informaticsJan 1, 20193 citations

Improved Decoding of Tanner Codes

Zhaienhe Zhou, Zeyu Guo

In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that $\delta d_{0}>2$ , corrects up to $\alpha n$ errors for a Tanner code $T\left(G, C_{0}\right)$ , where $G$ is a ( $c, d, \alpha, \delta$ ) bipartite expander with $n$ left vertices, and $C_{0} \subseteq \mathbb{F}_{2}^{d}$ is a linear inner code with minimum distance $d_{0}$ . This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required $\delta d_{0}>3$ . We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of $\alpha n$ , compared with the previous radius of $\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} n$ . Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code $T\left(G, C_{0}\right)$ is approximately $f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n$ , where $f_{\delta}(\cdot)$ is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from $\alpha n$ to approximately $f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n$ .In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that$\delta d_{0}>2$, corrects up to$\alpha n$errors for a Tanner code$T\left(G, C_{0}\right)$, where$G$is a ($c, d, \alpha, \delta$) bipartite expander with$n$left vertices, and$C_{0} \subseteq \mathbb{F}_{2}^{d}$is a linear inner code with minimum distance$d_{0}$. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required$\delta d_{0}>3$. We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of$\alpha n$, compared with the previous radius of$\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} n$. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code$T\left(G, C_{0}\right)$is approximately$f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n$, where$f_{\delta}(\cdot)$is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from$\alpha n$to approximately$f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n$.

arXiv:2501.12293IEEE International Symposium on Information Theory (ISIT)Jun 22, 20252 citations

Rectangles Are Nonnegative Juntas

Mika Göös, Shachar Lovett, Raghu Meka +2 more

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ , where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently “hard” two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ g^n$ can be simulated by a nonnegative combination of juntas. This is a new formalization for the intuition that each low-communication randomized protocol can only “query” a few inputs of $f$ as encoded by the gadget $g$ . Consequently, we characterize the communication complexity of $f\circ g^n$ in all known one-sided (i.e., not closed under complement) zero-communication models by a corresponding query complexity measure of $f$ . These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work. We show that $\mathsf{SBP}^{\sf cc}$ (a class characterized by corruption) is not closed under intersection. An immediate corollary is that $\mathsf{MA}^{\sf cc} \neq \mathsf{SBP}^{\sf cc}$ . These results answer questions of Klauck [Proceedings of the 18th Conference on Computational Complexity (CCC), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 118--134] and Böhler, Glasser, and Meister [J. Comput. System Sci., 72 (2006), pp. 1043--1076]. We also show that the approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. [Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Springer, Berlin, 2014, pp. 701--712] for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the clique versus independent set problem.We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$, where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently “hard” two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ g^n$ can be simulated by a nonnegative combination of juntas. This is a new formalization for the intuition that each low-communication randomized protocol can only “query” a few inputs of $f$ as encoded by the gadget $g$. Consequently, we characterize the communication complexity of $f\circ g^n$ in all known one-sided (i.e., not closed under complement) zero-communication models by a corresponding query complexity measure of $f$. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work. We show that $\mathsf{SBP}^{\sf cc}$ (a class characterized by corruption) is not closed under intersection. An immediate corollary is that $\mathsf{MA}^{\sf cc} \neq \mathsf{SBP}^{\sf cc}$. These results answer questions of Klauck [Proceedings of the 18th Conference on Computational Complexity (CCC), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 118--134] and Böhler, Glasser, and Meister [J. Comput. System Sci., 72 (2006), pp. 1043--1076]. We also show that the approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. [Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Springer, Berlin, 2014, pp. 701--712] for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the clique versus independent set problem.

SIAM Journal on ComputingJan 1, 201650 citations

k

bits on input, it admits a simulation theorem for all outer function of arity roughly

2^{k/2}

or less (the same was also known for

k

2^{O(k)}

, i.e, in time polynomial in size of gadget's matrix.

Assume that we have an outer function

f:\{0, 1\}^n \to \{0, 1\}

and a gadget function

g:A\times B \to\{0, 1\}

and we want to lower bound deterministic communication complexity of a composed function

f\circ g^n

, denoted here by

D^{cc}(f\circ g^n)

, in terms of deterministic query complexity of

f

, denoted here by

D^{dt}(f)

. The study of such questions, now usually called \emph{Simulation Theorems}, was initiated in the work of Raz and McKenzie (\cite{raz1997separation}). Recently, Chattopadhyaay et al. (\cite{chattopadhyay2017simulation}) introduced a very convenient tool to study such questions, they called this tool \emph{hitting distributions}. Using this tool, they proved that

D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)

, where

g

is either Inner Product or Gap Hamming Distance gadget on

k

bits, and

f

is any function depending on at most

2^{ck}

variables for some absolute constant

c

. In this work we use hitting distributions to show Simulation Theorem for a new gadget. Our gadget is the following one: Alice holds

a\in \mathbb{F}_{p^2}

, Bob holds

b\in \mathbb{F}_{p^2}

and they want to know whether

a - b

is a square in

\mathbb{F}_{p^2}

. We show that

D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)

, where

g

is our gadget and

f

is any function depending on at most

p^c

variables for some constant

c

(note that this bound is exponential in the size of gadget, which is

O(\log p)

). We also investigate hitting distributions for disjointness predicate on

k

-element subsets of

\{1, 2, \ldots, n\}

. Finally, we study Thickness Lemma, a combinatorial statement from the proof of Simulation Theorems of G\{o}\{o}s et al and Chattopadhyaay et al., and show that this Lemma can not be improved.

Lifting theorems are theorems that relate the query complexity of a function

f:\{0,1\}^{n}\to \{0,1\}

to the communication complexity of the composed function

f\circ g^{n}

for some “gadget”

g:\{ 0,1\}^{b}\times \{0,1\}^{b}\to \{0,1\}

. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget

g

. We prove a new lifting theorem that works for all gadgets

g

that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold. Our result has two main motivations: first, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.

μ_p

, where the input bits are independent Bernoulli variables with fixed bias

p

. We show that for every fixed

p \in (0, 1)

, quantum query algorithms under the

μ_p

distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution

ν_p

that is uniform over the slice of strings with Hamming weight

\lfloor pn \rfloor

and prove a similar equivalence for the

ν_p

distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that

\delta d_{0}>2

, corrects up to

\alpha n

errors for a Tanner code

T\left(G, C_{0}\right)

, where

G

is a (

c, d, \alpha, \delta

) bipartite expander with

n

left vertices, and

C_{0} \subseteq \mathbb{F}_{2}^{d}

is a linear inner code with minimum distance

d_{0}

. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required

\delta d_{0}>3

. We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of

\alpha n

, compared with the previous radius of

\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} n

. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code

T\left(G, C_{0}\right)

is approximately

f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n

, where

f_{\delta}(\cdot)

is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from

\alpha n

to approximately

f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n

We develop a new method to prove communication lower bounds for composed functions of the form

f\circ g^n

, where

f

is any boolean function on

n

inputs and

g

is a sufficiently “hard” two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of

f \circ g^n

can be simulated by a nonnegative combination of juntas. This is a new formalization for the intuition that each low-communication randomized protocol can only “query” a few inputs of

f

as encoded by the gadget

g

. Consequently, we characterize the communication complexity of

f\circ g^n

in all known one-sided (i.e., not closed under complement) zero-communication models by a corresponding query complexity measure of

f

. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work. We show that

\mathsf{SBP}^{\sf cc}

(a class characterized by corruption) is not closed under intersection. An immediate corollary is that

\mathsf{MA}^{\sf cc} \neq \mathsf{SBP}^{\sf cc}

. These results answer questions of Klauck [Proceedings of the 18th Conference on Computational Complexity (CCC), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 118--134] and Böhler, Glasser, and Meister [J. Comput. System Sci., 72 (2006), pp. 1043--1076]. We also show that the approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. [Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Springer, Berlin, 2014, pp. 701--712] for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the clique versus independent set problem.