2026-07-21T14:10:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11265 2024-03-06T10:47:50Z ddc:004 open_access

Testing Odd Direct Sums Using High Dimensional Expanders Gotlib, Roy Kaufman, Tali High Dimensional Expanders Property Testing Direct Sum In this work, using methods from high dimensional expansion, we show that the property of k-direct-sum is testable for odd values of k . Previous work of [Kaufman and Lubotzky, 2014] could inherently deal only with the case that k is even, using a reduction to linearity testing. Interestingly, our work is the first to combine the topological notion of high dimensional expansion (called co-systolic expansion) with the combinatorial/spectral notion of high dimensional expansion (called colorful expansion) to obtain the result. The classical k-direct-sum problem applies to the complete complex; Namely it considers a function defined over all k-subsets of some n sized universe. Our result here applies to any collection of k-subsets of an n-universe, assuming this collection of subsets forms a high dimensional expander. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roy Gotlib and Tali Kaufman 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.50 urn:nbn:de:0030-drops-112651 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.50 eng https://creativecommons.org/licenses/by/3.0/legalcode