60 citations · 204 across the 15 of their papers we have counts for
6 papers · 1 filter
Minimax Rates for Robust Community Detection
Allen Liu, Ankur Moitra
In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolera…
From algorithms to connectivity and back: finding a giant component in random k-SAT
Zongchen Chen, Nitya Mani, Ankur Moitra
We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree -CNFs for large . In the course of doing so, we establi…
Learning in Observable POMDPs, without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Much of reinforcement learning theory is built on top of oracles that are computationally hard to implement. Specifically for learning near-optimal policies in Partially Observable…
Provably Auditing Ordinary Least Squares in Low Dimensions
Ankur Moitra, Dhruv Rohatgi
Measuring the stability of conclusions derived from Ordinary Least Squares linear regression is critically important, but most metrics either only measure local stability (i.e. aga…
Distilling Model Failures as Directions in Latent Space
Saachi Jain, Hannah Lawrence, Ankur Moitra +1
Existing methods for isolating hard subpopulations and spurious correlations in datasets often require human intervention. This can make these methods labor-intensive and dataset-s…
Planning in Observable POMDPs in Quasipolynomial Time
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Partially Observable Markov Decision Processes (POMDPs) are a natural and general model in reinforcement learning that take into account the agent's uncertainty about its current s…