Source author record

Shashwat Garg

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Discrete Mathematics math.FA math.PR

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2016arXiv

Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

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 algorithm that finds a coloring with discrepancy $O((t \log n \log s)^{1/2})$ where $s$ is the maximum cardinality of a set. This improves upon the previous constructive bound of $O(t^{1/2} \log n)$ based on algorithmic variants of the partial coloring method, and for small $s$ (e.g. $s=\textrm{poly}(t)$ ) comes close to the non-constructive $O((t \log n)^{1/2})$ bound due to Banaszczyk. Previously, no algorithmic results better than $O(t^{1/2}\log n)$ were known even for $s = O(t^2)$ . Our method is quite robust and we give several refinements and extensions. For example, the coloring we obtain satisfies the stronger size-sensitive property that each set $S$ in the set system incurs an $O((t \log n \log |S|)^{1/2})$ discrepancy. Another variant can be used to essentially match Banaszczyk's bound for a wide class of instances even where $s$ is arbitrarily large. Finally, these results also extend directly to the more general Komlós setting.

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.

preprint2015arXiv

Tighter Estimates for epsilon-nets for Disks

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set $P$ of points, and a set $\mathcal{D}$ of geometric objects in the plane, the goal is to compute a small-sized subset of $P$ that hits all objects in $\mathcal{D}$ . In 1994, Bronniman and Goodrich made an important connection of this problem to the size of fundamental combinatorial structures called $ε$ -nets, showing that small-sized $ε$ -nets imply approximation algorithms with correspondingly small approximation ratios. Very recently, Agarwal and Pan showed that their scheme can be implemented in near-linear time for disks in the plane. Altogether this gives $O(1)$ -factor approximation algorithms in $\tilde{O}(n)$ time for hitting sets for disks in the plane. This constant factor depends on the sizes of $ε$ -nets for disks; unfortunately, the current state-of-the-art bounds are large -- at least $24/ε$ and most likely larger than $40/ε$ . Thus the approximation factor of the Agarwal and Pan algorithm ends up being more than $40$ . The best lower-bound is $2/ε$ , which follows from the Pach-Woeginger construction for halfspaces in two dimensions. Thus there is a large gap between the best-known upper and lower bounds. Besides being of independent interest, finding precise bounds is important since this immediately implies an improved linear-time algorithm for the hitting-set problem. The main goal of this paper is to improve the upper-bound to $13.4/ε$ for disks in the plane. The proof is constructive, giving a simple algorithm that uses only Delaunay triangulations. We have implemented the algorithm, which is available as a public open-source module. Experimental results show that the sizes of $ε$ -nets for a variety of data-sets is lower, around $9/ε$ .

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.

Shashwat Garg

Research overview

Is this your work?

4 publications

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

Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

Tighter Estimates for epsilon-nets for Disks

See the researcher in context

Building this map preview