93 citations · 578 across the 83 of their papers we have counts for
Showing 2012 · cs.CCShow all
2 papers · 2 filters
cs.CC2012★ 22 cited
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…
cs.CC2012★ 6 cited
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…