8 citations · 13 across the 13 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
Samplability makes learning easier
Guy Blanc, Caleb Koch, Jane Lange +2
The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contras…
cs.CC2022
Certification with an NP Oracle
Guy Blanc, Caleb Koch, Jane Lange +2
In the certification problem, the algorithm is given a function with certificate complexity and an input , and the goal is to find a certificate of size $\le \text…
cs.CC2019
Constructive derandomization of query algorithms
Guy Blanc, Jane Lange, Li-Yang Tan
We give efficient deterministic algorithms for converting randomized query algorithms into deterministic ones. We first give an algorithm that takes as input a randomized -query…