Author

S. Dughmi

h-index 27 View on Semantic Scholar

We have 3 of 86 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Sep 2026

The Strong Secretary Conjecture is True for Linear Matroids

We prove a $1/e$ guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online. In the known-matroid model, the...

Kristóf Bérczi, S. Dughmi, V. Livanos et al. · 5 citations

#machine learning Preprint Sep 2026

Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning

We continue the study of relatively smart learning, introduced by Dughmi and Pour (2026), which asks a supervised learner to compete, marginal by marginal, with every distribution-fixed error guarantee soundly certifiable from unlabeled data. They showed that the One-Inclusion Graph (OIG) learner is relatively smart wi...

S. Dughmi, Alireza F. Pour · 0 citations

Preprint Aug 2026

When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification

This work exhibits a learnable multiclass problem that becomes altogether unlearnable under a monotone adversary, and shows an analogous result for partial binary concept classes, and demonstrates that monotone adversaries are frighteningly more powerful in each of these settings.

Julian Asilis, S. Dughmi, Chirag Pabbaraju · 0 citations