Source author record

Vivek Madan

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 Discrete Mathematics math.CO Computational Complexity Logic in Computer Science Machine Learning math.LO math.OC

Catalog footprint

Research overview

5works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Maximizing Determinants under Matroid Constraints

Given vectors $v_1,\dots,v_n\in\mathbb{R}^d$ and a matroid $M=([n],I)$ , we study the problem of finding a basis $S$ of $M$ such that $\det(\sum_{i \in S}v_i v_i^\top)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning. The current best results include an $e^{2k}$ -estimation for any matroid of rank $k$ and a $(1+ε)^d$ -approximation for a uniform matroid of rank $k\ge d+\frac dε$ , where the rank $k\ge d$ denotes the desired size of the optimal set. Our main result is a new approximation algorithm with an approximation guarantee that depends only on the dimension $d$ of the vectors and not on the size $k$ of the output set. In particular, we show an $(O(d))^{d}$ -estimation and an $(O(d))^{d^3}$ -approximation for any matroid, giving a significant improvement over prior work when $k\gg d$ . Our result relies on the existence of an optimal solution to a convex programming relaxation for the problem which has sparse support; in particular, no more than $O(d^2)$ variables of the solution have fractional values. The sparsity results rely on the interplay between the first-order optimality conditions for the convex program and matroid theory. We believe that the techniques introduced to show sparsity of optimal solutions to convex programs will be of independent interest. We also give a randomized algorithm that rounds a sparse fractional solution to a feasible integral solution to the original problem. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials and show new relationships between different convex programs studied for the problem. Finally, we use the estimation algorithm and sparsity results to give an efficient deterministic approximation algorithm with an approximation guarantee that depends solely on the dimension $d$ .

preprint2016arXiv

Approximating Multicut and the Demand Graph

In the minimum Multicut problem, the input is an edge-weighted supply graph $G=(V,E)$ and a simple demand graph $H=(V,F)$ . Either $G$ and $H$ are directed (DMulC) or both are undirected (UMulC). The goal is to remove a minimum weight set of edges in $G$ such that there is no path from $s$ to $t$ in the remaining graph for any $(s,t) \in F$ . UMulC admits an $O(\log k)$ -approximation where $k$ is the vertex cover size of $H$ while the best known approximation for DMulC is $\min\{k, \tilde{O}(n^{11/23})\}$ . These approximations are obtained by proving corresponding results on the multicommodity flow-cut gap. In contrast to these results some special cases of Multicut, such as the well-studied Multiway Cut problem, admit a constant factor approximation in both undirected and directed graphs. Motivated by both concrete instances from applications and abstract considerations, we consider the role that the structure of the demand graph $H$ plays in determining the approximability of Multicut. In undirected graphs our main result is a $2$ -approximation in $n^{O(t)}$ time when the demand graph $H$ excludes an induced matching of size $t$ . This gives a constant factor approximation for a specific demand graph that motivated this work. In contrast to undirected graphs, we prove that in directed graphs such approximation algorithms can not exist. Assuming the Unique Games Conjecture (UGC), for a large class of fixed demand graphs DMulC cannot be approximated to a factor better than worst-case flow-cut gap. As a consequence we prove that for any fixed $k$ , assuming UGC, DMulC with $k$ demand pairs is hard to approximate to within a factor better than $k$ . On the positive side, we prove an approximation of $k$ when the demand graph excludes certain graphs as an induced subgraph. This generalizes the Multiway Cut result to a much larger class of demand graphs.

preprint2016arXiv

On the Expansion of Group-Based Lifts

