I am a PhD student in the Department of Computer Science at the Louisiana State University, supervised by Dr. Rahul Shah. My interest lies in Data Structures and Algorithms for Pattern Matching, with an emphasis on designing Succinct Data Structures for Pattern Matching and its Variants. This is an active research area in Theoretical Computer Science, where the focus lies on designing data structures occupying space close to the information theoretic minimal space (ignoring lower order terms), yet matching query time of linear-space data-structures with only negligible (typically poly-log factors) slowdown.
Currently, I am working on a project aimed at designing succinct data structures for a class of pattern matching problems for which although suffix tree based solutions exist, but no succinct/compact space data structures are known. Typical examples include parameterized and order-isomorphic pattern matching. I am hopeful that a larger question that will be answered from this project is whether there are problems which are intrinsically hard to compress, i.e., they are suffix tree solvable, but not succinct/compact solvable.
Recently, I have also taken an interest in the streaming model of computation, mostly for many unaddressed, yet important variants, of the classical pattern matching problem.
Before coming to LSU, I obtained my bachelors degree in Computer Science from Jadavpur University, Kolkata, India in 2009. My CV and DBLP can be found here: [CV] and [dblp]. Please feel free to write to me at agangu4 AT lsu DOT edu for collaborations, discussions, or simply to have a chat!
Below are my publications, including pdf copies of the papers for interested readers.
- Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching, and Related Problems. 28th ACM-SIAM Symposium on Discreet Algorithms (SODA) Barcelona, Spain, January 16-19, 2017 [pdf] [arxiv] [slides]
- Arnab Ganguly, Wing-Kai Hon, and Rahul Shah: Stabbing Colors in One Dimension. Data Compression Conference (DCC) Snowbird, Utah, USA, April 4-7, 2017 [pdf]
- Arnab Ganguly, Wing-Kai Hon, and Rahul Shah: A Framework for Dynamic Parameterized Dictionary Matching. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) Reykjavik, Iceland, June 22-24, 2016 [pdf]
- Arnab Ganguly, Wing-Kai Hon, Kunihiko Sadakane, Rahul Shah, Sharma V. Thankachan, and Yilin Yang: Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching. 27th Annual Symposium on Combinatorial Pattern Matching (CPM) Tel Aviv, Israel, June 27-29, 2016 [pdf]
- Arnab Ganguly, Wing-Kai Hon, Rahul Shah, and Sharma V. Thankachan: Space-Time Trade-offs for the Shortest Unique Substring Problem. 27th International Symposium on Algorithms and Computation (ISAAC) Sydney, Australia, December 12-14, 2016 [pdf]
- Sudip Biswas, Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: Ranked Document Retrieval with Forbidden Pattern. 26th Annual Symposium on Combinatorial Pattern Matching (CPM) Ischia Island, Italy, June 29-July 1, 2015 [pdf]
- Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: Succinct Non-overlapping Indexing. 26th Annual Symposium on Combinatorial Pattern Matching (CPM) Ischia Island, Italy, June 29-July 1, 2015 [pdf]
- Sudip Biswas, Arnab Ganguly, and Rahul Shah: Restricted Shortest Path in Temporal Graphs. 26th International Conference on Database and Expert Systems Applications (DEXA) Valencia, Spain, September 1-4, 2015 [pdf]
- Sudip Biswas, Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: Forbidden Extension Queries. 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) Indian Institute of Science, Bangalore, India, December 16-18, 2015 [pdf]
- Sukhamay Kundu and Arnab Ganguly: A Formal Model of Use-Cases and Its Application in Generating A Hierarchical Class-Structure. 9th International Conference on Software Engineering Advances (ICSEA) Nice, France, October 12-16, 2014 [pdf]