Deeparnab Chakrabarty
Affiliations: Dartmouth College, Hanover, NH, USA
According to our database^{1},
Deeparnab Chakrabarty
authored at least 95 papers
between 2005 and 2023.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:

on dl.acm.org
On csauthors.net:
Bibliography
2023
Math. Program., February, 2023
A d<sup>1/2+o(1)</sup> Monotonicity Tester for Boolean Functions on $d$Dimensional Hypergrids.
Electron. Colloquium Comput. Complex., 2023
CoRR, 2023
CoRR, 2023
CoRR, 2023
Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs.
CoRR, 2023
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
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.
Electron. Colloquium Comput. Complex., 2022
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022
Approximation Algorithms for Continuous Clustering and Facility Location Problems.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022
2021
Better and simpler error analysis of the SinkhornKnopp 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
CoRR, 2021
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
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
Proceedings of the 29th Annual European Symposium on Algorithms, 2021
2020
Theory Comput., 2020
ACM Trans. Algorithms, 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 ACMSIAM 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
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 TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Interpolating between kMedian and kCenter: Approximation Algorithms for Ordered kMedian.
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, OneSided 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
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: LPBased Techniques for MinimumLatency Problems.
Math. Oper. Res., 2016
J. Comput. Biol., 2016
Electron. Colloquium Comput. Complex., 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 TwentySixth Annual ACMSIAM 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
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
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
Electron. Colloquium Comput. Complex., 2012
Algorithmica, 2012
Proceedings of the Automata, Languages, and Programming  39th International Colloquium, 2012
2011
New geometryinspired 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 EisenbergGale 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
EisenbergGale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.
Electron. Colloquium Comput. Complex., 2006
New Results on Rationality and Strongly Polynomial Time Solvability in EisenbergGale Markets.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006
2005
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC2005), 2005