research
∙
07/07/2022
Search versus Search for Collapsing Electoral Control Types
Electoral control types are ways of trying to change the outcome of elec...
share
research
∙
07/02/2022
Separating and Collapsing Electoral Control Types
[HHM20] discovered, for 7 pairs (C,D) of seemingly distinct standard ele...
research
∙
09/29/2021
Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ...
research
∙
07/22/2019
The Complexity of Online Bribery in Sequential Elections (Extended Abstract)
Prior work on the complexity of bribery assumes that the bribery happens...
research
∙
06/19/2019
The Complexity of Online Bribery in Sequential Elections
Prior work on the complexity of bribery assumes that the bribery happens...
research
∙
02/21/2019
The Power of Self-Reducibility: Selectivity, Information, and Approximation
This chapter provides a hands-on tutorial on the important technique kno...
research
∙
07/28/2018
Team Diagonalization
Ten years ago, Glaßer, Pavan, Selman, and Zhang [GPSZ08] proved that if ...
research
∙
11/03/2017
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
We show that the counting class LWPP [FFK94] remains unchanged even if o...
research
∙
11/01/2017
Credimus
We believe that economic design and computational complexity---while alr...
research
∙
10/30/2017
Computational Social Choice and Computational Complexity: BFFs?
We discuss the connection between computational social choice (comsoc) a...
research
∙
06/14/2017
The Opacity of Backbones and Backdoors Under a Weak Assumption
Backdoors and backbones of Boolean formulas are hidden structural proper...
research
∙
06/11/2016
The Opacity of Backbones
A backbone of a boolean formula F is a collection S of its variables for...
research
∙
10/30/2012
An Atypical Survey of Typical-Case Heuristic Algorithms
Heuristic approaches often do so well that they seem to pretty much alwa...
research
∙
01/21/2000
Take-home Complexity
We discuss the use of projects in first-year graduate complexity theory ...
research
∙
11/01/1998