More Like this

1. Search versus Search for Collapsing Electoral Control Types

   Carleton, Benjamin; Chavrimootoo, Michael C; Hemaspaandra, Lane A; Narvaez, David; Taliancich, Conor; Welles, Henry B (June 2025, Proceedings of the 21st European Conference on Multi-Agent Systems, Springer Nature)

   A 2024 paper of Carleton et al. [11] building on Hemaspaandra et al. [25] surprisingly shows, for 36 pairs of cases involving plurality, veto, and approval voting, that seemingly different, long-studied partition-based control attack types “collapse”: they are the same set (and so have the same decision complexity). The rather novel open question the 2024 paper concludes with is whether, for the 36 collapsing decision-problem pairs, their search-complexities are linked. In this paper, we completely resolve that question. We build a framework for linking the search complexities and solutions of members of collapsing pairs, and we both link and pinpoint the search complexities of all 36 collapsing cases (in part via linking the search complexities within the 7 “universal” collapsing pairs). This is important because for election problems the search versions are by far the more important versions: they tell one how to perform the desired attack. 

   more » « less
2. Separations and Collapses in Computational Social Choice and Complexity Theory

   Chavrimootoo, Michael C (May 2024, ProQuest)

   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 (separate) 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. The particular too we study 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 (thus giving another type of “collapse”) 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 that game. 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. 

   more » « less
3. A Comparison of Tree Search Method for Graph Topology Design Problems

   Short, Ada-Rhodes; DuPont, B.; Campbell, M.I. (July 2018, International Conference on Design Computing And Cognition (DCC'18 or DCC18))

   In this paper, we discuss the relevance and effectiveness of two com-mon methods for searching decision trees that represent design problems. When design problems are encoded in decision trees they are of-ten multimodal, capture a range of complexity in valid solutions, and have distinguishable internal locations. We propose the use of a simple Color Graph problem to represent these characteristics. The two methods evaluated are a genetic algorithm and a Monte Carlo tree search. Using the Color Graph problem, it is demonstrated that a genetic algorithm can perform exceptionally well on such unbounded and opaque design decision trees and that Monte Carlo tree searches are ineffective. Insights from this experiment are used to draw conclusions about the nature of design problems stored in decision trees and the need for new methods to search such trees and lead us to believe that exploitative methods are more effective than rigorously explorative methods. 

   more » « less
4. Separating and Collapsing Electoral Control Types

   Carleton, C.; Chavrimootoo, M.; Hemaspaandra, Lane A.; Narvaez, D.; Taliancich, C.; Welles, H. (May 2023, Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems)

   Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates [3]. Hemaspaandra et al. [16] discovered, for seven pairs (T , T ′ ) of seemingly distinct standard electoral control types, that T and T ′ are identical: For each input 𝐼 and each election system E, 𝐼 is a “yes” instance of both T and T ′ under E, or of neither. Surprisingly, this had gone undetected even as the field was score-carding how many standard control types election systems were resistant to; various “different” cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that other pairs of control types are also identical, and so work still is being needlessly duplicated. We determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. We show that no identical control pairs exist beyond the known seven. For three central election systems, we determine which control pairs are identical (“collapse”) with respect to those particular systems, and we explore containment/incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra et al.’s [16] seven collapses still hold. But we find 14 additional collapses that hold for approval voting but not for some election systems whose votes are linear orderings. We find one additional collapse for veto and none for plurality. We prove that each of the three election sys- tems mentioned have no collapses other than those inherited from Hemaspaandra et al. [16] or added here. But we show many new containment relationships that hold between some separating con- trol pairs, and for each separating pair of standard control types classify its separation in terms of containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these three important election systems, clarifies the landscape of the 44 standard control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations. 

   more » « less
5. On the Pseudo-Deterministic Query Complexity of NP Search Problems

   https://doi.org/10.4230/LIPIcs.CCC.2021.36  

   Goldwasser, Shafi and (August 2021, Leibniz international proceedings in informatics)

   Kabanets, Valentine (Ed.)

   We study pseudo-deterministic query complexity - randomized query algorithms that are required to output the same answer with high probability on all inputs. We prove Ω(√n) lower bounds on the pseudo-deterministic complexity of a large family of search problems based on unsatisfiable random CNF instances, and also for the promise problem (FIND1) of finding a 1 in a vector populated with at least half one’s. This gives an exponential separation between randomized query complexity and pseudo-deterministic complexity, which is tight in the quantum setting. As applications we partially solve a related combinatorial coloring problem, and we separate random tree-like Resolution from its pseudo-deterministic version. In contrast to our lower bound, we show, surprisingly, that in the zero-error, average case setting, the three notions (deterministic, randomized, pseudo-deterministic) collapse. 

   more » « less