Diptarka Chakraborty

According to our database, Diptarka Chakraborty authored at least 35 papers between 2014 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Equivalence Testing: The Power of Bounded Adaptivity.

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel

CoRR, 2024

Tight Lower Bound on Equivalence Testing in Conditional Sampling Model.

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Support Size Estimation: The Power of Conditioning.

Diptarka Chakraborty, Gunjan Kumar, Kuldeep S. Meel

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Matrix Completion: Approximating the Minimum Diameter.

Diptarka Chakraborty, Sanjana Dey

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Clustering Permutations: New Techniques with Streaming Applications.

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle?

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Approximate Maximum Rank Aggregation: Beyond the Worst-Case.

Alvin Yan Hong Yao, Diptarka Chakraborty

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

Fair Rank Aggregation.

Diptarka Chakraborty, Syamantak Das, Arindam Khan, Aditya Subramanian

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Pairwise Reachability Oracles and Preservers Under Failures.

Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Approximating the Median under the Ulam Metric.

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Approximating the Center Ranking Under Ulam.

Diptarka Chakraborty, Kshitij Gajjar, Agastya Vibhuti Jha

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Approximate Trace Reconstruction via Median String (In Average-Case).

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks

J. ACM, 2020

New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures.

Diptarka Chakraborty, Keerti Choudhary

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Hardness of Approximation of (Multi-)LCS over Small Alphabet.

Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar

Proceedings of the Approximation, 2020

2019

Approximate Online Pattern Matching in Sublinear Time.

Diptarka Chakraborty, Debarati Das, Michal Koucký

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

An <i>O</i>(<i>n</i>^ε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs.

Diptarka Chakraborty, Raghunath Tewari

ACM Trans. Comput. Theory, 2018

Approximate Online Pattern Matching in Sub-linear Time.

Diptarka Chakraborty, Debarati Das, Michal Koucký

CoRR, 2018

Sparse Weight Tolerant Subgraph for Single Source Shortest Path.

Diptarka Chakraborty, Debarati Das

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Tight cell probe bounds for succinct Boolean matrix-vector multiplication.

Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.

Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Optimal Quasi-Gray Codes: Does the Alphabet Matter?

Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

CoRR, 2017

Near Optimal Sized Weight Tolerant Subgraph for Single Source Shortest Path.

Diptarka Chakraborty, Debarati Das

CoRR, 2017

Dimension, pseudorandomness and extraction of pseudorandomness.

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Comput., 2017

On Resource-Bounded Versions of the van Lambalgen Theorem.

Diptarka Chakraborty, Satyadev Nandakumar, Himanshu Shukla

Proceedings of the Theory and Applications of Models of Computation, 2017

2016

Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

CoRR, 2016

Streaming algorithms for embedding and computing edit distance in the low distance regime.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

An O(n^ε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs.

Diptarka Chakraborty, Raghunath Tewari

Electron. Colloquium Comput. Complex., 2015

Low Distortion Embedding from Edit to Hamming Distance using Coupling.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

Electron. Colloquium Comput. Complex., 2015

Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs.

Diptarka Chakraborty, Raghunath Tewari

CoRR, 2015

Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs.

Diptarka Chakraborty, Raghunath Tewari

Proceedings of the WALCOM: Algorithms and Computation - 9th International Workshop, 2015

An O(n^ε ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs.

Diptarka Chakraborty, Raghunath Tewari

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

2014

New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.

Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. Variyam Vinodchandran, Lin F. Yang

Electron. Colloquium Comput. Complex., 2014

Information Complexity for Multiparty Communication.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

Electron. Colloquium Comput. Complex., 2014

Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness.

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Electron. Colloquium Comput. Complex., 2014