71 citations · 437 across the 49 of their papers we have counts for
54 papers
Transductive Learning Is Compact
Julian Asilis, Siddartha Devic, Shaddin Dughmi +2
We demonstrate a compactness result holding broadly across supervised learning with a general class of loss functions: Any hypothesis class is learnable with transductive sampl…
Regularization and Optimal Multiclass Learning
Julian Asilis, Siddartha Devic, Shaddin Dughmi +2
The quintessential learning algorithm of empirical risk minimization (ERM) is known to fail in various settings for which uniform convergence does not characterize learning. It is…
Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings
Kyle Burke, Matthew Ferland, Shanghua Teng
The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among…
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
Kyle Burke, Matthew Ferland, Shanghua Teng
We settle two long-standing complexity-theoretical questions-open since 1981 and 1993-in combinatorial game theory (CGT). We prove that the Grundy value (a.k.a. nim-value, or nimbe…
Transverse Wave: an impartial color-propagation game inspired by Social Influence and Quantum Nim
Kyle Burke, Matthew Ferland, Shanghua Teng
In this paper, we study a colorful, impartial combinatorial game played on a two-dimensional grid, Transverse Wave. We are drawn to this game because of its apparent simplicity, co…
On the Equivalence Between High-Order Network-Influence Frameworks: General-Threshold, Hypergraph-Triggering, and Logic-Triggering Models
Wei Chen, Shang-Hua Teng, Hanrui Zhang
In this paper, we study several high-order network-influence-propagation frameworks and their connection to the classical network diffusion frameworks such as the triggering model…