4 papers · 1 filter
PAC Learning with Query Feedback
Chase Hutton, Adam Melrod, Han Shao
We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen…
Truly Work-efficient Parallel Deterministic -coloring and Maximal Independent Set
Chase Hutton, Adam Melrod
We give deterministic parallel algorithms that compute a -coloring and a maximal independent set for a simple graph with vertices and edges in work and $O(\…
High Probability Work Efficient Parallel Algorithms
Chase Hutton, Adam Melrod
Randomized parallel algorithms for many fundamental problems achieve optimal linear work in expectation, but upgrading this guarantee to hold with high probability (whp) remains a…
On Randomized Algorithms in Online Strategic Classification
Chase Hutton, Adam Melrod, Han Shao
Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions. For example, given a classifier that determine…