All reports by Author Dor Minzer:

__
TR24-020
| 2nd February 2024
__

Mitali Bafna, Noam Lifshitz, Dor Minzer#### Constant Degree Direct Product Testers with Small Soundness

Revisions: 1

__
TR23-120
| 18th August 2023
__

Mitali Bafna, Dor Minzer#### Characterizing Direct Product Testing via Coboundary Expansion

Mitali Bafna, Noam Lifshitz, Dor Minzer

Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich ... more >>>

Mitali Bafna, Dor Minzer

A $d$-dimensional simplicial complex $X$ is said to support a direct product tester if any locally consistent function defined on its $k$-faces (where $k\ll d$) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution $\mu$ over pairs of $k$-faces $(A,A')$, and given ... more >>>