Search for: All records

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. 

We interviewed four undergraduate biology instructors who reformed their curriculum to include queer gender and intersex inclusive strategies. We found that instructors focused on changing language, often removing sexed or gendered language, and used a variety of inclusive activities in their undergraduate biology classroom. 

Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs (T, T′) of seemingly distinct standard electoral control types, that T and T′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various 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 perhaps other pairs of control types are identical, and so work still is being needlessly duplicated.We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either 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. 

Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that Few P ⊆ ⊕P). In this article, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed “nongappiness”) of the easy-to-find “targets” used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra–Pomerance–Wagstaff Conjecture implies that all\((\mathcal {O}(1) + \log \log n)\)-ambiguity NP sets are in the restricted counting class RC_PRIMES. 

Metal nanocrystals (NCs) with different structural features are produced by seeded-electrodeposition. 

Single nanopores in silicon nitride membranes are asymmetrically modified with Nafion and investigated with scanning ion conductance microscopy, where Nafion alters local ion concentrations at the nanopore. Effects of applied transmembrane potentials on local ion concentrations are examined, with the Nafion film providing a reservoir of cations in close proximity to the nanopore. Fluidic diodes based on ion concentration polarization are observed in the current-voltage response of the nanopore and in approach curves of SICM nanopipette in the vicinity of the nanopore. Experimental results are supported with finite element method simulations that detail ion depletion and enrichment of the nanopore/Nafion/nanopipette environment. 

It has been a tremendous treat being the SIGACT News Complexity Theory Column editor for these past thirty years. I thought about what to say here, and realized it is pretty simple: Thank you. 

Juris Hartmanis was so preternaturally wise and brilliant that in time people may find it hard to believe that someone so extraordinary existed in this world. Yet as I write this, three months to the day after Juris passed away, it still seems impossible that such a force of nature can no longer be part of this world.