Sandip Sinha

According to our database, Sandip Sinha authored at least 9 papers between 2019 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Approximate Trace Reconstruction from a Single Trace.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

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

2022

Efficient recovery algorithms with restricted access to strings

Sandip Sinha

PhD thesis, 2022

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

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

Estimating the Longest Increasing Subsequence in Nearly Optimal Time.

Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Polynomial-time trace reconstruction in the smoothed complexity model.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

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

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2019

Local decodability of the Burrows-Wheeler transform.

Sandip Sinha, Omri Weinstein

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

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel.

Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha

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

Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.

Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha

Proceedings of the Approximation, 2019