57 citations · 245 across the 48 of their papers we have counts for
4 papers · 1 filter
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds
Moses Charikar, Shay Solomon
Despite significant research efforts, the state-of-the-art algorithm for maintaining an approximate matching in fully dynamic graphs has a polynomial {worst-case} update time, even…
Local Guarantees in Graph Cuts and Clustering
Moses Charikar, Neha Gupta, Roy Schwartz
Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min Cut, Multiway Cut, and Multicut, extensively studied in combinatorial opti…
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
Jacob Steinhardt, Moses Charikar, Gregory Valiant
We introduce a criterion, resilience, which allows properties of a dataset (such as its mean or best low rank approximation) to be robustly computed, even in the presence of a larg…
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
Yuchen Zhang, Percy Liang, Moses Charikar
We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for non-convex optimization. The algorithm performs stochastic gradient descent, where in each step it injects a…