Buchumschlag

On Optimal Testing of Linearity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Arora, Vipul, Kelman, Esty, Meir, Uri
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimal Testing of Reed-Muller Codes with an Online Adversary
von: Kelman, Esty, et al.
Veröffentlicht: (2026)

Homomorphism Testing with Resilience to Online Manipulations
von: Kelman, Esty, et al.
Veröffentlicht: (2025)

Online versus Offline Adversaries in Property Testing
von: Kelman, Esty, et al.
Veröffentlicht: (2024)

Outlier Robust Multivariate Polynomial Regression
von: Arora, Vipul, et al.
Veröffentlicht: (2024)

Linear Hashing Is Optimal
von: Jaber, Michael, et al.
Veröffentlicht: (2025)

On the Mysteries of MAX NAE-SAT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2020)

MAX BISECTION might be harder to approximate than MAX CUT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Improved Algorithm for Permutation Testing
von: Zhang, Xiaojin
Veröffentlicht: (2020)

Testing Properties of Edge Distributions
von: Fei, Yumou
Veröffentlicht: (2026)

Computational Complexity in Property Testing
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Near-Optimal Averaging Samplers and Matrix Samplers
von: Xun, Zhiyang, et al.
Veröffentlicht: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
von: Minzer, Dor, et al.
Veröffentlicht: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
von: Sajith, Thejas Radhika
Veröffentlicht: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Testing noisy low-degree polynomials for sparsity
von: Bao, Yiqiao, et al.
Veröffentlicht: (2025)

Encoding Co-Lex Orders of Finite-State Automata in Linear Space
von: Becker, Ruben, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
von: Li, Qian, et al.
Veröffentlicht: (2025)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
von: Andoni, Alexandr, et al.
Veröffentlicht: (2026)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
von: Wallisch, Christian, et al.
Veröffentlicht: (2025)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
von: Jiang, Cheng, et al.
Veröffentlicht: (2026)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
von: Mao, Songtao
Veröffentlicht: (2026)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
von: Arvind, V., et al.
Veröffentlicht: (2023)

Testing Sumsets is Hard
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Characterizing and Testing Principal Minor Equivalence of Matrices
von: Chatterjee, Abhranil, et al.
Veröffentlicht: (2024)

A General Framework for Low Soundness Homomorphism Testing
von: Mittal, Tushant, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
von: Lee, Euiwoong, et al.
Veröffentlicht: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Lower Bounds for Linear Operators
von: Ko, Young Kun
Veröffentlicht: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Optimality of Frequency Moment Estimation
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Fractional Linear Matroid Matching is in quasi-NC
von: Gurjar, Rohit, et al.
Veröffentlicht: (2024)