1 citations · 1 across the 13 of their papers we have counts for
15 papers
Linked Fates: How Small of an Ambiguity Increase Can Make the Difference Between Equaling and Separating from P?
Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra +3
Ambiguity-bounded versions of , denoted , bound by the number of accepting paths the nondeterministic polynomial-time Turing machine ca…
Axiomatic Tools for Separating Electoral Control Types, with Applications to Concrete Systems
Michael C. Chavrimootoo, Ian Clingerman, Ethan Ferland +5
Electoral control is the study of whether an attacker, by structural changes on an election such as adding/deleting/partitioning voters or candidates, can affect the winner in some…
The Cost of Failure: On The Complexity of Recampaigning under Fixed Districts
Michael C. Chavrimootoo, Aidan Jeansonne
Redistricting efforts have gathered contemporary attention in both popular and scholarly debates, particularly in the United States where efforts to redraw congressional districts…
Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
Michael C. Chavrimootoo, Jin Seok Youn
The Hanano Puzzle is a one-player game with gravity, where the goal is to make colored blocks make contact with flowers of the corresponding color. The game Jelly no Puzzle shares…
Approximating Electoral Control Problems
Huy Vu Bui, Michael C. Chavrimootoo, Kien T. Le +1
Much research in electoral control---one of the most studied form of electoral attacks, in which an entity running an election alters the structure of that election to yield a pref…
A Brief Note on a Recent Claim About NP-Hard Problems and BQP
Michael C. Chavrimootoo
This short note outlines some of the issues in Czerwinski's paper [Cze23] claiming that NP-hard problems are not in BQP. We outline one major issue and two minor issues, and conclu…
On Czerwinski's " relative to a -complete oracle"
Michael C. Chavrimootoo, Tran Duy Anh Le, Michael P. Reidy +1
In this paper, we take a closer look at Czerwinski's " relative to a -complete oracle" [Cze23]. There are (uncountably) infinitely-many relativized wo…
Evaluating the Claims of "SAT Requires Exhaustive Search"
Michael C. Chavrimootoo, Yumeng He, Matan Kotler-Berkowitz +2
In this paper, we take a closer look at the claims made by Xu and Zhou in their paper "SAT Requires Exhaustive Search" [XZ23], which claims to provide a lower bound on the complexi…
A Closer Look at Some Recent Proof Compression-Related Claims
Michael C. Chavrimootoo, Ethan Ferland, Erin Gibson +1
Gordeev and Haeusler [GH19] claim that each tautology of minimal propositional logic can be proved with a natural deduction of size polynomial in . This builds on work fro…
A Critique of Sopin's ""
Michael C. Chavrimootoo, Ian Clingerman, Quan Luu
We critique Valerii Sopin's paper "" [Sop14]. The paper claims to resolve one of the major open problems of theoretical computer science by leveraging the…
Search versus Search for Collapsing Electoral Control Types
Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra +3
Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [BTT92]. We say two compatible (i.e., having th…
Separating and Collapsing Electoral Control Types
Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra +3
[HHM20] discovered, for 7 pairs (C,D) of seemingly distinct standard electoral control types, that C and D are identical: For each input I and each election system, I is a Yes inst…
Defying Gravity: The Complexity of the Hanano Puzzle
Michael C. Chavrimootoo
Using the notion of visibility representations, our paper establishes a new property of instances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete problem…
A Critique of Kumar's "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications on P versus NP problem."
Michael C. Chavrimootoo, Henry B. Welles
In this paper, we analyze the argument made by Kumar in the technical report "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications…
A Critique of Keum-Bae Cho's Proof that
Benjamin Carleton, Michael C. Chavrimootoo, Conor Taliancich
In this paper we critique Keum-Bae Cho's proof that . This proof relates instances of 3-SAT to indistinguishable binomial decision trees and clai…