Cover Image

Optimal Testing of Reed-Muller Codes with an Online Adversary

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kelman, Esty, Meir, Uri, Zheng, Kai Zhe
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

Homomorphism Testing with Resilience to Online Manipulations
by: Kelman, Esty, et al.
Published: (2025)

Online versus Offline Adversaries in Property Testing
by: Kelman, Esty, et al.
Published: (2024)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
by: Andoni, Alexandr, et al.
Published: (2026)

Smoothed Analysis of Dynamic Graph Algorithms
by: Meir, Uri, et al.
Published: (2025)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
by: Brakensiek, Joshua, et al.
Published: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

On the Adversarial Robustness of Online Importance Sampling
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Faster All-Pairs Optimal Electric Car Routing
by: Dorfman, Dani, et al.
Published: (2025)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

Chasing Small Sets Optimally Against Adaptive Adversaries
by: Coester, Christian, et al.
Published: (2026)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
by: Gribelyuk, Elena, et al.
Published: (2025)

List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics
by: Peikert, Chris, et al.
Published: (2025)

Optimal Learning-Augmented Algorithm for Online Bidding
by: Lee, Changyeol, et al.
Published: (2026)

Nearly Optimal Bounds for Stochastic Online Sorting
by: Hu, Yang
Published: (2025)

Near-Optimal Bayesian Online Assortment of Reusable Resources
by: Feng, Yiding, et al.
Published: (2025)

Bounding the Optimal Performance of Online Randomized Primal-Dual Methods
by: Xu, Pan
Published: (2025)

Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
by: Goyal, Vineet, et al.
Published: (2020)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Search Trees on Trees via LP
by: Sadeh, Yaniv, et al.
Published: (2025)

Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
by: De Marco, Gianluca, et al.
Published: (2025)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
by: Udwani, Rajan
Published: (2024)

Grafite: Taming Adversarial Queries with Optimal Range Filters
by: Costa, Marco, et al.
Published: (2023)

Optimal Bounds for Adversarial Constrained Online Convex Optimization
by: Ferreira, Ricardo N., et al.
Published: (2025)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
by: Brakensiek, Joshua, et al.
Published: (2026)

Adaptively Robust Resettable Streaming
by: Cohen, Edith, et al.
Published: (2026)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
by: Black, Hadley
Published: (2023)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

On Differentially Private Linear Algebra
by: Kaplan, Haim, et al.
Published: (2024)

Time-Optimal and Energy-Efficient Deterministic Consensus
by: Meir, Shachar, et al.
Published: (2025)

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
by: Nikolov, Aleksandar, et al.
Published: (2026)

Approximation Schemes for Sequential Hiring Problems
by: Segev, Danny, et al.
Published: (2026)

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
by: Guo, Zeyu, et al.
Published: (2023)

Adversarial Robustness on Insertion-Deletion Streams
by: Gribelyuk, Elena, et al.
Published: (2026)

Sorting and Selection in Rounds with Adversarial Comparisons
by: Trevisan, Chris
Published: (2023)