I am an Assistant Professor in the Department of Computer Science at University of Wisconsin - Whitewater.

I completed my PhD in 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 the order-isomorphic pattern matching problem.  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. 

Before coming to LSU, I obtained my undergraduate 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 gangulya AT uww DOT edu for collaborations, discussions, or simply to have a chat!

Below are my publications, including pdf copies of the papers for interested readers.

Conference Publications

2019

1. Arnab Ganguly, Ian Munro, Yakov Nekrich, Rahul Shah, and Sharma V. Thankachan. Categorical Range Reporting with Frequencies. 22nd International Conference on Database Theory (ICDT) in Lisbon, Portugal, March 26-29, 2019 [pdf]
2. Arnab Ganguly, Wing-Kai Hon, Yu-An Huang, Solon P. Pissis, Rahul Shah, and Sharma V. Thankachan. Parameterized Text Indexing with One Wildcard. Data Compression Conference (DCC) in Snowbird, Utah, USA, March 26-29, 2019
3. Arnab Ganguly, Daniel Gibney, Rahul Shah, and Sharma V. Thankachan. I/O Optimal Data Structures for Categorical Range Skyline Queries. 31st Canadian Conference in Computational Geometry (CCCG) in Alberta, Canada, August 8-10, 2019
4. Paniz Abedin, Arnab Ganguly, Solon P. Pissis, and Sharma V. Thankachan. Range Shortest Unique Substring Queries. 26th International Symposium on String Processing and Information Retrieval (SPIRE) in Segovia, Spain, October 7-9, 2019

2018

1. Paniz Abedin, Sahar Hooshmand, Arnab Ganguly, and Sharma V. Thankachan. The Heaviest Induced Ancestors Problem Revisited. 29th Annual Symposium on Combinatorial Pattern Matching (CPM) in Qingdao, China, July 2-4, 2018 [pdf]
2. Paniz Abedin, Arnab Ganguly, Wing-Kai Hon, Yakov Nekrich, Kunihiko Sadakane, Rahul Shah, and Sharma V. Thankachan. A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time. 24th International Computing and Combinatorics Conference (COCOON) in Qingdao, China, July 2-4, 2018 [pdf]

2017

1. 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) in Barcelona, Spain, January 16-19, 2017 [pdf] [slides]
2. Arnab Ganguly, Wing-Kai Hon, and Rahul Shah: Stabbing Colors in One Dimension. Data Compression Conference (DCC) in Snowbird, Utah, USA, April 4-7, 2017 [pdf]
3. Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: Structural Pattern Matching - Succinctly. 28th International Symposium on Algorithms and Computation (ISAAC) in Phuket, Thailand, December 9-12, 2017 [pdf]

2016

1. Arnab Ganguly, Wing-Kai Hon, and Rahul Shah: A Framework for Dynamic Parameterized Dictionary Matching. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) in Reykjavik, Iceland, June 22-24, 2016 [pdf]
2. 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) in Tel Aviv, Israel, June 27-29, 2016 [pdf]
3. 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) in Sydney, Australia, December 12-14, 2016 [pdf]

2015

1. 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) in Nice, France, October 12-16, 2014 [pdf]

Journal Publications

2019

1. Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: Succinct Non-overlapping Indexing. Algorithmica, August 2019

2018 

1. Sudip Biswas, Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: Ranked Document Retrieval for Multiple Patterns. Theoretical Computer Science, June 2018 [pdf]
2. Sudip Biswas, Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan: Space-efficient indexes for forbidden extension queries. Journal of Discrete Algorithms, October 2018 [pdf]
3. Arnab Ganguly, Manish Patil, Rahul Shah, and Sharma V. Thankachan: A Linear Space Data Structure for Range LCP Queries. Fundamenta Informaticae, November 2018 

2017

1. Arnab Ganguly, Wing-Kai Hon, Rahul Shah, and Sharma V. Thankachan: Space-time trade-offs for finding shortest unique substrings and maximal unique matches. Theoretical Computer Science, November 2017 [pdf]