DUTTA , Kunal

A k-uniform hypergraph is d-degenerate if every induced subgraph has a vertex of degree at most d. Given a k-uniform hyper-graph H = (V (H), E(H)), we show there exists an induced subgraph of size at least $v∈V (H) min (1, c_k d + (1/ d_H (v) + 1)^{1/(k−1)}$ , where $c_k = 2^{−(1+ 1/ k−1)}( 1 − 1/ k)$ and d_H (v) denotes the degree of ver-tex v...

A $k$-uniform hypergraph has degeneracy bounded by $d$ if every induced subgraph has a vertex of degree at most $d$. Given a $k$-uniform hypergraph $H = (V (H), E(H))$, we show there exists an induced subgraph of size at least $\sum{v\in V (H)} \min \left\{1, c_k\left(\frac{ d + 1}{ d_{H (v)} + 1}\right)^{1/(k−1)}\right\}$, where $c_k =...

We consider the edge collapse (introduced in [Boissonnat, Pritam. SoCG 2020]) process on the Erdős-Rényi random clique complex X(n,c/√n) on n vertices with edge probability c/√n such that c > √η₂ where η₂ = inf{η | x = e^{-η(1-x)²} has a solution in (0,1)}. For a given c > √η₂, we show that after t iterations of maximal edge collapsing phases,...

Computing persistent homology using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, contrary to the case of computing persistent homology using the Euclidean distance or even the k-distance, it is not known how to compute the persistent...

Computing persistent homology of large datasets using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, unlike in the case of persistent homology computation using the Euclidean distance or the k-distance, using Gaussian kernels involves...

We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let V be a finite set system defined over an n-point set X; we view V as a set of indicator vectors over the n-dimensional unit cube. A δ-separated set of V is a subcollection W, s.t. the Hamming distance between each pair...

The Khatri-\v{S}id\'{a}k lemma says that for any Gaussian measure $\mu$ over $\mathbb{R}^n$ , given a convex set $K$ and a slab $L$, both symmetric about the origin, one has $\mu(K \cap L) \geq \mu(K)\mu(L)$. We state and prove a new asymmetric version of the Khatri-\v{S}id\'{a}k lemma when $K$ is a symmetric convex body and $L$ is a slab (not...

Showing the existence of small-sized epsilon-nets has been the subject of investigation for almost 30 years, starting from the breakthrough of Haussler and Welzl (1987). Following a long line of successive improvements, recent results have settled the question of the size of the smallest epsilon-nets for set systems as a function of their...

The packing lemma of Haussler states that given a set system $(X, R)$ with bounded VC dimension, if every pair of sets in $R$ are 'far apart' (i.e., have large symmetric difference), then $R$ cannot contain too many sets. This has turned out to be the technical foundation for many results in geometric discrepancy using the entropy method (see...

Given a set system (X,R) such that every pair of sets in R have large symmetric difference, the Shallow Packing Lemma gives an upper bound on |R| as a function of the shallow-cell complexity of R. In this paper, we first present a matching lower bound. Then we give our main theorem, an application of the Shallow Packing Lemma: given a...

Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy [Proc. SoCG, 2014 ]. We show that any linear transformation that preserves...

In this paper, we consider variants of the Geometric Subset General Position problem. In defining this problem, a geometric subsystem is specified, like a subsystem of lines, hyperplanes or spheres. The input of the problem is a set of n points in R d and a positive integer k. The objective is to find a subset of at least k input points such...

The randomized incremental construction (RIC) for building geometric data structures has been analyzed extensively, from the point of view of worst-case distributions. In many practical situations however, we have to face nicer distributions. A natural question that arises is: do the usual RIC algorithms automatically adapt when the point...

Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy (The persistent homology of distance functions under random projection. In Cheng,...

Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are most of the time space and time optimal in...

Randomized incremental construction(RIC) is one of the most important paradigms for buildinggeometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice.Randomized incremental constructions are most of the time space and time optimal in the...

The Point Hyperplane Cover problem in R d takes as input a set of n points in R d and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Hitting Set (D-Polynomial Points HS) problem in R d takes as input a family F of D-degree polynomials from a vector space R in R d...

The Point Hyperplane Cover problem in $R d$ takes as input a set of $n$ points in $R d$ and a positive integer $k$. The objective is to cover all the given points with a set of at most $k$ hyperplanes. The D-Polynomial Points Cover problem in $R d$ takes as input a family $F$ of D-degree polynomials from a vector space $R$ in $R d$ , and...

Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are usually space-optimal and time-optimal in the...