Deeparnab Chakrabarty

Affiliations:
  • Dartmouth College, Hanover, NH, USA


According to our database1, Deeparnab Chakrabarty authored at least 87 papers between 2005 and 2022.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
Improved Lower Bounds for Submodular Function Minimization.
CoRR, 2022

Approximation Algorithms for Continuous Clustering and Facility Location Problems.
CoRR, 2022

2021
Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling.
Math. Program., 2021

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

Better Algorithms for Individually Fair k-Clustering.
CoRR, 2021

Better Algorithms for Individually Fair <i>k</i>-Clustering.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Robust k-Center with Two Types of Radii.
Proceedings of the Integer Programming and Combinatorial Optimization, 2021

Revisiting Priority k-Center: Fairness and Outliers.
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.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Graph Connectivity and Single Element Recovery via Linear and OR Queries.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.
Theory Comput., 2020

The Non-Uniform <i>k</i>-Center Problem.
ACM Trans. Algorithms, 2020

Deterministic Dynamic Matching in O(1) Update Time.
Algorithmica, 2020

On a Decentralized (Δ+1)-Graph Coloring Algorithm.
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.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Generalized Center Problems with Outliers.
ACM Trans. Algorithms, 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

Fair Algorithms for Clustering.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Faster Matroid Intersection.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

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

2018
Online Buy-at-Bulk Network Design.
SIAM J. Comput., 2018

Adaptive Boolean Monotonicity Testing in Total Influence Time.
Electron. Colloquium Comput. Complex., 2018

Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids.
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>]<sup><i>d</i></sup>.
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

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]<sup>d</sup>.
Electron. Colloquium Comput. Complex., 2017

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

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

Subquadratic submodular function minimization.
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

2016
Monotonicity Testing.
Encyclopedia of Algorithms, 2016

Max-Min Allocation.
Encyclopedia of Algorithms, 2016

Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword.
Theory Comput., 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.
J. Comput. Biol., 2016

A Õ(n) Non-Adaptive Tester for Unateness.
Electron. Colloquium Comput. Complex., 2016

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

Graph Balancing with Two Edge Types.
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. Discret. Math., 2015

Approximability of Capacitated Network Design.
Algorithmica, 2015

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

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

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

On $(1, ε)$-Restricted Assignment Makespan Minimization.
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. Discret. Math., 2013

A o(n) monotonicity tester for Boolean functions over the hypercube.
Electron. Colloquium Comput. Complex., 2013

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids.
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

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.
Electron. Colloquium Comput. Complex., 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

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

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. Discret. Math., 2010

Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents.
SIAM J. Discret. 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.
Discret. Math., 2010

Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
CoRR, 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

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 17th International Conference on World Wide Web, 2008

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

2007
Public Advertisement Broker Markets.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

2006
Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.
Electron. Colloquium Comput. Complex., 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

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


  Loading...