Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DOR MINZER:
All reports by Author Dor Minzer:

TR23-120 | 18th August 2023
Mitali Bafna, Dor Minzer

Characterizing Direct Product Testing via Coboundary Expansion

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 >>>




ISSN 1433-8092 | Imprint