Deeparnab Chakrabarty

According to our database1, Deeparnab Chakrabarty authored at least 78 papers between 2005 and 2020.

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

Book
In proceedings
Article
PhD thesis
Other

Bibliography

2020
Graph Connectivity and Single Element Recovery via Linear and OR Queries.
CoRR, 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
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

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 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>.
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

A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid [n]<sup>d</sup>.
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

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.
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

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.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 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
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

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