Publications (38)
An optimal lower bound for monotonicity testing over hypergrids
Deeparnab Chakrabarty, C. Seshadhri
Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences
Deeparnab Chakrabarty, Chaitanya Swamy
Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
Deeparnab Chakrabarty, C. Seshadhri
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2
Hypergraphic LP Relaxations for Steiner Trees
Deeparnab Chakrabarty, Jochen Koenemann, David Pritchard
Graph Balancing with Two Edge Types
Deeparnab Chakrabarty, Kirankumar Shiragur
A o(n) monotonicity tester for Boolean functions over the hypercube
Deeparnab Chakrabarty, C. Seshadhri
Testing Coverage Functions
Deeparnab Chakrabarty, Zhiyi Huang
Dynamic Algorithms for Graph Coloring
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger +1
The Non-Uniform k-Center Problem
Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy
Fair Algorithms for Clustering
Suman K. Bera, Deeparnab Chakrabarty, Nicolas J. Flores +1
Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound
Deeparnab Chakrabarty, Jochen Koenemann, David Pritchard
A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness
Deeparnab Chakrabarty, C. Seshadhri
Interpolating between $k$-Median and $k$-Center: Approximation Algorithms for Ordered $k$-Median
Deeparnab Chakrabarty, Chaitanya Swamy
A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n]^d$
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri
On $(1,ε)$-Restricted Assignment Makespan Minimization
Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
Simpler and Better Algorithms for Minimum-Norm Load Balancing
Deeparnab Chakrabarty, Chaitanya Swamy
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
Social Welfare in One-sided Matching Markets without Money
Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems
Deeparnab Chakrabarty, Chaitanya Swamy
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Deeparnab Chakrabarty, Chaitanya Swamy
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha +1
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2
The Heterogeneous Capacitated $k$-Center Problem
Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Amit Kumar
Online Buy-at-Bulk Network Design
Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy +1
Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling
Deeparnab Chakrabarty, Sanjeev Khanna
Subquadratic Submodular Function Minimization
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +1
Adaptive Boolean Monotonicity Testing in Total Influence Time
Deeparnab Chakrabarty, C. Seshadhri
On Column-restricted and Priority Covering Integer Programs
Deeparnab Chakrabarty, Elyot Grant, Jochen Koenemann
Approximability of Sparse Integer Programs
David Pritchard, Deeparnab Chakrabarty
Variance on the Leaves of a Tree Markov Random Field: Detecting Character Dependencies in Phylogenies
Deeparnab Chakrabarty, Sampath Kannan, Kevin Tian
Provable Submodular Minimization using Wolfe's Algorithm
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
Generalized Center Problems with Outliers
Deeparnab Chakrabarty, Maryam Negahbani
Approximability of Capacitated Network Design
Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna +1
The Effect of Malice on the Social Optimum in Linear Load Balancing Games
Deeparnab Chakrabarty, Chinmay Karande, Ashish Sangwan
On Allocating Goods to Maximize Fairness
Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna
$G$-Parking Functions, Acyclic Orientations and Spanning Trees
Brian Benson, Deeparnab Chakrabarty, Prasad Tetali