BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Daniel Dadush

Daniel Dadush appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational Complexitymath.OCmath.FAComputational GeometryDiscrete Mathematicsmath.COmath.PRmath.MG

Catalog footprint

What is connected

19works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2022arXiv

A Simple Method for Convex Optimization in the Oracle Model

We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function $f$ over a convex set $K$ given by a separation oracle. Our method utilizes the Frank--Wolfe algorithm over the cone of valid inequalities of $K$ and subgradients of $f$. Under the assumption that $f$ is $L$-Lipschitz and that $K$ contains a ball of radius $r$ and is contained inside the origin centered ball of radius $R$, using $O(\frac{(RL)^2}{\varepsilon^2} \cdot \frac{R^2}{r^2})$ iterations and calls to the oracle, our main method outputs a point $x \in K$ satisfying $f(x) \leq \varepsilon + \min_{z \in K} f(z)$. Our algorithm is easy to implement, and we believe it can serve as a useful alternative to existing cutting plane methods. As evidence towards this, we show that it compares favorably in terms of iteration counts to the standard LP based cutting plane method and the analytic center cutting plane method, on a testbed of combinatorial, semidefinite and machine learning instances.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Geometric Rescaling Algorithms for Submodular Function Minimization

We present a new class of polynomial-time algorithms for submodular function minimization (SFM), as well as a unified framework to obtain strongly polynomial SFM algorithms. Our algorithms are based on simple iterative methods for the minimum-norm problem, such as the conditional gradient and Fujishige-Wolfe algorithms. We exhibit two techniques to turn simple iterative methods into polynomial-time algorithms. Firstly, we adapt the geometric rescaling technique, which has recently gained attention in linear programming, to SFM and obtain a weakly polynomial bound $O(({n}^4\cdot \textrm{EO} + {n}^5)\log ({n} L))$. Secondly, we exhibit a general combinatorial black-box approach to turn $\varepsilon L$-approximate SFM oracles into strongly polynomial exact SFM algorithms. This framework can be applied to a wide range of combinatorial and continuous algorithms, including pseudo-polynomial ones. In particular, we can obtain strongly polynomial algorithms by a repeated application of the conditional gradient or of the Fujishige-Wolfe algorithm. Combined with the geometric rescaling technique, the black-box approach provides an $O(({n}^5\cdot \textrm{EO} +{n}^6)\log^2{n})$ algorithm. Finally, we show that one of the techniques we develop in the paper can also be combined with the cutting-plane method of Lee, Sidford, and Wong \cite{LSW}, yielding a simplified variant of their $O(n^3 \log^2 n \cdot \textrm{EO} + n^4\log^{O(1)} n)$ algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Complexity of Branching Proofs

