First Advisor

Shravas Rao

Date of Award

6-2025

Document Type

Thesis

Degree Name

Bachelor of Science (B.S.) in Computer Science and University Honors

Department

Computer Science

Language

English

Subjects

Hamming Nearest Neighbor, Computational Theory, Probabilistic Polynomial, Hamming Distance, subquadratic

DOI

10.15760/honors.1701

Abstract

This paper is an exposition of the paper Probabilistic Polynomials and Hamming Nearest Neighbors by Josh Alman and Ryan Williams. It presents the findings of this paper in a more accessible format for Computer Science students earlier in their career who may not be as familiar with Computational Theory and its concepts as their PhD counterparts are. The paper assumes that the reader has a basic understanding of Algorithms and Complexity, typically obtained in an introductory level Algorithms course.

The paper by Alman and Williams analyzes a specific problem known as the Hamming Nearest Neighbor problem. All known solutions for this problem had a runtime of n2 or greater prior to this paper. Alman and Williams derive a subquadratic time algorithm for a variation of this problem known as the Batch Hamming Nearest Neighbor (BHNN) problem. The authors use various Lemmas and Theorems (some new, some old) in order to achieve the subquadratic time algorithm. This is done using a probabilistic polynomial combined with known mathematical concepts. Then, once the subquadratic time algorithm is achieved, the authors show how it can be applied to the problems of computing pairs with maximum inner product, finding the closest pair in ℓ1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients. This exposition will go over each part of the original paper. The critical parts of this paper such as theorems and lemmas will be listed followed by explanations and examples to provide further context and understanding.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Persistent Identifier

https://archives.pdx.edu/ds/psu/43806

Download

Share

COinS