Publications

My papers are given here for teaching and research purposes only. The publications must not be distributed for profit or commercial advantage.
In mathematics and theoretical computer science, we follow the convention of listing authors in alphabetical order of their last names.

Dissertation

Automatic Discovery of Efficient Recursive Divide-and-Conquer Algorithms for Dynamic Programming Problems
  • Ph.D. Thesis, Department of Computer Science, Stony Brook University, New York, USA, 2016
  • Advisor: Rezaul Chowdhury
  • We design several algorithms/frameworks that can automatically/semi-automatically discover efficient and portable algorithms for solving a wide class of dynamic programming problems. We show that computers can discover non-trivial algorithms.
  • [Read thesis]

Patents

Balancing the Loads of Servers in a Server Farm Based on an Angle Between Two Vectors
  • United States Patent US 8,645,545 B2 and US 8,676,983 B2, 2014
  • Pramod Ganapathi and Darshan S. Palasamudram
  • We design a server load balancing algorithm that can load balance a large number of client connections onto servers having different client-serving capacities. The algorithm makes use of the simple concept of finding the angle between two vectors.
  • [Read patent application 1] [Read patent application 2]

Journal Papers

Autogen: Automatic Discovery of Efficient Recursive Divide-and-Conquer Algorithms for Solving Dynamic Programming Problems
  • ACM Transactions on Parallel Computing (TOPC). 4(1):4. 2017
  • Special Issue for Top Papers from PPoPP 2016
  • Rezaul Chowdhury, Pramod Ganapathi, Jesmin Jahan Tithi, Stephen Tschudi, Charles Bachmeier, Bradley Kuszmaul, Charles E. Leiserson, Armando Solar-Lezama, and Yuan Tang
  • We discover an algorithm called Deductive Autogen that uses integer linear programming to automatically discover efficient and portable algorithms for a wide class of dynamic programming problems. The deductive Autogen algorithm is much more powerful than the Autogen algorithm.
  • [Link] [Read paper]
The Range 1 Query (R1Q) Problem
  • Theoretical Computer Science (TCS). 2016
  • Special Issue for Top Papers from COCOON 2014
  • Michael A. Bender, Rezaul Chowdhury, Pramod Ganapathi, Samuel McCauley, and Yuan Tang
  • We design a recursive divide-and-conquer algorithm to answer the orthogonal range 1 query (R1Q) problem. An orthogonal R1Q problem is defined as follows. Given a bit matrix consisting of 0s and 1s, can we preprocess the matrix such that given any orthogonal query range inside the bit matrix, we should be able to answer if there exists any set bit (or 1) inside the query range, in constant query time and linear space (in the number of bits)?
  • [Link] [Read paper]

Conference / Workshop Papers

Provably Efficient Scheduling of Cache-Oblivious Wavefront Algorithms
  • Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 2017. pp. 339-350. Washington DC. USA.
  • Rezaul Chowdhury, Pramod Ganapathi, Yuan Tang, and Jesmin Jahan Tithi
  • We design an algorithmic framework that can be used to semi-automatically discover recursive divide-and-conquer wavefront algorithms for dynamic programming problems. This project is the sequel of Autogen. The algorithms discovered by Autogen is fed as the input to this framework to output (with human assistance) divide-and-conquer wavefront algorithms with improved parallelism.
  • [Link] [Read paper]
Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic Programs
  • Proceedings of the 20th Symposium on Principles and Practice of Parallel Programming (PPoPP). 2016. 51(8). article 10. Barcelona. Spain.
  • Rezaul Chowdhury, Pramod Ganapathi, Jesmin Jahan Tithi, Charles Bachmeier, Bradley Kuszmaul, Charles E. Leiserson, Armando Solar-Lezama, and Yuan Tang
  • We discover an algorithm called Autogen to automatically discover efficient and portable algorithms for a wide class of dynamic programming problems. Autogen is the first algorithm to automatically discover nontrivial divide-and-conquer algorithms.
  • [Link] [Read paper]
An Efficient Cache-Oblivious Parallel Viterbi Algorithm
  • Proceedings of the 22nd International European Conference on Parallel and Distributed Computing (Euro-Par). 2016. LNCS 9833. pp. 574-587. Grenoble. France.
  • Rezaul Chowdhury, Pramod Ganapathi, Vivek Pradhan, Jesmin Jahan Tithi, and Yunpeng Xiao
  • We design the first efficient and portable algorithm for the complicated Viterbi problem.
  • [Link] [Read paper]
The I/O Complexity of Computing Prime Tables
  • Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN). 2016. LNCS 9644. pp. 192-206. Ensenada. Mexico.
  • Michael A. Bender, Rezaul Chowdhury, Alex Conway, Martin Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon, and Shikha Singh
  • We design several algorithms to compute prime tables (primes up till a given number) in the external-memory model i.e., when the computed primes do not fit in RAM.
  • [Link] [Read paper]
Cache-Oblivious Wavefront: Improving Parallelism of Recursive Dynamic Programming Algorithms Without Losing Cache-Efficiency
  • Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 2015. pp. 205-214. San Francisco. USA.
  • Yuan Tang, Ronghui You, Haibin Kan, Jesmin Jahan Tithi, Pramod Ganapathi, and Rezaul Chowdhury
  • We develop a method of designing highly parallel recursive divide-and-conquer algorithms that fill a dynamic programming table in a wavefront fashion.
  • [Link] [Read paper]