We consider the task of proving integer infeasibility of a bounded convex $K$ in $\mathbb{R}^n$ using a general branching proof system. In a general branching proof, one constructs a branching tree by adding an integer disjunction $\mathbf{a} \mathbf{x} \leq b$ or $\mathbf{a} \mathbf{x} \geq b+1$, $\mathbf{a} \in \mathbb{Z}^n$, $b \in \mathbb{Z}$, at each node, such that the leaves of the tree correspond to empty sets (i.e., $K$ together with the inequalities picked up from the root to leaf is empty). Recently, Beame et al (ITCS 2018), asked whether the bit size of the coefficients in a branching proof, which they named stabbing planes (SP) refutations, for the case of polytopes derived from SAT formulas, can be assumed to be polynomial in $n$. We resolve this question by showing that any branching proof can be recompiled so that the integer disjunctions have coefficients of size at most $(n R)^{O(n^2)}$, where $R \in \mathbb{N}$ such that $K \in R \mathbb{B}_1^n$, while increasing the number of nodes in the branching tree by at most a factor $O(n)$. As our second contribution, we show that Tseitin formulas, an important class of infeasible SAT instances, have quasi-polynomial sized cutting plane (CP) refutations, disproving the conjecture that Tseitin formulas are (exponentially) hard for CP. As our final contribution, we give a simple family of polytopes in $[0,1]^n$ requiring branching proofs of length $2^n/n$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

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

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 \langle c,{x}\rangle$, $Ax=b$, $x \geq 0$, $A \in \mathbb{Z}^{m \times 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\barχ_A)$, depending on Stewart's $\barχ_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\barχ_A$. Plugging in the recent algorithm of van den Brand (SODA '20), our method computes an optimal primal and dual solution using ${O}(m n^{ω+1} \log (n)\log(\barχ_A+n))$ arithmetic operations, outperforming the specialized interior point method of Vavasis and Ye and its recent improvement by Dadush et al (STOC '20). 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

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. The result also extends to the more general Komlós setting and gives an algorithmic O(log^{1/2} n) bound.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Lattice Distortion Problem

We introduce and study the \emph{Lattice Distortion Problem} (LDP). LDP asks how "similar" two lattices are. I.e., what is the minimal distortion of a linear bijection between the two lattices? LDP generalizes the Lattice Isomorphism Problem (the lattice analogue of Graph Isomorphism), which simply asks whether the minimal distortion is one. As our first contribution, we show that the distortion between any two lattices is approximated up to a $n^{O(\log n)}$ factor by a simple function of their successive minima. Our methods are constructive, allowing us to compute low-distortion mappings that are within a $2^{O(n \log \log n/\log n)}$ factor of optimal in polynomial time and within a $n^{O(\log n)}$ factor of optimal in singly exponential time. Our algorithms rely on a notion of basis reduction introduced by Seysen (Combinatorica 1993), which we show is intimately related to lattice distortion. Lastly, we show that LDP is NP-hard to approximate to within any constant factor (under randomized reductions), by a reduction from the Shortest Vector Problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

An important theorem of Banaszczyk (Random Structures & Algorithms `98) states that for any sequence of vectors of $\ell_2$ norm at most $1/5$ and any convex body $K$ of Gaussian measure $1/2$ in $\mathbb{R}^n$, there exists a signed combination of these vectors which lands inside $K$. A major open problem is to devise a constructive version of Banaszczyk's vector balancing theorem, i.e. to find an efficient algorithm which constructs the signed combination. We make progress towards this goal along several fronts. As our first contribution, we show an equivalence between Banaszczyk's theorem and the existence of $O(1)$-subgaussian distributions over signed combinations. For the case of symmetric convex bodies, our equivalence implies the existence of a universal signing algorithm (i.e. independent of the body), which simply samples from the subgaussian sign distribution and checks to see if the associated combination lands inside the body. For asymmetric convex bodies, we provide a novel recentering procedure, which allows us to reduce to the case where the body is symmetric. As our second main contribution, we show that the above framework can be efficiently implemented when the vectors have length $O(1/\sqrt{\log n})$, recovering Banaszczyk's results under this stronger assumption. More precisely, we use random walk techniques to produce the required $O(1)$-subgaussian signing distributions when the vectors have length $O(1/\sqrt{\log n})$, and use a stochastic gradient ascent method to implement the recentering procedure for asymmetric bodies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Towards Strong Reverse Minkowski-type Inequalities for Lattices

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 Lovász (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 $\ell_2$ case of the Kannan and Lovász conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure for based on "uncrossing" lattice subspaces.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Lattice Smoothing Parameter Problem

The smoothing parameter $η_ε(\mathcal{L})$ of a Euclidean lattice $\mathcal{L}$, introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is (informally) the smallest amount of Gaussian noise that "smooths out" the discrete structure of $\mathcal{L}$ (up to error $ε$). It plays a central role in the best known worst-case/average-case reductions for lattice problems, a wealth of lattice-based cryptographic constructions, and (implicitly) the tightest known transference theorems for fundamental lattice quantities. In this work we initiate a study of the complexity of approximating the smoothing parameter to within a factor $γ$, denoted $γ$-${\rm GapSPP}$. We show that (for $ε= 1/{\rm poly}(n)$): $(2+o(1))$-${\rm GapSPP} \in {\rm AM}$, via a Gaussian analogue of the classic Goldreich-Goldwasser protocol (STOC'98); $(1+o(1))$-${\rm GapSPP} \in {\rm coAM}$, via a careful application of the Goldwasser-Sipser (STOC'86) set size lower bound protocol to thin spherical shells; $(2+o(1))$-${\rm GapSPP} \in {\rm SZK} \subseteq {\rm AM} \cap {\rm coAM}$ (where ${\rm SZK}$ is the class of problems having statistical zero-knowledge proofs), by constructing a suitable instance-dependent commitment scheme (for a slightly worse $o(1)$-term); $(1+o(1))$-${\rm GapSPP}$ can be solved in deterministic $2^{O(n)} {\rm polylog}(1/ε)$ time and $2^{O(n)}$ space. As an application, we demonstrate a tighter worst-case to average-case reduction for basing cryptography on the worst-case hardness of the ${\rm GapSPP}$ problem, with $\tilde{O}(\sqrt{n})$ smaller approximation factor than the ${\rm GapSVP}$ problem. Central to our results are two novel, and nearly tight, characterizations of the magnitude of discrete Gaussian sums.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Shadow Simplex Method for Curved Polyhedra

We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds, which enforce that the boundary always meets vertices at sharp angles. Motivated by linear programs with totally unimodular constraint matrices, recent results of Bonifas et al (SOCG 2012), Brunsch and Röglin (ICALP 2013), and Eisenbrand and Vempala (2014) have improved our understanding of such polyhedra. We develop a new type of dual analysis of the shadow simplex method which provides a clean and powerful tool for improving all previously mentioned results. Our methods are inspired by the recent work of Bonifas and the first named author (SODA 2015), who analyzed a remarkably similar process as part of an algorithm for the Closest Vector Problem with Preprocessing. For our first result, we obtain a constructive diameter bound of $O(\frac{n^2}δ \ln \frac{n}δ)$ for $n$-dimensional polyhedra with curvature parameter $δ\in [0,1]$. For the class of polyhedra arising from totally unimodular constraint matrices, this implies a bound of $O(n^3 \ln n)$. For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected $O(\frac{n^3}δ \ln \frac{n}δ)$ simplex pivots, each requiring $O(m n)$ time to compute. An initial feasible solution can be found using $O(\frac{m n^3}δ \ln \frac{n}δ)$ pivot steps.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing

Improving on the Voronoi cell based techniques of Micciancio and Voulgaris (SIAM J. Comp. 13), and Sommer, Feder and Shalvi (SIAM J. Disc. Math. 09), we give a Las Vegas $\tilde{O}(2^n)$ expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the $\tilde{O}(4^n)$ deterministic runtime of the Micciancio Voulgaris algorithm, henceforth MV, for CVPP (which also solves CVP) at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the $\tilde{O}(4^n)$ path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Deterministic Polynomial Space Construction for eps-nets under any Norm

We give a deterministic polynomial space construction for nearly optimal eps-nets with respect to any input n-dimensional convex body K and norm |.|. More precisely, our algorithm can build and iterate over an eps-net of K with respect to |.| in time 2^O(n) x (size of the optimal net) using only poly(n)-space. This improves on previous constructions of Alon et al [STOC 2013] which achieve either a 2^O(n) approximation or an n^O(n) approximation of the optimal net size using 2^n space and poly(n)-space respectively. As in their work, our algorithm relies on the mathematically classical approach of building thin lattice coverings of space, which reduces the task of constructing eps-nets to the problem of enumerating lattice points. Our main technical contribution is a deterministic 2^O(n)-time and poly(n)-space construction of thin lattice coverings of space with respect to any convex body, where enumeration in these lattices can be efficiently performed using poly(n)-space. This also yields the first existential construction of poly(n)-space enumerable thin covering lattices for general convex bodies, which we believe is of independent interest. Our construction combines the use of the M-ellipsoid from convex geometry with lattice sparsification and densification techniques. As an application, we give a 2^O(n)(1+1/eps)^n time and poly(n)-space deterministic algorithm for computing a (1+eps)^n approximation to the volume of a general convex body, which nearly matches the lower bounds for volume estimation in the oracle model (the dependence on eps is larger by a factor 2 in the exponent). This improves on the previous results of Dadush and Vempala [PNAS 2013], which gave the above result only for symmetric bodies and achieved a dependence on eps of (1+log^{5/2}(1/eps)/eps^2)^n.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the existence of 0/1 polytopes with high semidefinite extension complexity

In Rothvoß it was shown that there exists a 0/1 polytope (a polytope whose vertices are in \{0,1\}^{n}) such that any higher-dimensional polytope projecting to it must have 2^{Ω(n)} facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high PSD extension complexity was left open. We answer this question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron projecting to it must be the intersection of a semidefinite cone of dimension~2^{Ω(n)} and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Lattice Sparsification and the Approximate Closest Vector Problem

We give a deterministic algorithm for solving the (1+eps)-approximate Closest Vector Problem (CVP) on any n dimensional lattice and any norm in 2^{O(n)}(1+1/eps)^n time and 2^n poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC 2010) and Dadush, Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the "AKS Sieve" based algorithms for (1+eps)-CVP (Ajtai, Kumar, and Sivakumar; STOC 2001 and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2^{O(n)} time algorithm for exact CVP in the l_2 norm, the space complexity of our algorithm can be reduced to polynomial. Our main technical contribution is a method for "sparsifying" any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS 2003) for the purpose of proving hardness for Shortest Vector Problem (SVP) under l_p norms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A O(1/eps^2)^n Time Sieving Algorithm for Approximate Integer Programming

The Integer Programming Problem (IP) for a polytope P \subseteq R^n is to find an integer point in P or decide that P is integer free. We give an algorithm for an approximate version of this problem, which correctly decides whether P contains an integer point or whether a (1+\eps) scaling of P around its barycenter is integer free in time O(1/\eps^2)^n. We reduce this approximate IP question to an approximate Closest Vector Problem (CVP) in a "near-symmetric" semi-norm, which we solve via a sieving technique first developed by Ajtai, Kumar, and Sivakumar (STOC 2001). Our main technical contribution is an extension of the AKS sieving technique which works for any near-symmetric semi-norm. Our results also extend to general convex bodies and lattices.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms

We give a deterministic O(log n)^n algorithm for the {\em Shortest Vector Problem (SVP)} of a lattice under {\em any} norm, improving on the previous best deterministic bound of n^O(n) for general norms and nearly matching the bound of 2^O(n) for the standard Euclidean norm established by Micciancio and Voulgaris (STOC 2010). Our algorithm can be viewed as a derandomization of the AKS randomized sieve algorithm, which can be used to solve SVP for any norm in 2^O(n) time with high probability. We use the technique of covering a convex body by ellipsoids, as introduced for lattice problems in (Dadush et al., FOCS 2011). Our main contribution is a deterministic approximation of an M-ellipsoid of any convex body. We achieve this via a convex programming formulation of the optimal ellipsoid with the objective function being an n-dimensional integral that we show can be approximated deterministically, a technique that appears to be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings

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 l_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 l_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 Sivakumar; STOC 2001 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 "flatness theorem," which satisfies f*(n) = O(n^{4/3} \polylog(n)) and is conjectured to be f*(n)=Θ(n). Our runtime improves upon the previous best of O(n^{2})^{n} by Hildebrand and Koppe (2010).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the Chvatal-Gomory Closure of a Compact Convex Set

In this paper, we show that the Chvatal-Gomory closure of a compact convex set is a rational polytope. This resolves an open question discussed in Schrijver [Schrijver 80'] and generalizes the same result for the case of rational polytopes [Schrijver 80'], rational ellipsoids [Dey-Vielma 10'] and strictly convex sets [Dadush-Dey-Vielma 10']. In particular, it shows that the CG closure of an irrational polytope is a rational polytope, which was the open question in [Schrijver 80'].

0 citations0 reviewsNo code linkedOpen access