250 Hutchison Rd, Rochester, NY 14620

Separations and Collapses in Computational Social Choice and Complexity Theory

 

This thesis studies separations and collapses in new ways, in both computational social choice and computational complexity theory.

Since the seminal work of Bartholdi et al. (1989a,b, 1992) and Bartholdi and Orlin (1991) in computational social choice, the tools and techniques of theoretical computer science have been used to discover the complexities of a range of attacks on different election systems. That line of work has broadly assumed that the seemingly different attacks were in fact different. A key contribution of this thesis will be to explore, in the widely-studied electoral attack domain known as electoral control, the extent to which that assumption is correct. In particular, Hemaspaandra et al. (2020) showed that there were several electoral control problems that, although they had been studied separately for years, are in fact one and the same (when viewed as decision problems). This showed that researchers had for years been doing redundant work. We continue this line of work and uncover additional surprising relationships among electoral control types, thus discovering additional cases where duplicate effort has occurred, and helping the field avoid further duplicate work.

Building on this, for control types that collapse in the literature's standard notion of collapse---equality of their decision problems---this thesis studies whether the search complexities of the collapsing types also collapse (i.e., coincide). We find they do for all known collapsing types, and for all new collapsing types discovered in this thesis. We indeed go beyond that by showing that one often can efficiently build search solutions for one type from the search solutions of the other type on the same input, and we provide a framework to study those search-complexity relationships.

In computational complexity theory, we study which pairs of ambiguity-bounded versions of NP stand (collapse) or fall together: one collapses to P exactly if the other does too. Prior to our work, the only known family of such connections was due to Watanabe (1988), and we present here new collections of such families.

Finally, in the area of the complexity of single-player games, we generalize a tool used to study reversible deterministic games to work for deterministic games with irreversible gravity. In some sense, this provides a "collapse" between the tools used to study two seemingly different categories of games. One such existing tool in the study of reversible games is the Nondeterministic Constraint Logic problem, which typically allows one to show PSPACE-hardness by constructing only two gadgets, but is unfortunately not directly applicable to the study of games with irreversible gravity. We devise a new method that when applied directly uses 32 gadgets, but we show that many of those gadgets are effectively equivalent and that we can simulate all 32 gadgets by using only three gadgets. We apply this method to the study of the Hanano Puzzle and find that only two gadgets are needed to show the PSPACE-hardness of the Hanano Puzzle.

Looking at the bigger picture, this thesis looks in new ways at collapses and separations in computational social choice and computational complexity theory, making progress using a variety of tools ranging from proving theorems to providing new human and computer-discovered separations. Overall, we paint a clearer picture in computational social choice of what collapses and separations occur, and in computational complexity of what collapses stand or fall together.

 

Advisor: Prof. Lane A. Hemaspaandra (Computer Science)  

Committee: Prof. Lenhart Schubert (Computer Science), Prof. Anson Kahng (Computer Science),

Prof. Edith Hemaspaandra (Computer Science, RIT), Prof. Jörg Rothe (Computer Science, HHU- Düsseldorf)

Chair: Prof. Saul Lubkin (Mathematics)   

Event Details


Zoom ID:  https://rochester.zoom.us/j/91653179766?pwd=MlZuN2gzMnNGRkZ1MmdLN0hKdE9kQT09

Meeting ID: 916 5317 9766
Password: 527149

User Activity

No recent activity