Deeparnab Chakrabarty

According to our database, Deeparnab Chakrabarty authored at least 98 papers between 2005 and 2024.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2024

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing.

Deeparnab Chakrabarty, C. Seshadhri

CoRR, 2024

Fault-tolerant k-Supplier with Outliers.

Deeparnab Chakrabarty, Luc Côté, Ankita Sarkar

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Learning Partitions Using Rank Queries.

Deeparnab Chakrabarty, Hang Liao

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries.

Hang Liao, Deeparnab Chakrabarty

Proceedings of the International Conference on Algorithmic Learning Theory, 2024

2023

Robust k-center with two types of radii.

Deeparnab Chakrabarty, Maryam Negahbani

Math. Program., February, 2023

A d^1/2+o(1) Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2023

A Primal-Dual Analysis of Monotone Submodular Maximization.

Deeparnab Chakrabarty, Luc Côté

CoRR, 2023

Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs.

Hang Liao, Deeparnab Chakrabarty

CoRR, 2023

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Parallel Submodular Function Minimization.

Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs.

Deeparnab Chakrabarty, Hang Liao

Proceedings of the International Conference on Algorithmic Learning Theory, 2023

2022

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2022

Improved Lower Bounds for Submodular Function Minimization.

Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Approximation Algorithms for Continuous Clustering and Facility Location Problems.

Deeparnab Chakrabarty, Maryam Negahbani, Ankita Sarkar

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling.

Deeparnab Chakrabarty, Sanjeev Khanna

Math. Program., 2021

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection.

Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna

CoRR, 2021

Better Algorithms for Individually Fair k-Clustering.

Deeparnab Chakrabarty, Maryam Negahbani

CoRR, 2021

Better Algorithms for Individually Fair <i>k</i>-Clustering.

Maryam Negahbani, Deeparnab Chakrabarty

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Revisiting Priority k-Center: Fairness and Outliers.

Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, Maryam Negahbani

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization.

Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Graph Connectivity and Single Element Recovery via Linear and OR Queries.

Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

The Non-Uniform <i>k</i>-Center Problem.

Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy

ACM Trans. Algorithms, 2020

Deterministic Dynamic Matching in O(1) Update Time.

Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger

Algorithmica, 2020

On a Decentralized (Δ+1)-Graph Coloring Algorithm.

Deeparnab Chakrabarty, Paul de Supinski

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Domain Reduction for Monotonicity Testing: A <i>o</i>(<i>d</i>) Tester for Boolean Functions in <i>d</i>-Dimensions.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Generalized Center Problems with Outliers.

Deeparnab Chakrabarty, Maryam Negahbani

ACM Trans. Algorithms, 2019

Fair Algorithms for Clustering.

Suman K. Bera, Deeparnab Chakrabarty, Maryam Negahbani

CoRR, 2019

Approximation algorithms for minimum norm and ordered optimization problems.

Deeparnab Chakrabarty, Chaitanya Swamy

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fair Algorithms for Clustering.

Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, Maryam Negahbani

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Faster Matroid Intersection.

Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Simpler and Better Algorithms for Minimum-Norm Load Balancing.

Deeparnab Chakrabarty, Chaitanya Swamy

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Online Buy-at-Bulk Network Design.

Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi

SIAM J. Comput., 2018

Adaptive Boolean Monotonicity Testing in Total Influence Time.

Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2018

Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2018

A <i>o</i>(<i>d</i>) · polylog <i>n</i> Monotonicity Tester for Boolean Functions over the Hypergrid [<i>n</i>]^<i>d</i>.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dynamic Algorithms for Graph Coloring.

Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median.

Deeparnab Chakrabarty, Chaitanya Swamy

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2017

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, Sofya Raskhodnikova, C. Seshadhri

Electron. Colloquium Comput. Complex., 2017

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

Electron. Colloquium Comput. Complex., 2017

A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d.

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

CoRR, 2017

Subquadratic submodular function minimization.

Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Heterogeneous Capacitated k-Center Problem.

Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Amit Kumar

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.

Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

2016

Monotonicity Testing.

Deeparnab Chakrabarty

Encyclopedia of Algorithms, 2016

Max-Min Allocation.

Deeparnab Chakrabarty

Encyclopedia of Algorithms, 2016

Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword.

Deeparnab Chakrabarty, David J. Galvin

Theory Comput., 2016

An o(n) Monotonicity Tester for Boolean Functions over the Hypercube.

Deeparnab Chakrabarty, C. Seshadhri

SIAM J. Comput., 2016

Facility Location with Client Latencies: LP-Based Techniques for Minimum-Latency Problems.

Deeparnab Chakrabarty, Chaitanya Swamy

Math. Oper. Res., 2016

Detecting Character Dependencies in Stochastic Models of Evolution.

Deeparnab Chakrabarty, Sampath Kannan, Kevin Tian

J. Comput. Biol., 2016

A Õ(n) Non-Adaptive Tester for Unateness.

Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2016

A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness.

Deeparnab Chakrabarty, C. Seshadhri

CoRR, 2016

Graph Balancing with Two Edge Types.

Deeparnab Chakrabarty, Kirankumar Shiragur

CoRR, 2016

IQ-Hopping: distributed oblivious channel selection for wireless networks.

