# Deeparnab Chakrabarty

According to our database1, Deeparnab Chakrabarty authored at least 116 papers between 2005 and 2019.

Collaborative distances:
• Dijkstra number2 of three.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2019
Generalized Center Problems with Outliers.
ACM Trans. Algorithms, 2019

Simpler and Better Algorithms for Minimum-Norm Load Balancing.
CoRR, 2019

Fair Algorithms for Clustering.
CoRR, 2019

Approximation algorithms for minimum norm and ordered optimization problems.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Adaptive Boolean Monotonicity Testing in Total Influence Time.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Simpler and Better Algorithms for Minimum-Norm Load Balancing.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018
SIAM J. Comput., 2018

Adaptive Boolean Monotonicity Testing in Total Influence Time.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Approximation Algorithms for Minimum Norm and Ordered Optimization Problems.
CoRR, 2018

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

Generalized Center Problems with Outliers.
CoRR, 2018

Adaptive Boolean Monotonicity Testing in Total Influence Time.
CoRR, 2018

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling.
CoRR, 2018

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dynamic Algorithms for Graph Coloring.
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.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Generalized Center Problems with Outliers.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties.
ACM Trans. Algorithms, 2017

A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d.
Electronic Colloquium on Computational Complexity (ECCC), 2017

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.
Electronic Colloquium on Computational Complexity (ECCC), 2017

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

Dynamic Algorithms for Graph Coloring.
CoRR, 2017

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

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube.
CoRR, 2017

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

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

The Heterogeneous Capacitated k-Center Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Monotonicity Testing.
Encyclopedia of Algorithms, 2016

Max-Min Allocation.
Encyclopedia of Algorithms, 2016

Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword.
Theory of Computing, 2016

An o(n) Monotonicity Tester for Boolean Functions over the Hypercube.
SIAM J. Comput., 2016

Facility Location with Client Latencies: LP-Based Techniques for Minimum-Latency Problems.
Math. Oper. Res., 2016

Detecting Character Dependencies in Stochastic Models of Evolution.
Journal of Computational Biology, 2016

A Õ(n) Non-Adaptive Tester for Unateness.
Electronic Colloquium on Computational Complexity (ECCC), 2016

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

Graph Balancing with Two Edge Types.
CoRR, 2016

CoRR, 2016

The Heterogeneous Capacitated $k$-Center Problem.
CoRR, 2016

The Non-Uniform k-Center Problem.
CoRR, 2016

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

IQ-Hopping: distributed oblivious channel selection for wireless networks.
Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2016

The Non-Uniform k-Center Problem.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Recognizing Coverage Functions.
SIAM J. Discrete Math., 2015

CoRR, 2015

Approximability of Capacitated Network Design.
Algorithmica, 2015

On (1, )-Restricted Assignment Makespan Minimization.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
An Optimal Lower Bound for Monotonicity Testing over Hypergrids.
Theory of Computing, 2014

Submodularity Helps in Nash and Nonsymmetric Bargaining Games.
SIAM J. Discrete Math., 2014

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties.
Electronic Colloquium on Computational Complexity (ECCC), 2014

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

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

Provable Submodular Minimization using Wolfe's Algorithm.
CoRR, 2014

Provable Submodular Minimization using Wolfe's Algorithm.
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.
Proceedings of the Innovations in Theoretical Computer Science, 2014

2013
Hypergraphic LP Relaxations for Steiner Trees.
SIAM J. Discrete Math., 2013

An optimal lower bound for monotonicity testing over hypergrids.
Electronic Colloquium on Computational Complexity (ECCC), 2013

A o(n) monotonicity tester for Boolean functions over the hypercube.
Electronic Colloquium on Computational Complexity (ECCC), 2013

An optimal lower bound for monotonicity testing over hypergrids
CoRR, 2013

A o(n) monotonicity tester for Boolean functions over the hypercube
CoRR, 2013

Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences.
CoRR, 2013

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids.
Proceedings of the Symposium on Theory of Computing Conference, 2013

A o(n) monotonicity tester for boolean functions over the hypercube.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Budget smoothing for internet ad auctions: a game theoretic approach.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

An Optimal Lower Bound for Monotonicity Testing over Hypergrids.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Capacitated Network Design on Undirected Graphs.
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.
SIGACT News, 2012

Optimal bounds for monotonicity and Lipschitz testing over the hypercube.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing Coverage Functions
CoRR, 2012

Optimal bounds for monotonicity and Lipschitz testing over the hypercube
CoRR, 2012

Approximability of the Firefighter Problem - Computing Cuts over Time.
Algorithmica, 2012

Testing Coverage Functions.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem.
Math. Program., 2011

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

Social Welfare in One-sided Matching Markets without Money
CoRR, 2011

Approximability of Sparse Integer Programs.
Algorithmica, 2011

Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Approximability of Capacitated Network Design.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Social Welfare in One-Sided Matching Markets without Money.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Design is as Easy as Optimization.
SIAM J. Discrete Math., 2010

Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents.
SIAM J. Discrete Math., 2010

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.
SIAM J. Comput., 2010

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound.
Oper. Res. Lett., 2010

G-parking functions, acyclic orientations and spanning trees.
Discrete Mathematics, 2010

Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
CoRR, 2010

Approximability of Capacitated Network Design
CoRR, 2010

Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems
CoRR, 2010

Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound
CoRR, 2010

On Column-restricted and Priority Covering Integer Programs
CoRR, 2010

Hypergraphic LP Relaxations for Steiner Trees.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010

On Column-Restricted and Priority Covering Integer Programs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009
On competitiveness in uniform utility allocation markets.
Oper. Res. Lett., 2009

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

Hypergraphic LP Relaxations for Steiner Trees
CoRR, 2009

On Allocating Goods to Maximize Fairness
CoRR, 2009

Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Algorithms for Message Ferrying on Mobile ad hoc Networks.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

On Allocating Goods to Maximize Fairness.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
Algorithmic aspects of connectivity, allocation and design problems.
PhD thesis, 2008

Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Efficiency, Fairness and Competitiveness in Nash Bargaining Games.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

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

On Competitiveness in Uniform Utility Allocation Markets.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

2006
Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.
Electronic Colloquium on Computational Complexity (ECCC), 2006

New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Design Is as Easy as Optimization.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
Fairness and optimality in congestion games.
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005