Buchumschlag

Detecting Low-Degree Truncation

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	De, Anindya, Li, Huan, Nadimpalli, Shivam, Servedio, Rocco A.
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

Testing Convex Truncation
von: De, Anindya, et al.
Veröffentlicht: (2023)

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

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

Sublinear-query relative-error testing of halfspaces
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Halfspaces are hard to test with relative error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Sparsifying Suprema of Gaussian Processes
von: De, Anindya, et al.
Veröffentlicht: (2024)

Model-agnostic super-resolution in high dimensions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

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

Relative-error monotonicity testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

No Price Tags? No Problem: Query Strategies for Unpriced Information
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2025)

Learning Functions of Halfspaces
von: Alman, Josh, et al.
Veröffentlicht: (2026)

DNF formulas are efficiently testable with relative error
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Faster exact learning of k-term DNFs with membership and equivalence queries
von: Alman, Josh, et al.
Veröffentlicht: (2025)

DNF Learning via Locally Mixing Random Walks
von: Alman, Josh, et al.
Veröffentlicht: (2025)

Relative-error testing of conjunctions and decision lists
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Is nasty noise actually harder than malicious noise?
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Testing Juntas and Junta Subclasses with Relative Error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

The Quasi-Polynomial Low-Degree Conjecture is False
von: Buhai, Rares-Darius, et al.
Veröffentlicht: (2025)

Relative-error unateness testing
von: Chen, Xi, et al.
Veröffentlicht: (2025)

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

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

Structural Parameterizations for Two Bounded Degree Problems Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

Low-Degree Method Fails to Predict Robust Subspace Recovery
von: Jia, He, et al.
Veröffentlicht: (2026)

Trace reconstruction from local statistical queries
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
von: Yu, Xifan, et al.
Veröffentlicht: (2024)

Strong Low Degree Hardness for the Number Partitioning Problem
von: Mallarapu, Rushil, et al.
Veröffentlicht: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
von: Sohn, Youngtak, et al.
Veröffentlicht: (2025)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
von: Yoshida, Yuichi, et al.
Veröffentlicht: (2025)

Fine-Grained Classification Of Detecting Dominating Patterns
von: Dransfeld, Jonathan, et al.
Veröffentlicht: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Quantum Property Testing for Bounded-Degree Directed Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
von: Vroon, Mats, et al.
Veröffentlicht: (2025)

Second Price Matching with Complete Allocation and Degree Constraints
von: Pinchasi, Rom, et al.
Veröffentlicht: (2025)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2024)

Constructing self-referential instances for the clique problem
von: Li, Jiaqi, et al.
Veröffentlicht: (2026)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
von: Shao, Shuai, et al.
Veröffentlicht: (2023)

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
von: Chen, Sitan, et al.
Veröffentlicht: (2025)

Asymptotic Rank Speedup Theorems, Revisited
von: Alman, Josh, et al.
Veröffentlicht: (2026)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
von: Alman, Josh, et al.
Veröffentlicht: (2025)