93 citations · 578 across the 83 of their papers we have counts for
3 papers · 1 filter
The Cutting Plane Method is Polynomial for Perfect Matchings
Karthekeyan Chandrasekaran, Laszlo A. Vegh, Santosh Vempala
The cutting plane approach to optimal matchings has been discussed by several authors over the past decades (e.g., Padberg and Rao '82, Grotschel and Holland '85, Lovasz and Plumme…
Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids
Daniel Dadush, Santosh Vempala
We give a deterministic 2^{O(n)} algorithm for computing an M-ellipsoid of a convex body, matching a known lower bound. This has several interesting consequences including improved…
Statistical Algorithms and a Lower Bound for Detecting Planted Clique
Vitaly Feldman, Elena Grigorescu, Lev Reyzin +2
We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle…