Speaker:  Pramod Ganapathi and Samuel McCauley

Title: The Range 1 Query (R1Q) Problem

Abstract: We define the "range 1 query" (R1Q) problem as follows. 
Given a d-dimensional (d >= 1) input bit matrix A, preprocess A 
so that for any given region R of A, one can efficiently answer 
queries asking if R contains a 1 or not. We consider both orthogonal 
and non-orthogonal shapes for R including rectangles, axis-parallel 
right-triangles, certain types of polygons, and spheres. We provide 
space-efficient deterministic and randomized algorithms with constant 
query times (in constant dimensions) for solving the problem in the 
word RAM model. The space usage in bits is  sublinear, linear, or 
near linear in the size of A, depending on the algorithm. The R1Q 
problem for both orthogonal and non-orthogonal ranges arises during 
the generation of optimized kernels in the Pochoir stencil compiler.

This is joint work with Michael Bender, Rezaul Chowdhury and Yuan Tang.