2026-09-10T09:44:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27775 2026-09-09T12:19:38Z ddc:004 open_access

Homomorphism Testing with Resilience to Online Manipulations Kelman, Esty Meir, Uri Nayak, Debanuj Raskhodnikova, Sofya Property Testing Sublinear Algorithms Online Manipulation Resilience Group Theory A central challenge in property testing is verifying algebraic structure with minimal access to data. A landmark result addressing this challenge, the linearity test of Blum, Luby, and Rubinfeld (JCSS `93), spurred a rich body of work on testing algebraic properties such as linearity and its generalizations to low-degree polynomials and group homomorphisms. However, classical tests for these properties assume unrestricted, noise-free access to the input function - an assumption that breaks down in adversarial or dynamic settings. To address this, Kalemaj, Raskhodnikova, and Varma (Theory of Computing `23) introduced the online manipulation model, where an adversary erases or corrupts query responses over time, based on the tester’s past queries. We initiate the study of manipulation-resilient testing for group homomorphism in this online model. Our main result is an optimal tester that makes O(1/ε+log t) queries, where ε is the distance parameter and t is the number of function values the adversary can erase or corrupt per query. Our result recovers the celebrated O(1/ε) bound by Ben-Or, Coppersmith, Luby, and Rubinfeld (Random Struct. Algorithms `08) for homomorphism testing in the standard property testing model, albeit with a different tester. Our tester, Random Signs Test, lifts known manipulation-resilient linearity testers for 𝔽₂ⁿ → 𝔽₂ to general group domains and codomains by introducing more randomness: instead of verifying the homomorphism condition for a sum of random elements, it uses additions and subtractions of random elements, randomly selecting a sign for each element. We also obtain improved group-specific query bounds for key families of groups. Our results show that despite the challenges of online manipulation, group homomorphism - a fundamental algebraic property - is efficiently testable across a wide range of domains and codomains. Finally, we formalize a general framework for proving online resilience. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esty Kelman and Uri Meir and Debanuj Nayak and Sofya Raskhodnikova 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.58 urn:nbn:de:0030-drops-277753 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.58 eng https://creativecommons.org/licenses/by/4.0/legalcode