Showing 2025Show all
2 papers · 1 filter
cs.DS2025
Homomorphism Testing with Resilience to Online Manipulations
Esty Kelman, Uri Meir, Debanuj Nayak +1
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,…
math.CO2025
Sparse graph counting and Kelley-Meka bounds for binary systems
Yuval Filmus, Hamed Hatami, Kaave Hosseini +1
In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. In thi…