Arrow Research search

Author name cluster

Daniel Dadush

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

25 papers
1 author row

Possible papers

25

STOC Conference 2024 Conference Paper

A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column

  • Daniel Dadush
  • Zhuan Khye Koh
  • Bento Natura
  • Neil Olver
  • László A. Végh

We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Végh ‍(MOR ’17) and Megiddo ‍(SICOMP ’83), respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale’s 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) by Allamigeon, Dadush, Loho, Natura, and Végh ‍(FOCS ’22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum ‍(ORL ’04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices and extreme rays. Our approach is black-box and can be applied to any log-barrier path-following method.

Details

SODA Conference 2023 Conference Paper

Integrality Gaps for Random Integer Programs via Discrepancy

  • Sander Borst
  • Daniel Dadush
  • Dan Mikulincer

In this work, we prove new bounds on the additive gap between the value of a random integer program max c T x, Ax ≤ b, x ∈ {0, 1} n with m constraints and that of its linear programming relaxation for a wide range of distributions on ( A, b, c ). Our investigation is motivated by the work of Dey, Dubey, and Molinaro (SODA'21), who gave a framework for relating the size of Branch-and-Bound (B&B) trees to additive integrality gaps. Dyer and Frieze (MOR '89) and Borst et al. (Mathematical Programming '22), respectively, showed that for certain random packing and Gaussian IPs, where the entries of A, c are independently distributed according to either the uniform distribution on [0, 1] or the Gaussian distribution N (0, 1), the integrality gap is bounded by O m (log 2 n/n ) with probability at least 1 − 1/ n - e −Ω m (1). In this paper, we generalize these results to the cases where the entries of A are uniformly distributed on an integer interval (e. g. , entries in {-1, 0, 1}), and where the columns of A are distributed according to an isotropic logconcave distribution. Second, we substantially improve the success probability to 1 - 1/poly( n ), compared to constant probability in prior works (depending on m ). Leveraging the connection to Branch-and-Bound, our gap results imply that for these IPs B&B trees have size n poly( m ) with high probability (i. e. , polynomial for fixed m ), which significantly extends the class of IPs for which B&B is known to be polynomial. Our main technical contribution and the key to achieving the above results is a new linear discrepancy theorem for random matrices. Our theorem gives general conditions under which a target vector is equal to or very close to a {0, 1} combination of the columns of a random matrix A. Compared to prior results, our theorem handles a much wider range of distributions on A, both continuous and discrete, and achieves success probability exponentially close to 1, as opposed to the constant probability shown in earlier results. Our proof uses a Fourier analytic approach, building on the work of Hoberg and Rothvoss (SODA '19) and Franks and Saks (RSA '20) who studied the discrepancy of random set systems and matrices respectively.

Details

STOC Conference 2022 Conference Paper

A new framework for matrix discrepancy: partial coloring bounds via mirror descent

  • Daniel Dadush
  • Haotian Jiang
  • Victor Reis

Motivated by the Matrix Spencer conjecture, we study the problem of finding signed sums of matrices with a small matrix norm. A well-known strategy to obtain these signs is to prove, given matrices A 1 , …, A n ∈ ℝ m × m , a Gaussian measure lower bound of 2 − O ( n ) for a scaling of the discrepancy body { x ∈ ℝ n : || ∑ i =1 n x i A i || ≤ 1}. We show this is equivalent to covering its polar with 2 O ( n ) translates of the cube 1/ n B ∞ n , and construct such a cover via mirror descent. As applications of our framework, we show:

Details

FOCS Conference 2022 Conference Paper

Interior point methods are not worse than Simplex

  • Xavier Allamigeon
  • Daniel Dadush
  • Georg Loho
  • Bento Natura
  • László A. Végh

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound $O(2^{n}n^{15}\log n)$ for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most $O(n^{15}\log n)$ times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths. From the existence of a line segment in the wide neighborhood we derive strong implications on the structure of the corresponding segment of the central path. Our algorithm is able to detect this structure from the local geometry at the current iterate, and constructs a step direction that descends along this segment. The bound $O(n^{15}\log n)$ that applies for arbitrarily long line segments is derived from a combinatorial progress measure. Our algorithm falls into the family of layered least squares interior point methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to previous layered least squares methods that partition the kernel of the constraint matrix into coordinate subspaces, our method creates layers based on a general subspace providing more flexibility. Our result also implies the same bound on the number of iterations of the trust region interior point method by Lan, Monteiro, and Tsuchiya (SIOPT 2009).

Details

SODA Conference 2022 Conference Paper

On finding exact solutions of linear programs in the oracle model

  • Daniel Dadush
  • László A. Végh
  • Giacomo Zambelli

We consider linear programming in the oracle model: min c T x s. t. x ∊ P, where the polyhedron P = { x ∊ ℝ n: Ax ≤ b } is given by a separation oracle that returns violated inequalities from the system Ax ≤ b. We present an algorithm that finds exact primal and dual solutions using O(n 2 log( n/δ )) oracle calls and O(n 4 log ( n/δ ) + n 6 log log(1/ δ )) arithmetic operations, where δ is a geometric condition number associated with the system ( A, b ). These bounds do not depend on the cost vector c. The algorithm works in a black box manner, requiring a subroutine for approximate primal and dual solutions; the above running times are achieved when using the cutting plane method of Jiang, Lee, Song, and Wong (STOC 2020) for this subroutine. Whereas approximate solvers may return primal solutions only, we develop a general framework for extracting dual certificates based on the work of Burrell and Todd (Math. Oper. Res. 1985). Our algorithm works in the real model of computation, and extends results by Grötschel, Lovász, and Schrijver (Prog. Comb. Opt. 1984), and by Frank and Tardos (Combinatorica 1987) on solving LPs in the bit-complexity model. We show that under a natural assumption, simultaneous Diophantine approximation in these results can be avoided.

Details

FOCS Conference 2020 Conference Paper

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers

  • Daniel Dadush
  • Bento Natura
  • László A. Végh

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based framework for solving linear programming (LP) in time depending only on the constraint matrix in the bit complexity model. In Tardos's framework, one reduces solving the LP min(c, x), Ax=b, x ≥ 0, A Z m×n, to solving O(nm) LPs in A having small integer coefficient objectives and right-hand sides using any exact LP algorithm. This gives rise to an LP algorithm in time poly (n, m log Δ A ), where Δ A is the largest subdeterminant of A. A significant extension to the real model of computation was given by Vavasis and Ye (Math. Prog. '96), giving a specialized interior point method that runs in time poly (n, m, log χ̑ A ), depending on Stewart's χ̑ A, a well-studied condition number. In this work, we extend Tardos's original framework to obtain such a running time dependence. In particular, we replace the exact LP solves with approximate ones, enabling us to directly leverage the tremendous recent algorithmic progress for approximate linear programming. More precisely, we show that the fundamental “accuracy” needed to exactly solve any LP in A is inverse polynomial in n and log χ̑ A. Plugging in the recent algorithm of van den Brand (SODA '20), our method computes an optimal primal and dual solution using O(mn ω+1+0(1) log(χ̑ A +n)) arithmetic operations, outperforming the specialized interior point method of Vavasis and Ye and its recent improvement by Dadush et al (STOC '20). By applying the preprocessing algorithm of the latter paper, the dependence can also be reduced from χ̑ A to χ̑ A *, the minimum value of χ̑ AD attainable via column rescalings. Our framework is applicable to achieve the poly (n, m, log χ̑ A *) bound using essentially any weakly polynomial LP algorithm, such as the ellipsoid method. At a technical level, our framework combines together approximate LP solutions to compute exact ones, making use of constructive proximity theorems-which bound the distance between solutions of “nearby” LPs-to keep the required accuracy low.

Details

STOC Conference 2019 Conference Paper

On approximating the covering radius and finding dense lattice subspaces

  • Daniel Dadush

In this work, we give a novel algorithm for computing dense lattice subspaces, a conjecturally tight characterization of the lattice covering radius, and provide a bound on the slicing constant of lattice Voronoi cells. Our work is motivated by the pursuit of faster algorithms for integer programming, for which we give a conditional speedup based on the recent resolution of the ℓ 2 Kannan-Lovász conjecture. Through these results, we hope to motivate further study of the interplay between the recently developed reverse Minkowski theory, lattice algorithms and convex geometry. On the algorithmic side, our main contribution is a 2 O ( n ) -time algorithm for computing a O ( C η ( n ))-approximate sublattice of minimum normalized determinant on any n -dimensional lattice, where C η ( n ) = O (log n ) is the reverse Minkowski constant in dimension n . Our method for finding dense lattice subspaces is surprisingly simple: we iteratively descend to a random co-dimension 1 subspace chosen to be the orthogonal space to a discrete Gaussian sample from the dual lattice. Applying this algorithm within a “filtration reduction” scheme, we further show how to compute a O ( C η ( n ))-approximate canonical filtration of any lattice, which corresponds to a canonical way of decomposing a lattice into dense blocks. As a primary application, we get the first 2 O ( n ) -time algorithm for computing a sparse lattice projection whose “volume radius” provides a lower bound on the lattice covering radius that is tight within a O (log 2.5 n )-factor. This provides an efficient algorithmic version of the ℓ 2 Kannan-Lovász conjecture, which was recently resolved by Regev and Stephens-Davidowitz (STOC ’2017). On the structural side, we prove a new lower bound on the covering radius which combines volumetric lower bounds across a chain of lattice projections. Assuming Bourgain’s slicing conjecture restricted to Voronoi cells of stable lattices, our lower bound implies (somewhat surprisingly) that the problem of approximating the lattice covering radius to within a constant factor is in . Complementing this result, we show that the slicing constant of any n -dimensional Voronoi cell is bounded by O ( C KL ,2 ( n )) = O (log 1.5 n ), the ℓ 2 Kannan-Lovász constant, which complements the O (log n ) bound of Regev and Stephens-Davidowitz for stable Voronoi cells.

Details

STOC Conference 2018 Conference Paper

A friendly smoothed analysis of the simplex method

  • Daniel Dadush
  • Sophie Huiberts

Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method was given by Spielman and Teng (JACM ‘04), who the developed the notion of smoothed analysis. Starting from an arbitrary linear program with d variables and n constraints, Spielman and Teng analyzed the expected runtime over random perturbations of the LP (smoothed LP), where variance σ Gaussian noise is added to the LP data. In particular, they gave a two-stage shadow vertex simplex algorithm which uses an expected O ( n 86 d 55 σ −30 ) number of simplex pivots to solve the smoothed LP. Their analysis and runtime was substantially improved by SpielmanDeshpande (FOCS ‘05) and later Vershynin (SICOMP ‘09). The fastest current algorithm, due to Vershynin, solves the smoothed LP using an expected O ( d 3 log 3 n σ −4 + d 9 log 7 n ) number of pivots, improving the dependence on n from polynomial to logarithmic.

Details

FOCS Conference 2018 Conference Paper

Balancing Vectors in Any Norm

  • Daniel Dadush
  • Aleksandar Nikolov
  • Kunal Talwar
  • Nicole Tomczak-Jaegermann

In the vector balancing problem, we are given symmetric convex bodies C and K in R^n, and our goal is to determine the minimum number β ≥ 0, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside β K. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Appl. ~Math '81), Spencer's "six standard deviations suffice" theorem (Trans. ~Amer. ~Math. ~Soc '85) and Banaszczyk's vector balancing theorem (Random Structures & Algorithms '98) correspond to bounds on vector balancing constants. The above theorems have inspired much research in recent years within theoretical computer science. In this work, we show that all vector balancing constants admit "good" approximate characterizations, with approximation factors depending only polylogarithmically on the dimension n. First, we show that a volumetric lower bound due to Banaszczyk is tight within a O(log n) factor. Our proof is algorithmic, and we show that Rothvoss's (FOCS '14) partial coloring algorithm can be analyzed to obtain these guarantees. Second, we present a novel convex program which encodes the "best possible way" to apply Banaszczyk's vector balancing theorem for bounding vector balancing constants from above, and show that it is tight within an O(log^2. 5 n) factor. This also directly yields a corresponding polynomial time approximation algorithm both for vector balancing constants, and for the hereditary discrepancy of any sequence of vectors with respect to an arbitrary norm.

Details

STOC Conference 2018 Conference Paper

The gram-schmidt walk: a cure for the Banaszczyk blues

  • Nikhil Bansal 0001
  • Daniel Dadush
  • Shashwat Garg
  • Shachar Lovett

An important result in discrepancy due to Banaszczyk states that for any set of n vectors in ℝ m of ℓ 2 norm at most 1 and any convex body K in ℝ m of Gaussian measure at least half, there exists a ± 1 combination of these vectors which lies in 5 K . This result implies the best known bounds for several problems in discrepancy. Banaszczyk’s proof of this result is non-constructive and an open problem has been to give an efficient algorithm to find such a ± 1 combination of the vectors.

Details

FOCS Conference 2016 Conference Paper

An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound

  • Nikhil Bansal 0001
  • Daniel Dadush
  • Shashwat Garg

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n) 1/2 ), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t 1/2 log n) bound. Our result also extends to the more general Komlós setting and gives an algorithmic O(log 1/2 n) bound.

Details

FOCS Conference 2016 Conference Paper

Towards Strong Reverse Minkowski-Type Inequalities for Lattices

  • Daniel Dadush
  • Oded Regev 0001

We present a natural reverse Minkowski-type inequality for lattices, which gives upper bounds on the number of lattice points in a Euclidean ball in terms of sublattice determinants, and conjecture its optimal form. The conjecture exhibits a surprising wealth of connections to various areas in mathematics and computer science, including a conjecture motivated by integer programming by Kannan and Lovasz (Annals of Math. 1988), a question from additive combinatorics asked by Green, a question on Brownian motions asked by Saloff-Coste (Colloq. Math. 2010), a theorem by Milman and Pisier from convex geometry (Ann. Probab. 1987), worst-case to average-case reductions in lattice-based cryptography, and more. We present these connections, provide evidence for the conjecture, and discuss possible approaches towards a proof. Our main technical contribution is in proving that our conjecture implies the l2 case of the Kannan and Lovasz conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure based on "uncrossing" lattice subspaces.

Details

FOCS Conference 2015 Conference Paper

Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!

  • Divesh Aggarwal
  • Daniel Dadush
  • Noah Stephens-Davidowitz

We give a 2 n+o(n) -time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic Õ(4 n )-time and Õ(2 n )-space algorithm of Micciancio and Voulgaris [1]. We achieve our main result in three steps. First, we show how to modify the sampling algorithm from [2] to solve the problem of discrete Gaussian sampling over lattice shifts, L - t, with very low parameters. While the actual algorithm is a natural generalization of [2], the analysis uses substantial new ideas. This yields a 2 n+o(n) -time algorithm for approximate CVP with the very good approximation factor γ = 1 + 2 -o(n/ log n). Second, we show that the approximate closest vectors to a target vector t can be grouped into “lower-dimensional clusters, ” and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that “behaves well with these clusters. ” Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.

Details

STOC Conference 2015 Conference Paper

Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling: Extended Abstract

  • Divesh Aggarwal
  • Daniel Dadush
  • Oded Regev 0001
  • Noah Stephens-Davidowitz

We give a randomized 2 n+o(n) -time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic ~O(4 n )-time and ~O(2 n )-space algorithm of Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample 2 n/2 vectors from the discrete Gaussian distribution at any parameter in 2 n+o(n) time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate 2 n/2 discrete Gaussian samples in just 2 n/2+o(n) time and space. Among other things, this implies a 2 n/2+o(n) -time and space algorithm for 1.93-approximate decision SVP.

Details

SODA Conference 2012 Conference Paper

Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms

  • Daniel Dadush
  • Santosh S. Vempala

We give a deterministic O (log n ) n -time and space algorithm for the Shortest Vector Problem (SVP) of a lattice under any norm, improving on the previous best deterministic n O ( n ) -time algorithms for general norms. This approaches the 2 O ( n ) -time and space complexity of the randomized sieve based SVP algorithms (Arvind and Joglekar, FSTTCS 2008), first introduced by Ajtai, Kumar and Sivakumar (STOC 2001) for ℓ 2 -SVP, and the M-ellipsoid covering based SVP algorithm of Dadush et al. (FOCS 2011).

Details

STOC Conference 2012 Conference Paper

Unconditional differentially private mechanisms for linear queries

  • Aditya Bhaskara
  • Daniel Dadush
  • Ravishankar Krishnaswamy
  • Kunal Talwar

We investigate the problem of designing differentially private mechanisms for a set of d linear queries over a database, while adding as little error as possible. Hardt and Talwar [HT10] related this problem to geometric properties of a convex body defined by the set of queries and gave a O(log 3 d)-approximation to the minimum l 2 2 error, assuming a conjecture from convex geometry called the Slicing or Hyperplane conjecture. In this work we give a mechanism that works unconditionally, and also gives an improved O(log 2 d) approximation to the expected l 2 2 error. We remove the dependence on the Slicing conjecture by using a result of Klartag [Kla06] that shows that any convex body is close to one for which the conjecture holds; our main contribution is in making this result constructive by using recent techniques of Dadush, Peikert and Vempala [DPV10]. The improvement in approximation ratio relies on a stronger lower bound we derive on the optimum. This new lower bound goes beyond the packing argument that has traditionally been used in Differential Privacy and allows us to add the packing lower bounds obtained from orthogonal subspaces. We are able to achieve this via a symmetrization argument which argues that there always exists a near optimal differentially private mechanism which adds noise that is independent of the input database! We believe this result should be of independent interest, and also discuss some interesting consequences.

Details

FOCS Conference 2011 Conference Paper

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

  • Daniel Dadush
  • Chris Peikert
  • Santosh S. Vempala

We give a novel algorithm for enumerating lattice points in any convex body, and give applications to several classic lattice problems, including the Shortest and Closest Vector Problems (SVP and CVP, respectively) and Integer Programming (IP). Our enumeration technique relies on a classical concept from asymptotic convex geometry known as the M-ellipsoid, and uses as a crucial subroutine the recent algorithm of Micciancio and Voulgaris (STOC 2010)for lattice problems in the ℓ 2 norm. As a main technical contribution, which may be of independent interest, we build on the techniques of Klartag (Geometric and Functional Analysis, 2006) to give an expected 2 O(n) -time algorithm for computing an M-ellipsoid for any n-dimensional convex body. As applications, we give deterministic 2 O(n) -time and -space algorithms for solving exact SVP, and exact CVP when the target point is sufficiently close to the lattice, on n-dimensional lattices in any (semi-)norm given an M-ellipsoid of the unit ball. In many norms of interest, including all ℓ p norms, an M-ellipsoid is computable in deterministic poly(n) time, in which case these algorithms are fully deterministic. Here our approach may be seen as a derandomization of the "AKS sieve" for exact SVP and CVP (Ajtai, Kumar, and Siva Kumar, STOC2001 and CCC 2002). As a further application of our SVP algorithm, we derive an expected O(f*(n)) n -time algorithm for Integer Programming, where f*(n) denotes the optimal bound in the so-called "flatnesstheorem, " which satisfies f*(n) = O(n 4/3 polylog(n))and is conjectured to be f*(n) = O(n). Our runtime improves upon the previous best of O(n 2 ) n by Hildebrand and Koppe (2010).

Details
v2026.09.13