First approximate calibration results for discrete properties in multiclass settings via Lipschitz intermediaries for strongly orderable discrete properties.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
citation-role summary
background 1
method 1
citation-polarity summary
verdicts
UNVERDICTED 5representative citing papers
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
Any low-success-probability LPN solver can be transformed into a high-success-probability solver on scaled parameters LPN with noise and dimension divided by k = Θ(1/δ log 1/ε).
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
Model checking for low-monodimensionality fragments of CMSO with disjoint-paths predicate is FPT on topological-minor-free graph classes.
citing papers explorer
-
Smoothed Elicitation Complexity for Approximate $\Gamma$-calibration of Discrete Classification Tasks
First approximate calibration results for discrete properties in multiclass settings via Lipschitz intermediaries for strongly orderable discrete properties.
-
Testable and Actionable Calibration for Full Swap Regret
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
-
Hardness Amplification for (Sparse) LPN
Any low-success-probability LPN solver can be transformed into a high-success-probability solver on scaled parameters LPN with noise and dimension divided by k = Θ(1/δ log 1/ε).
-
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
-
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Model checking for low-monodimensionality fragments of CMSO with disjoint-paths predicate is FPT on topological-minor-free graph classes.