Showing 2025Show all
2 papers · 1 filter
cs.DS2025
Learning and Testing Convex Functions
Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1
We consider the problems of \emph{learning} and \emph{testing} real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematic…
cs.DS2025
Quality control in sublinear time: a case study via random graphs
Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan
Many algorithms are designed to work well on average over inputs. But when such an algorithm is run on an arbitrary input, the question arises: Can we trust the algorithm on this i…