Copertina

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Li, Rupert, Mossel, Elchanan
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Probability Computational Complexity Machine Learning Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
di: Gamarnik, David, et al.
Pubblicazione: (2023)

Some Theoretical Limitations of t-SNE
di: Li, Rupert, et al.
Pubblicazione: (2026)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
di: Kush, Deepanshu
Pubblicazione: (2026)

Monotonicity, Topology, and Convexity of Recurrence in Random Walks
di: Li, Rupert, et al.
Pubblicazione: (2024)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2024)

Multiplayer Games of War
di: Adjei, Axel, et al.
Pubblicazione: (2024)

On hardness of computing analytic Brouwer degree
di: Chakraborty, Somnath
Pubblicazione: (2023)

Permanents of random matrices over finite fields
di: Hunter, Zach, et al.
Pubblicazione: (2026)

Optimal Union Probability Interval Is NP-Hard
di: Kaski, Petteri, et al.
Pubblicazione: (2026)

Separating complexity classes of LCL problems on grids
di: Berlow, Katalin, et al.
Pubblicazione: (2025)

Denoising distances beyond the volumetric barrier
di: Huang, Han, et al.
Pubblicazione: (2026)

Reconstructing the Geometry of Random Geometric Graphs
di: Huang, Han, et al.
Pubblicazione: (2024)

Low-degree learning and the metric entropy of polynomials
di: Eskenazis, Alexandros, et al.
Pubblicazione: (2022)

Some easy optimization problems have the overlap-gap property
di: Li, Shuangping, et al.
Pubblicazione: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
di: Basu, Arpon, et al.
Pubblicazione: (2024)

Universality for roots of derivatives of entire functions via finite free probability
di: Campbell, Andrew, et al.
Pubblicazione: (2024)

Polynomial-time sampling despite disorder chaos
di: Ma, Eric, et al.
Pubblicazione: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs
di: Mossel, Elchanan, et al.
Pubblicazione: (2024)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
di: Bhore, Sujoy, et al.
Pubblicazione: (2026)

The Optimal Approximation Factor in Density Estimation
di: Bousquet, Olivier, et al.
Pubblicazione: (2019)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
di: Amiri, Alireza, et al.
Pubblicazione: (2025)

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
di: Williamson, Christopher
Pubblicazione: (2026)

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
di: Nagda, Ansh, et al.
Pubblicazione: (2025)

On the Expressibility of the Reconstructional Color Refinement
di: Arvind, V., et al.
Pubblicazione: (2024)

Asymptotics for the harmonic descent chain and applications to critical beta-splitting trees
di: Brandenberger, Anna, et al.
Pubblicazione: (2025)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
di: Majumdar, Angshul
Pubblicazione: (2026)

Sensitivity and Hamming graphs
di: Asensio, Sara, et al.
Pubblicazione: (2025)

Infinite circle patterns in the Weil-Petersson class
di: Lam, Wai Yeung
Pubblicazione: (2026)

Decay of correlations and zeros for the hard-core model
di: Peters, Han, et al.
Pubblicazione: (2026)

Sharp Online Hardness for Large Balanced Independent Sets
di: Dhawan, Abhishek, et al.
Pubblicazione: (2025)

The stochastic block model has the overlap graph property for modularity
di: Bhamidi, Shankar, et al.
Pubblicazione: (2026)

Inference of rankings planted in random tournaments
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Statistical inference of a ranked community in a directed graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
di: Gamarnik, David, et al.
Pubblicazione: (2026)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2026)

A computational phase transition for learning-to-sample from Ising models
di: Risteski, Andrej, et al.
Pubblicazione: (2026)

Sparsifying Suprema of Gaussian Processes
di: De, Anindya, et al.
Pubblicazione: (2024)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
di: Tulsiani, Madhur, et al.
Pubblicazione: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
di: Bhangale, Amey, et al.
Pubblicazione: (2024)