Apurv Bhartia, Deeparnab Chakrabarty, Krishna Chintalapudi, Lili Qiu, Bozidar Radunovic, Ramachandran Ramjee

Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2016

The Non-Uniform k-Center Problem.

Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Recognizing Coverage Functions.

Deeparnab Chakrabarty, Zhiyi Huang

SIAM J. Discret. Math., 2015

Approximability of Capacitated Network Design.

Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula

Algorithmica, 2015

On (1, <i>∊</i>)-Restricted Assignment Makespan Minimization.

Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Submodularity Helps in Nash and Nonsymmetric Bargaining Games.

Deeparnab Chakrabarty, Gagan Goel, Vijay V. Vazirani, Lei Wang, Changyuan Yu

SIAM J. Discret. Math., 2014

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties.

Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri

Electron. Colloquium Comput. Complex., 2014

On $(1, ε)$-Restricted Assignment Makespan Minimization.

Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li

CoRR, 2014

Provable Submodular Minimization using Wolfe's Algorithm.

Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Welfare maximization and truthfulness in mechanism design with ordinal preferences.

Deeparnab Chakrabarty, Chaitanya Swamy

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Hypergraphic LP Relaxations for Steiner Trees.

Deeparnab Chakrabarty, Jochen Könemann, David Pritchard

SIAM J. Discret. Math., 2013

An optimal lower bound for monotonicity testing over hypergrids.

Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2013

A o(n) monotonicity tester for Boolean functions over the hypercube.

Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2013

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids.

Deeparnab Chakrabarty, C. Seshadhri

Proceedings of the Symposium on Theory of Computing Conference, 2013

Budget smoothing for internet ad auctions: a game theoretic approach.

Denis Xavier Charles, Deeparnab Chakrabarty, Max Chickering, Nikhil R. Devanur, Lei Wang

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Capacitated Network Design on Undirected Graphs.

Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li, Srivatsan Narayanan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Review of design of approximation algorithms, by David P. Williamson and David B. Shmoys.

Deeparnab Chakrabarty

SIGACT News, 2012

Optimal bounds for monotonicity and Lipschitz testing over the hypercube.

Deeparnab Chakrabarty, C. Seshadhri

Electron. Colloquium Comput. Complex., 2012

Approximability of the Firefighter Problem - Computing Cuts over Time.

Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, Chaitanya Swamy

Algorithmica, 2012

Testing Coverage Functions.

Deeparnab Chakrabarty, Zhiyi Huang

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

New geometry-inspired relaxations and algorithms for the metric Steiner tree problem.

Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani

Math. Program., 2011

Variance on the Leaves of a Tree Markov Random Field: Detecting Character Dependencies in Phylogenies

Deeparnab Chakrabarty, Sampath Kannan

CoRR, 2011

Approximability of Sparse Integer Programs.

David Pritchard, Deeparnab Chakrabarty

Algorithmica, 2011

Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems.

Deeparnab Chakrabarty, Chaitanya Swamy

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Social Welfare in One-Sided Matching Markets without Money.

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs.

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Design is as Easy as Optimization.

Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani

SIAM J. Discret. Math., 2010

Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents.

Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani

SIAM J. Discret. Math., 2010

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.

Deeparnab Chakrabarty, Gagan Goel

SIAM J. Comput., 2010

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound.

Deeparnab Chakrabarty, Jochen Könemann, David Pritchard

Oper. Res. Lett., 2010

G-parking functions, acyclic orientations and spanning trees.

Brian Benson, Deeparnab Chakrabarty, Prasad Tetali

Discret. Math., 2010

Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna

CoRR, 2010

On Column-Restricted and Priority Covering Integer Programs.

Deeparnab Chakrabarty, Elyot Grant, Jochen Könemann

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

On competitiveness in uniform utility allocation markets.

Deeparnab Chakrabarty, Nikhil R. Devanur

Oper. Res. Lett., 2009

The Effect of Malice on the Social Optimum in Linear Load Balancing Games

Deeparnab Chakrabarty, Chinmay Karande, Ashish Sangwan

CoRR, 2009

Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity.

Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, Chaitanya Swamy

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Algorithms for Message Ferrying on Mobile ad hoc Networks.

Mostafa H. Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram, Richard J. Lipton

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

On Allocating Goods to Maximize Fairness.

Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Algorithmic aspects of connectivity, allocation and design problems.

Deeparnab Chakrabarty

PhD thesis, 2008

Budget constrained bidding in keyword auctions and online knapsack problems.

Yunhong Zhou, Deeparnab Chakrabarty, Rajan M. Lukose

Proceedings of the 17th International Conference on World Wide Web, 2008

Efficiency, Fairness and Competitiveness in Nash Bargaining Games.

Deeparnab Chakrabarty, Gagan Goel, Vijay V. Vazirani, Lei Wang, Changyuan Yu

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

2007

Public Advertisement Broker Markets.

Atish Das Sarma, Deeparnab Chakrabarty, Sreenivas Gollapudi

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

2006

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.

Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani

Electron. Colloquium Comput. Complex., 2006

New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets.

Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

2005

Fairness and optimality in congestion games.

Deeparnab Chakrabarty, Aranyak Mehta, Viswanath Nagarajan

Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005