PUBLICATIONS

[PDF]

Zarankiewicz problem is about upper bounding the number of edges in graphs that are free of K_{r,r}. We show that many low-dimensional graphs have Zarankiewicz number as low as O(nr), which is asymptotically the lowest possible. 

[PDF]

The paper is written in memory of our friend, Sumedha Uniyal, who passed away in 2020. 

[PDF] 

We look at arborescence problems with multiple roots from the primal-dual perspectives. Our main results are tight bounds for these problems via LP rounding techniques. 

[short] [full]  

We propose a new family of bounds (that generalizes the classical access lemma) for binary search trees. This allows us to "unify" many strong BST bounds that have appeared in the literature under the same framework. 

[PDF] 

We show that robust clustering (aka socially fair clustering) becomes more tractable in Euclidean spaces, in contrast to the general metric spaces. In particular, while the Gap-ETH hardness is (3-o(1)) for general metrics, our algorithms can break a factor of 3 in high-dimensional Euclidean spaces. In sub-logarithmic dimension, we present an approximation scheme.  

[PDF]

Improved upper bounds for sorting sequences avoiding a given permutation. The bounds are proved by tight analysis of the density of 0-1 matrices that forbid a certain product pattern.  

[PDF]

We define the notion of combinatorial diameter of a tree decomposition and show that a natural LP rounding gives approximation ratio and running time depending on this diameter. 

[PDF] 

We consider the maximum independent set problem and show that any approximation algorithm with a ``non-trivial'' approximation ratio (as a function of the number of vertices of the input graph G) can be turned into an algorithm achieving almost the same ratio, albeit as a function of the treewidth of G. 

[PDF]

We give a clean and simple approximation scheme for clustering problems. Our algorithm (despite being oblivious to the input structures and objective functions) handles almost all known clustering objectives as well as multiple metric spaces. 

[PDF] 

Forbidden submatrix theory (more generally extremal combinatorics techniques) has been used as a potential by-pass for the design of potential function (for which we lack systematic understanding). This paper shows how to better harness the power of extremal combinatorics in analyzing binary search trees by a careful decomposition of execution logs of BSTs.  

[PDF]

A near-linear-time LP solver for the standard covering LP for k-ECSS is presented. This leads to a fast algorithm for (2+epsilon)-approximating k-ECSS in time O(m+(kn)^1.5). The previous best 2-approximation in time O(mnk) was presented in 1990 by Khuller & Vishkin.  

[PDF]

We introduced a new combinatorial problem that connects three distinct areas: data structures, geometry, and approximation algorithms. Our problem generalizes the minimum cost binary search trees, is a node-weighted variant of Manhattan Network, and is a special case of node-weighted Steiner forests. 

[PDF]  

We show that any rectangle graphs are O(q log q) colorable where q = maximum clique size. This is the first asymptotic improvement over the six-decade-old bound by Asplund and Grunbaum in 1960. 

[PDF] 

We initiated the study of parameterized variants of mimicking networks (roughly, a graph that preserves all cut structures among the designated "terminals"). We presented two applications.

[PDF] 

We proposed a new potential function based on counting inversions in binary search trees.  We use our potential function to derive old and new bounds. 

[PDF]

We present geometric approximation algorithms and lower bounds for finding a minimum cost binary search tree. Our main results (i) confirm the gap of O(log log n) between the Wilber's alternation bound and OPT, and (ii) present the first sub-exponential time constant approximation for the problem. 

[PDF] 

The first approximation algorithm for balanced bicliques with approximation guarantee beyond "enumeration". 

The Tuza conjecture postulates that the duality ratio between transversal size and triangle packing is at most 2 in any graph. We show an algorithmic proof of a relaxed statement. The duality ratio is bounded by a local-search type argument. 

[PDF] 

We show that any plane graph contains a cactus subgraph that captures 1/6 fraction of the triangular faces. An immediate application is a 4/9 approximation algorithm for finding the maximum planar subgraph .

[PDF] 

We consider some central NP-hard optimization problems (independent set, vertex cover, coloring) in the exponential-time approximation setting. We show the first sets of algorithms that perform better than the brute-force results and discuss the connections with PCP parameters.  

[PDF] 

We show how to simulate the binary search trees (BST) with multiple finger in the standard BST model with a near-optmal loss. We also illustrate the power and limitations of the multi-finger model. 

[PDF] 

We give algorithms for various survivable network design problems in the low-treewidth setting. 

[PDF] 

We illustrate the use of Gap Exponential-Time Hypothesis (Gap-ETH) in proving parameterized inapproximability. 

[PDF]