An official website of the United States government
Hemaspaandra et al. [6] and Carleton et al. [3, 4] found that many pairs of electoral (decision) problems about the same election sys- tem coincide as sets (i.e., they are collapsing pairs), which had pre- viously gone undetected in the literature. While both members of a collapsing pair certainly have the same decision complexity, there is no guarantee that the associated search problems also have the same complexity. For practical purposes, search problems are more relevant than decision problems. Our work focuses on exploring the relationships between the search versions of collapsing pairs. We do so by giving a framework that relates the complexity of search problems via efficient reduc- tions that transform a solution from one problem to a solution of the other problem on the same input. We not only establish that the known decision collapses carry over to the search model, but also refine our results by determining for the concrete systems plurality, veto, and approval whether collapsing search-problem pairs are polynomial-time computable or NP-hard.
more »
« less
This content will become publicly available on June 20, 2026
Search versus Search for Collapsing Electoral Control Types
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
- PAR ID:
- 10643635
- Publisher / Repository:
- Proceedings of the 21st European Conference on Multi-Agent Systems, Springer Nature
- Date Published:
- ISSN:
- 978-3-031-93930-3
- ISBN:
- 978-3-031-93929-7
- Page Range / eLocation ID:
- 217-236
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
In this work, we present the first database reconstruction attacks against response-hiding private range search schemes on encrypted databases of arbitrary dimensions. Falzon et al. (VLDB 2022) present a number of range-supporting schemes on arbitrary dimensions exhibiting different security and efficiency trade-offs. Additionally, they characterize a form of leakage, structure pattern leakage, also present in many one-dimensional schemes e.g., Demertzis et al. (SIGMOD 2016) and Faber et al. (ESORICS 2015). We present the first systematic study of this leakage and attack a broad collection of schemes, including schemes that allow the responses to contain false-positives (often considered the gold standard in security). We characterize the information theoretic limitations of a passive persistent adversary. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.more » « less
-
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
-
Abstract Unconscious neural activity has been shown to precede both motor and cognitive acts. In the present study, we investigated the neural antecedents of overt attention during visual search, where subjects make voluntary saccadic eye movements to search a cluttered stimulus array for a target item. Building on studies of both overt self-generated motor actions (Lau et al., 2004, Soon et al., 2008) and self-generated cognitive actions (Bengson et al., 2014, Soon et al., 2013), we hypothesized that brain activity prior to the onset of a search array would predict the direction of the first saccade during unguided visual search. Because both spatial attention and gaze are coordinated during visual search, both cognition and motor actions are coupled during visual search. A well-established finding in fMRI studies of willed action is that neural antecedents of the intention to make a motor act (e.g., reaching) can be identified seconds before the action occurs. Studies of the volitional control ofcovertspatial attention in EEG have shown that predictive brain activity is limited to only a few hundred milliseconds before a voluntary shift of covert spatial attention. In the present study, the visual search task and stimuli were designed so that subjects could not predict the onset of the search array. Perceptual task difficulty was high, such that they could not locate the target using covert attention alone, thus requiring overt shifts of attention (saccades) to carry out the visual search. If the first saccade to the array onset in unguided visual search shares mechanisms with willed shifts of covert attention, we expected predictive EEG alpha-band activity (8-12 Hz) immediately prior to the array onset (within 1 sec) (Bengson et al., 2014; Nadra et al., 2023). Alternatively, if they follow the principles of willed motor actions, predictive neural signals should be reflected in broadband EEG activity (Libet et al., 1983) and would likely emerge earlier (Soon et al., 2008). Applying support vector machine decoding, we found that the direction of the first saccade in an unguided visual search could be predicted up to two seconds preceding the search array’s onset in the broadband but not alpha-band EEG. These findings suggest that self-directed eye movements in visual search emerge from early preparatory neural activity more akin to willed motor actions than to covert willed attention. This highlights a distinct role for unconscious neural dynamics in shaping visual search behavior.more » « less
