# Deeparnab Chakrabarty

According to our database

Collaborative distances:

^{1}, Deeparnab Chakrabarty authored at least 78 papers between 2005 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2020

CoRR, 2020

Algorithmica, 2020

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

ACM Trans. Algorithms, 2019

CoRR, 2019

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

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

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

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

2018

SIAM J. Comput., 2018

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

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

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

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

Encyclopedia of Algorithms, 2016

Encyclopedia of Algorithms, 2016

Theory Comput., 2016

SIAM J. Comput., 2016

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

Math. Oper. Res., 2016

J. Comput. Biol., 2016

Electronic Colloquium on Computational Complexity (ECCC), 2016

CoRR, 2016

CoRR, 2016

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

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

2015

SIAM J. Discret. Math., 2015

Algorithmica, 2015

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

2014

Theory Comput., 2014

SIAM J. Discret. Math., 2014

CoRR, 2014

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

SIAM J. Discret. Math., 2013

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

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

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

Electronic Colloquium on Computational Complexity (ECCC), 2012

Algorithmica, 2012

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

Algorithmica, 2011

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

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

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

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

Discret. Math., 2010

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

CoRR, 2010

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

Oper. Res. Lett., 2009

CoRR, 2009

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

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

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

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

2008

PhD thesis, 2008

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

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

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