High-Performance Energy-Efficient Recursive Dynamic Programming with MM-Like Flexible Kernels
  • Proceedings of the 29th IEEE International Parallel and Distributed Processing Symposium (IPDPS). 2015. pp. 303-312. Hyderabad. India.
  • Jesmin Jahan Tithi, Pramod Ganapathi, Aakrati Talati, Sonal Aggarwal, and Rezaul Chowdhury
  • We show that recursive divide-and-conquer dynamic programming (DP) algorithms that have matrix-multiplication-like kernels execute very fast in practice and beat the state-of-the-art implementations of DP. The recursive algorithms are also more energy efficient than the state-of-the-art implementations.
  • [Link] [Read paper]
The Range 1 Query (R1Q) Problem
  • Proceedings of the 20th International Computing and Combinatorics Conference (COCOON). 2014. pp. 116-128. Atlanta. USA.
  • Michael A. Bender, Rezaul Chowdhury, Pramod Ganapathi, Samuel McCauley, and Yuan Tang
  • We discover algorithms and data structures to answer the range 1 query (R1Q) problem. An R1Q problem is defined as follows. Given a bit matrix consisting of 0s and 1s, can we preprocess the matrix such that given any specific query range inside the bit matrix, we should be able to answer if there exists at least one set bit (or 1) inside the query range, in constant query time and linear space (in the number of bits)? We give deterministic and probabilistic algorithms for answering the R1Q problem for rectangles, circles, triangles, and polygons.
  • [Link] [Read paper]
Improving Parallelism of Recursive Stencil Computations without Sacrificing Cache Performance
  • Proceedings of the SPLASH Workshop on Stencil Computations (WOSC). 2014. Portland. USA.
  • Yuan Tang, Ronghui You, Haibin Kan, Jesmin Jahan Tithi, Pramod Ganapathi, and Rezaul Chowdhury.
  • We show how we can use divide-and-conquer wavefront algorithms to improve the parallelism of stencil computations.
  • [Link] [Read paper]

Short Papers / Brief Announcements / Posters

Provably Efficient Scheduling of Cache-Oblivious Wavefront Algorithms
  • Proceedings of the 22nd SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 2017. Austin. USA.
  • Rezaul Chowdhury, Pramod Ganapathi, Yuan Tang, and Jesmin Jahan Tithi.
  • [Link]
Cache-Oblivious Wavefront Algorithms for Dynamic Programming Problems: Efficient Scheduling with Optimal Cache Performance and High Parallelism
  • Proceedings of the 29th High Performance Computing, Networking Storage and Analysis (SC). 2016. Salt Lake City. USA.
  • Jesmin Jahan Tithi, Pramod Ganapathi, Rezaul Chowdhury, and Yuan Tang.
  • [Link]
High-performance Recursive Dynamic Programming for Bioinformatics using MM-like Flexible Kernels
  • Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM BCB). 2014. pp. 600-601. Newport Beach, USA.
  • Jesmin Jahan Tithi, Pramod Ganapathi, Aakrati Talati, and Rezaul Chowdhury.
  • [Link]
The R1Q Problem
  • Proceedings of the 22nd Annual Fall Workshop on Computational Geometry (FWCG). 2012. University of Maryland. USA.
  • Rezaul Chowdhury, Pramod Ganapathi, and Yuan Tang.
  • [Link]

In Preparation

A Framework to Discover Combinatorial Algorithms
  • Rama Badrinath, Pramod Ganapathi, and Abhiram Natarajan
  • We design a combinatorial framework that uses backtracking design technique to discover several combinatorial algorithms. The combinatorial algorithms that can be generated by the framework includes permutations, combinations, subsets, Catalan numbers, partitions, compositions, gray codes, palindromes, derangements, solutions to Diophantine equations, sudoku, and the n-queens problem.
  • [Read paper]
A Framework to Discover Permutation Algorithms
  • Rezaul Chowdhury and Pramod Ganapathi
  • We design a framework using which we can generate 21 permutation generation algorithms. We also discover two permutation generation algorithms that uses sorting.
  • [Read paper]
Divide-and-Conquer Variants of Bubble, Selection, and Insertion Sorts
  • Rezaul Chowdhury and Pramod Ganapathi
  • We discover recursive divide-and-conquer variants of bubble sort, selection sort, and insertion sort algorithms.
  • [Read paper]

Older Publications

An Efficient and Preventive Method to Solve Broken Links Problem for Internal Links in Static Pages
  • ip.com, 2011
  • Pramod Ganapathi and Pradeep S. Bhat
  • We design an efficient and preventive method to solve the broken links problem for internal links in static web pages.
  • [Read paper]
A Face's Parent/Offspring Determination using Geometric Features and PCA
  • International Conference on Signal and Image Processing (ICSIP), 2009
  • C. N. Ravi Kumar, Anil Kumar, and Pramod Ganapathi
  • We design an algorithm that can be used to identify a parent or offspring of a person with good probability from a dataset of faces. The algorithm makes use of geometric features of the faces and the Principal Components Analysis technique.
  • [Read paper]