Diptarka Chakraborty

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 49

Top Topics

Pattern Matching

Single Source Shortest Path

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Equivalence Testing: The Power of Bounded Adaptivity. CoRR (2024)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Equivalence Testing: The Power of Bounded Adaptivity. AISTATS (2024)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model. SODA (2024)
Diptarka Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Support Size Estimation: The Power of Conditioning. MFCS (2023)
Alvin Yan Hong Yao, Diptarka Chakraborty
Approximate Maximum Rank Aggregation: Beyond the Worst-Case. FSTTCS (2023)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model. CoRR (2023)
Diptarka Chakraborty, Sanjana Dey
Matrix Completion: Approximating the Minimum Diameter. ISAAC (2023)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Clustering Permutations: New Techniques with Streaming Applications. ITCS (2023)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle? ICALP (2023)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle? CoRR (2023)
Diptarka Chakraborty, Syamantak Das, Arindam Khan, Aditya Subramanian
Fair Rank Aggregation. CoRR (2023)
Diptarka Chakraborty, Syamantak Das, Arindam Khan, Aditya Subramanian
Fair Rank Aggregation. NeurIPS (2022)
Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary
Pairwise Reachability Oracles and Preservers Under Failures. ICALP (2022)
Diptarka Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Support Size Estimation: The Power of Conditioning. CoRR (2022)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Clustering Permutations: New Techniques with Streaming Applications. CoRR (2022)
Diptarka Chakraborty, Kshitij Gajjar, Agastya Vibhuti Jha
Approximating the Center Ranking Under Ulam. FSTTCS (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximate Trace Reconstruction via Median String (In Average-Case). FSTTCS (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximating the Median under the Ulam Metric. SODA (2021)
Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary
Pairwise Reachability Oracles and Preservers under Failures. CoRR (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximate Trace Reconstruction via Median String (in Average-Case). CoRR (2021)
Diptarka Chakraborty, Keerti Choudhary
New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures. ICALP (2020)
Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar
Hardness of Approximation of (Multi-)LCS over Small Alphabet. CoRR (2020)
Diptarka Chakraborty, Keerti Choudhary
New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures. CoRR (2020)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximating the Median under the Ulam Metric. CoRR (2020)
Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar
Hardness of Approximation of (Multi-)LCS over Small Alphabet. APPROX-RANDOM (2020)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. J. ACM 67 (6) (2020)
Diptarka Chakraborty, Debarati Das, Michal Koucký
Approximate Online Pattern Matching in Sublinear Time. FSTTCS (2019)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS (2018)
Diptarka Chakraborty, Debarati Das
Sparse Weight Tolerant Subgraph for Single Source Shortest Path. SWAT (2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký
Approximate Online Pattern Matching in Sub-linear Time. CoRR (2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. ESA (2018)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR (2018)
Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
Tight cell probe bounds for succinct Boolean matrix-vector multiplication. STOC (2018)
Diptarka Chakraborty, Raghunath Tewari
) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs. ACM Trans. Comput. Theory 9 (4) (2018)
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Dimension, pseudorandomness and extraction of pseudorandomness. Comput. 6 (3) (2017)
Diptarka Chakraborty, Satyadev Nandakumar, Himanshu Shukla
On Resource-Bounded Versions of the van Lambalgen Theorem. TAMC (2017)
Diptarka Chakraborty, Satyadev Nandakumar, Himanshu Shukla
On Resource-bounded versions of the van Lambalgen theorem. CoRR (2017)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Optimal Quasi-Gray Codes: Does the Alphabet Matter? CoRR (2017)
Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication. CoRR (2017)
Diptarka Chakraborty, Debarati Das
Near Optimal Sized Weight Tolerant Subgraph for Single Source Shortest Path. CoRR (2017)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Streaming algorithms for embedding and computing edit distance in the low distance regime. STOC (2016)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees. CoRR (2016)
Diptarka Chakraborty, Raghunath Tewari
) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs. Electron. Colloquium Comput. Complex. 22 (2015)
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Dimension, Pseudorandomness and Extraction of Pseudorandomness. FSTTCS (2015)
Diptarka Chakraborty, Raghunath Tewari
An O(n^ε ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs. ISAAC (2015)
Diptarka Chakraborty, Raghunath Tewari
Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs. WALCOM (2015)
Diptarka Chakraborty, Raghunath Tewari
An $O(n^ε)$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs. CoRR (2015)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Low Distortion Embedding from Edit to Hamming Distance using Coupling. Electron. Colloquium Comput. Complex. 22 (2015)
Diptarka Chakraborty, Raghunath Tewari
Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs. CoRR (2015)
Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. Variyam Vinodchandran, Lin F. Yang
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. Electron. Colloquium Comput. Complex. 21 (2014)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Information Complexity for Multiparty Communication. Electron. Colloquium Comput. Complex. 21 (2014)
Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin F. Yang
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. FSTTCS (2014)
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness. Electron. Colloquium Comput. Complex. 21 (2014)