Date of Degree

9-2018

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Amotz Bar-Noy

Committee Members

Theodore Brown

Matthew Johnson

Stathis Zachos

Subject Categories

Software Engineering | Theory and Algorithms

Abstract

Counting plays a fundamental role in many scientific fields including chemistry, physics, mathematics, and computer science. There are two approaches for counting, the first relies on analytical tools to drive closed form expression, while the second takes advantage of the combinatorial nature of the problem to construct an algorithm whose output is the number of structures. There are many algorithmic techniques for counting, they cover the explicit approach of counting by listing to the approximate approach of counting by sampling.

This thesis looks at counting three sets of objects. First, we consider a subclass of boolean functions that are monotone. They appear naturally in great variety of contexts including combinatorics, cryptography, voting theory, and game theory. Next, we consider permutations of n pairs of numbers, called Skolem sequences. These sequences are employed in several areas including construction of Steiner triple systems, binary sequences with controllable complexity, interference resistant codes, and graph labeling. Finally, we consider a variation of the n-queens problem, called the queens of the night. This constraint satisfaction problem is not just a recreational puzzle, but rather it is useful in designing conflict free access in parallel systems. In each case we verify previously known values and provide the next unknown exact value(s) in the counting sequence. Furthermore, we approximate the count for the next unknown values in the sequence by employing a sampling procedure.

This work is embargoed and will be available for download on Wednesday, September 30, 2020

Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.

Non-GC Users:
See the GC’s lending policies to learn more.

Share

COinS