Characterizing Direct Product Testing via Coboundary Expansion
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155664 |
| _version_ | 1824458323368345600 |
|---|---|
| author | Bafna, Mitali Minzer, Dor |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Bafna, Mitali Minzer, Dor |
| author_sort | Bafna, Mitali |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T14:47:37Z |
| format | Article |
| id | mit-1721.1/155664 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:24:04Z |
| publishDate | 2024 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1556642025-01-08T04:29:28Z Characterizing Direct Product Testing via Coboundary Expansion Bafna, Mitali Minzer, Dor Massachusetts Institute of Technology. Department of Mathematics STOC ’24, June 24–28, 2024, Vancouver, BC, Canada 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≪ d) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution µ over pairs of k-faces (A,A′), and given query access to F: X(k)→{0,1}k it samples (A,A′)∼ µ and checks that F[A]|A∩ A′ = F[A′]|A∩ A′. The tester should have (1) the ”completeness property”, meaning that any assignment F which is a direct product assignment passes the test with probability 1, and (2) the ”soundness property”, meaning that if F passes the test with probability s, then F must be correlated with a direct product function. Dinur and Kaufman showed that a sufficiently good spectral expanding complex X admits a direct product tester in the ”high soundness” regime where s is close to 1. They asked whether there are high dimensional expanders that support direct product tests in the ”low soundness”, when s is close to 0. We give a characterization of high-dimensional expanders that support a direct product tester in the low soundness regime. We show that spectral expansion is insufficient, and the complex must additionally satisfy a variant of coboundary expansion, which we refer to as ”Unique-Games coboundary expanders”. Conversely, we show that this property is also sufficient to get direct product testers. This property can be seen as a high-dimensional generalization of the standard notion of coboundary expansion over non-Abelian groups for 2-dimensional complexes. It asserts that any locally consistent Unique-Games instance obtained using the low-level faces of the complex, must admit a good global solution. 2024-07-11T21:38:05Z 2024-07-11T21:38:05Z 2024-06-10 2024-07-01T07:50:43Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155664 Bafna, Mitali and Minzer, Dor. 2024. "Characterizing Direct Product Testing via Coboundary Expansion." PUBLISHER_CC en 10.1145/3618260.3649714 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Bafna, Mitali Minzer, Dor Characterizing Direct Product Testing via Coboundary Expansion |
| title | Characterizing Direct Product Testing via Coboundary Expansion |
| title_full | Characterizing Direct Product Testing via Coboundary Expansion |
| title_fullStr | Characterizing Direct Product Testing via Coboundary Expansion |
| title_full_unstemmed | Characterizing Direct Product Testing via Coboundary Expansion |
| title_short | Characterizing Direct Product Testing via Coboundary Expansion |
| title_sort | characterizing direct product testing via coboundary expansion |
| url | https://hdl.handle.net/1721.1/155664 |
| work_keys_str_mv | AT bafnamitali characterizingdirectproducttestingviacoboundaryexpansion AT minzerdor characterizingdirectproducttestingviacoboundaryexpansion |