Deeparnab Chakrabarty
Affiliations:- Dartmouth College, Hanover, NH, USA
According to our database1,
Deeparnab Chakrabarty
authored at least 95 papers
between 2005 and 2024.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on dl.acm.org
On csauthors.net:
Bibliography
2024
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024
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
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 Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 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
Proceedings of the 30th Annual European Symposium on Algorithms, 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
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
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
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
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
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
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
SIAM J. Comput., 2016
Facility Location with Client Latencies: LP-Based Techniques for Minimum-Latency Problems.
Math. Oper. Res., 2016
J. Comput. Biol., 2016
Electron. Colloquium Comput. Complex., 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
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
2014
Theory Comput., 2014
SIAM J. Discret. Math., 2014
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014
Proceedings of the Innovations in Theoretical Computer Science, 2014
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 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
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
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
CoRR, 2010
Proceedings of the Integer Programming and Combinatorial Optimization, 2010
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.
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
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005