Linear decision lists are a computational model for Boolean functions. A linear decision list is built from a sequence of linear threshold function queries which are evaluated one by one: if a query returns true, the list outputs the value of the function, and if the answer is false, the process continues to the next query. The size of a linear decision list is the number of queries in it. Linear decision lists form a natural and nontrivial subclass of depth-2 threshold circuits, the class of circuits that currently marks the frontier of explicit circuit lower bounds. Although some techniques for proving lower bounds against linear decision lists exist, they are quite limited, leaving important open problems unresolved. Moreover, for the related model of exact linear decision lists, no strong lower bounds are known. We initiate the study of alternation depth of decision lists with linear threshold queries. The alternation depth is defined as the number of alternations in the sequence of output values of the decision list. We show that linear decision lists, both with bounded and unbounded weights in the threshold queries, form fine hierarchies with respect to alternation depth. A similar hierarchy exists for rectangle decision lists, the model closely related to communication complexity with NP oracles. We prove strong separations within these hierarchies and between them. Next, we give a superpolynomial lower bound for an explicit function for exact linear decision lists of depth below n/log n. Such lower bounds were not previously known and do not follow directly from existing methods. We also establish a fine depth hierarchy for exact linear decision lists. To prove these hierarchy separations, we use an iterative technique combined with existing techniques such as fooling sets and the analysis of blocky matrices. For the lower bound on exact linear decision lists, we combine the discrepancy method with an iterative analysis of blocky matrices.

We study the public-coin randomized communication complexity of the equality function. The communication complexity of this function is known to be low when the error probability is constant and the players have access to many random bits. The complexity grows, however, if the allowed error probability and the amount of randomness are restricted. We show that public-coin randomized protocols for equality and error-correcting codes are essentially the same object. That is, given a protocol for equality, we can construct a code, and vice versa. We substantially extend the protocol-implies-code direction: any protocol computing a function with a large fooling set can be converted into an error-correcting code. As a corollary, we show that among functions with a fooling set of size s, equality on log s bits has the least randomized communication complexity, regardless of the restrictions on the error probability and the amount of randomness. Finally, we use the connection to error-correcting codes to analyze the randomized communication complexity of equality for varying restrictions on the error probability and the amount of randomness. In most cases, we provide tight bounds. We pinpoint the setting in which tight bounds are still unknown.

The Big Data explosion has necessitated the development of search algorithms that scale sub-linearly in time and memory. While compression algorithms and search algorithms do exist independently, few algorithms offer both, and those which do are domain-specific. We present panCAKES, a novel approach to compressive search, i.e., a way to perform k-NN and ρ-NN search on compressed data while only decompressing a small, relevant, portion of the data. panCAKES assumes the manifold hypothesis and leverages the low-dimensional structure of the data to compress and search it efficiently. panCAKES is generic over any distance function for which the distance between two points is proportional to the memory cost of storing an encoding of one in terms of the other. This property holds for many widely-used distance functions, e.g. string edit distances (Levenshtein, Needleman-Wunsch, etc.) and set dissimilarity measures (Jaccard, Dice, etc.). We benchmark panCAKES on a variety of datasets, including genomic, proteomic, and set data. We compare compression ratios to gzip, and search performance between the compressed and uncompressed versions of the same dataset. panCAKES achieves compression ratios close to those of gzip, while offering sub-linear time performance for k-NN and ρ-NN search. We conclude that panCAKES is an efficient, general-purpose algorithm for exact compressive search on large datasets that obey the manifold hypothesis. We provide an open-source implementation of panCAKES in the Rust programming language.