225 citations · 278 across the 25 of their papers we have counts for
10 papers · 1 filter
Engineering an Efficient Approximate DNF-Counter
Mate Soos, Uddalok Sarkar, Divesh Aggarwal +3
Model counting is a fundamental problem in many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In thi…
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
Divesh Aggarwal, Antoine Joux, Miklos Santha +1
The Unbounded Subset Sum (USS) problem is an NP-hard computational problem where the goal is to decide whether there exist non-negative integers such that $x_1 a…
Recursive lattice reduction -- A framework for finding short lattice vectors
Divesh Aggarwal, Thomas Espitau, Spencer Peters +1
We propose a recursive lattice reduction framework for finding short non-zero vectors or dense sublattices of a lattice. The framework works by recursively searching for dense subl…
Dimension-Preserving Reductions Between SVP and CVP in Different -Norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +2
We show a number of reductions between the Shortest Vector Problem and the Closest…
A -Time Algorithm for -SVP and -Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz
We show a -time algorithm that finds a (non-zero) vector in a lattice with norm at most $\tilde{O}(\sqrt{n})\cdot \min\{λ_1(\mathca…
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable c…
Slide Reduction, Revisited---Filling the Gaps in SVP Approximation
Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen +1
We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the f…
Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm
Divesh Aggarwal, Priyanka Mukhopadhyay
Blomer and Naewe[BN09] modified the randomized sieving algorithm of Ajtai, Kumar and Sivakumar[AKS01] to solve the shortest vector problem (SVP). The algorithm starts with $N = 2^{…
Just Take the Average! An Embarrassingly Simple -Time Algorithm for SVP (and CVP)
Divesh Aggarwal, Noah Stephens-Davidowitz
We show a -time (and space) algorithm for the Shortest Vector Problem on lattices (SVP) that works by repeatedly running an embarrassingly simple "pair and average" sie…
Solving the Closest Vector Problem in Time--- The Discrete Gaussian Strikes Again!
Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz
We give a -time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on -dimensional Euclidean lattices. This improves on the previous f…