Pith. sign in

REVIEW 1 cited by

Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1201.5972 v2 pith:45GMQNWG submitted 2012-01-28 cs.CC cs.DSmath.FA

Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids

Daniel Dadush , Santosh Vempala This is my paper
classification cs.CC cs.DSmath.FA
keywords deterministicalgorithmsconvexlatticeproblemsvolumealgorithmbodies
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
read the original abstract

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 deterministic algorithms for volume estimation of convex bodies and the shortest and closest lattice vector problems under general norms.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Exact Algorithms for Minimum Steiner Point Trees

    cs.CG 2026-08 conditional novelty 7.0

    An exact n^{O(n)}-time algorithm computes an optimal implicit Steiner tree for STP-MSPBEL in the plane, with the bound independent of the number of Steiner points.