Buchumschlag

Transductive Learning Is Compact

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Asilis, Julian, Devic, Siddartha, Dughmi, Shaddin, Sharan, Vatsal, Teng, Shang-Hua
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Machine Learning Computational Complexity Data Structures and Algorithms Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Regularization and Optimal Multiclass Learning
von: Asilis, Julian, et al.
Veröffentlicht: (2023)

Is Transductive Learning Equivalent to PAC Learning?
von: Dughmi, Shaddin, et al.
Veröffentlicht: (2024)

Proper Learnability and the Role of Unlabeled Data
von: Asilis, Julian, et al.
Veröffentlicht: (2025)

PAC Learning is just Bipartite Matching (Sort of)
von: Dughmi, Shaddin
Veröffentlicht: (2025)

Efficient Convex Optimization Requires Superlinear Memory
von: Marsden, Annie, et al.
Veröffentlicht: (2022)

First Order Logic on Pathwidth Revisited Again
von: Lampis, Michael
Veröffentlicht: (2022)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
von: Barto, Libor, et al.
Veröffentlicht: (2026)

Fine-grained Meta-Theorems for Vertex Integrity
von: Lampis, Michael, et al.
Veröffentlicht: (2021)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

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

Enumeration and updates for conjunctive linear algebra queries through expressibility
von: Muñoz, Thomas, et al.
Veröffentlicht: (2023)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
von: Černý, Marek, et al.
Veröffentlicht: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
von: Černý, Marek
Veröffentlicht: (2026)

Polynomial Logical Zonotope: A Set Representation for Reachability Analysis of Logical Systems
von: Alanwar, Amr, et al.
Veröffentlicht: (2023)

A faster FPRAS for #NFA
von: Meel, Kuldeep S., et al.
Veröffentlicht: (2023)

Smaller Circuits for Bit Addition
von: Goncharov, Mikhail, et al.
Veröffentlicht: (2025)

Finding hardness reductions automatically using SAT solvers
von: Bergold, Helena, et al.
Veröffentlicht: (2024)

Simultaneous Swap Regret Minimization via KL-Calibration
von: Luo, Haipeng, et al.
Veröffentlicht: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
von: Ding, Jingqiu, et al.
Veröffentlicht: (2025)

Private graphon estimation via sum-of-squares
von: Chen, Hongjie, et al.
Veröffentlicht: (2024)

On the Power of Interactive Proofs for Learning
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Superconstant Inapproximability of Decision Tree Learning
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

Learning-Augmented Algorithms for Boolean Satisfiability
von: Attias, Idan, et al.
Veröffentlicht: (2025)

Hardness of Maximum Likelihood Learning of DPPs
von: Grigorescu, Elena, et al.
Veröffentlicht: (2022)

A Distributional-Lifting Theorem for PAC Learning
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Active Learning for Decision Trees with Provable Guarantees
von: Moakhar, Arshia Soltani, et al.
Veröffentlicht: (2026)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

The Ideal Membership Problem and Abelian Groups
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2022)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
von: Masařík, Tomáš, et al.
Veröffentlicht: (2025)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
von: Sato, Atsuki, et al.
Veröffentlicht: (2025)

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

Fast decision tree learning solves hard coding-theoretic problems
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Adaptive and oblivious statistical adversaries are equivalent
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
von: Mardia, Jay, et al.
Veröffentlicht: (2024)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Differentially Private Verification of Distribution Properties
von: Du, Elbert, et al.
Veröffentlicht: (2026)

Efficient and Private Property Testing via Indistinguishability
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)