Copertina

Hardness of Learning Boolean Functions from Label Proportions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Guruswami, Venkatesan, Saket, Rishi
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Data Structures and Algorithms Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

Scheduling Problems with Constrained Rejections
di: Davies, Sami, et al.
Pubblicazione: (2025)

Learning-Augmented Algorithms for Boolean Satisfiability
di: Attias, Idan, et al.
Pubblicazione: (2025)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

Weak to Strong Learning from Aggregate Labels
di: Makhija, Yukti, et al.
Pubblicazione: (2024)

Hardness of Maximum Likelihood Learning of DPPs
di: Grigorescu, Elena, et al.
Pubblicazione: (2022)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2025)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

On the Hardness of Approximation of the Fair k-Center Problem
di: Thejaswi, Suhas
Pubblicazione: (2026)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
di: Gopalan, Parikshit, et al.
Pubblicazione: (2024)

On the Power of Interactive Proofs for Learning
di: Gur, Tom, et al.
Pubblicazione: (2024)

Superconstant Inapproximability of Decision Tree Learning
di: Koch, Caleb, et al.
Pubblicazione: (2024)

Exact and Approximate Algorithms for Polytree Learning
di: Harviainen, Juha, et al.
Pubblicazione: (2026)

A Distributional-Lifting Theorem for PAC Learning
di: Blanc, Guy, et al.
Pubblicazione: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
di: Larsen, Kasper Green, et al.
Pubblicazione: (2026)

Active Learning for Decision Trees with Provable Guarantees
di: Moakhar, Arshia Soltani, et al.
Pubblicazione: (2026)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
di: Sato, Atsuki, et al.
Pubblicazione: (2025)

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

Computational-Statistical Tradeoffs from NP-hardness
di: Blanc, Guy, et al.
Pubblicazione: (2025)

Training Neural Networks is NP-Hard in Fixed Dimension
di: Froese, Vincent, et al.
Pubblicazione: (2023)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
di: Sharma, Amatya, et al.
Pubblicazione: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
di: Jansen, Bart M. P., et al.
Pubblicazione: (2026)

Fast decision tree learning solves hard coding-theoretic problems
di: Koch, Caleb, et al.
Pubblicazione: (2024)

Adaptive and oblivious statistical adversaries are equivalent
di: Blanc, Guy, et al.
Pubblicazione: (2024)

Private graphon estimation via sum-of-squares
di: Chen, Hongjie, et al.
Pubblicazione: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
di: Mardia, Jay, et al.
Pubblicazione: (2024)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
di: Blanc, Guy, et al.
Pubblicazione: (2024)

Differentially Private Verification of Distribution Properties
di: Du, Elbert, et al.
Pubblicazione: (2026)

Efficient and Private Property Testing via Indistinguishability
di: Dwork, Cynthia, et al.
Pubblicazione: (2025)

Low-Degree Method Fails to Predict Robust Subspace Recovery
di: Jia, He, et al.
Pubblicazione: (2026)

Feature Selection and Junta Testing are Statistically Equivalent
di: Beretta, Lorenzo, et al.
Pubblicazione: (2025)

Samplability makes learning easier
di: Blanc, Guy, et al.
Pubblicazione: (2025)

Efficient Turing Machine Simulation with Transformers
di: Li, Qian, et al.
Pubblicazione: (2025)

Is nasty noise actually harder than malicious noise?
di: Blanc, Guy, et al.
Pubblicazione: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
di: Ding, Jingqiu, et al.
Pubblicazione: (2025)

The Computational Complexity of Almost Stable Clustering with Penalties
di: Khodamoradi, Kamyar, et al.
Pubblicazione: (2025)

AdaBoost is not an Optimal Weak to Strong Learner
di: Høgsgaard, Mikael Møller, et al.
Pubblicazione: (2023)

Supersimulators
di: Dwork, Cynthia, et al.
Pubblicazione: (2025)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
di: Hu, Bingbing, et al.
Pubblicazione: (2024)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)