A $k$ -lift of an $n$ -vertex base graph $G$ is a graph $H$ on $n\times k$ vertices, where each vertex $v$ of $G$ is replaced by $k$ vertices $v_1,\cdots{},v_k$ and each edge $(u,v)$ in $G$ is replaced by a matching representing a bijection $π_{uv}$ so that the edges of $H$ are of the form $(u_i,v_{π_{uv}(i)})$ . Lifts have been studied as a means to efficiently construct expanders. In this work, we study lifts obtained from groups and group actions. We derive the spectrum of such lifts via the representation theory principles of the underlying group. Our main results are: (1) There is a constant $c_1$ such that for every $k\geq 2^{c_1nd}$ , there does not exist an abelian $k$ -lift $H$ of any $n$ -vertex $d$ -regular base graph with $H$ being almost Ramanujan (nontrivial eigenvalues of the adjacency matrix at most $O(\sqrt{d})$ in magnitude). This can be viewed as an analogue of the well-known no-expansion result for abelian Cayley graphs. (2) A uniform random lift in a cyclic group of order $k$ of any $n$ -vertex $d$ -regular base graph $G$ , with the nontrivial eigenvalues of the adjacency matrix of $G$ bounded by $λ$ in magnitude, has the new nontrivial eigenvalues also bounded by $λ+O(\sqrt{d})$ in magnitude with probability $1-ke^{-Ω(n/d^2)}$ . In particular, there is a constant $c_2$ such that for every $k\leq 2^{c_2n/d^2}$ , there exists a lift $H$ of every Ramanujan graph in a cyclic group of order $k$ with $H$ being almost Ramanujan. We use this to design a quasi-polynomial time algorithm to construct almost Ramanujan expanders deterministically. The existence of expanding lifts in cyclic groups of order $k=2^{O(n/d^2)}$ can be viewed as a lower bound on the order $k_0$ of the largest abelian group that produces expanding lifts. Our results show that the lower bound matches the upper bound for $k_0$ (upto $d^3$ in the exponent).

preprint2015arXiv

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

In Directed Multiway Cut(Dir-MC) the input is an edge-weighted directed graph $G=(V,E)$ and a set of $k$ terminal nodes $\{s_1,s_2,\ldots,s_k\} \subseteq V$ ; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from $s_i$ to $s_j$ for any $i \neq j$ . In Node-weighted Multiway Cut(Node-MC) the input is a node-weighted undirected graph $G$ and a set of $k$ terminal nodes $\{s_1,s_2,\ldots,s_k\} \subseteq V$ ; the goal is to remove a min-weight subset of nodes to disconnect each pair of terminals. Dir-MC admits a $2$ -approximation [Naor, Zosin '97] and Node-MC admits a $2(1-\frac{1}{k})$ -approximation [Garg, Vazirani, Yannakakis '94], both via rounding of LP relaxations. Previous rounding algorithms for these problems, from nearly twenty years ago, are based on careful rounding of an "optimum" solution to an LP relaxation. This is particularly true for Dir-MC for which the rounding relies on a custom LP formulation instead of the natural distance based LP relaxation [Naor, Zosin '97]. In this paper we describe extremely simple and near linear-time rounding algorithms for Dir-MC and Node-MC via a natural distance based LP relaxation. The dual of this relaxation is a special case of the maximum multicommodity flow problem. Our algorithms achieve the same bounds as before but have the significant advantage in that they can work with "any feasible" solution to the relaxation. Consequently, in addition to obtaining "book" proofs of LP rounding for these two basic problems, we also obtain significantly faster approximation algorithms by taking advantage of known algorithms for computing near-optimal solutions for maximum multicommodity flow problems. We also investigate lower bounds for Dir-MC when $k=2$ and in particular prove that the integrality gap of the LP relaxation is $2$ even in directed planar graphs.

preprint2012arXiv

Preservation under Substructures modulo Bounded Cores

We investigate a model-theoretic property that generalizes the classical notion of "preservation under substructures". We call this property \emph{preservation under substructures modulo bounded cores}, and present a syntactic characterization via $Σ_2^0$ sentences for properties of arbitrary structures definable by FO sentences. As a sharper characterization, we further show that the count of existential quantifiers in the $Σ_2^0$ sentence equals the size of the smallest bounded core. We also present our results on the sharper characterization for special fragments of FO and also over special classes of structures. We present a (not FO-definable) class of finite structures for which the sharper characterization fails, but for which the classical Łoś-Tarski preservation theorem holds. As a fallout of our studies, we obtain combinatorial proofs of the Łoś-Tarski theorem for some of the aforementioned cases.

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.