No article text was recorded for this version.
worst-case complexity gap
Version 1 of 1299 papers364 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach
- Blog: AI's War on Manipulation: Are We Winning?
- Blog: Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Blog: Complexity of and Algorithms for Borda Manipulation
- Blog: On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
- Blog: An Empirical Study of Borda Manipulation
- Blog: Complexity of and Algorithms for Borda Manipulation
- Blog: Complexity of Manipulation, Bribery, and Campaign Management in Bucklin and Fallback Voting
- Blog: A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three Alternatives
- Blog: Solving Hard Control Problems in Voting Systems via Integer Programming
- Blog: Control Complexity in Bucklin and Fallback Voting
- Blog: The Power of Local Manipulation Strategies in Assignment Mechanisms
- Blog: Nonexistence of Voting Rules That Are Usually Hard to Manipulate
- Blog: Undecidable problems associated with variational quantum algorithms
- Blog: Comparing Multiagent Systems Research in Combinatorial Auctions and Voting
- Blog: Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
- Blog: An Integer Linear Programming Approach for Coalitional Weighted Manipulation under Scoring Rules
- Blog: Control Complexity in Bucklin and Fallback Voting
- Blog: Swap Bribery
- Blog: Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate
- Blog: Detecting communities is hard, and counting them is even harder
- Blog: Eliminating the Weakest Link: Making Manipulation Intractable?
- Blog: Manipulative Elicitation - A New Attack on Elections with Incomplete Preferences
- Blog: Ties Matter: Complexity of Manipulation when Tie-Breaking with a Random Vote
- Blog: A Richer Understanding of the Complexity of Election Systems
- Blog: The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Blog: Beyond the Worst Case: Semi-Random Complexity Analysis of Winner Determination
- Blog: Llull and Copeland Voting Broadly Resist Bribery and Control
- Blog: Control in Computational Social Choice
- Blog: A Smooth Transition from Powerlessness to Absolute Power
- Blog: Multi-Winner Elections: Complexity of Manipulation, Control and Winner-Determination
- Blog: The Price of Neutrality for the Ranked Pairs Method
- Blog: Realistic Assumptions for Attacks on Elections
- Blog: A Complexity-of-Strategic-Behavior Comparison between Schulze's Rule and Ranked Pairs
- Blog: Approximability of Manipulating Elections
- Blog: The shield that never was: Societies with single-peaked preferences are more open to manipulation and control
- Blog: Manipulation of Nanson's and Baldwin's Rules
- Blog: Super Strong ETH is False for Random k-SAT
- Blog: Computational Asymmetries in Robust Classification
- Blog: Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
- Blog: The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates
- Blog: Borda Count in Collective Decision Making: A Summary of Recent Results
- Blog: Bundling Attacks in Judgment Aggregation
- Blog: Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
- Blog: Solving hard control problems in voting systems via integer programming
- Blog: Reinstating Combinatorial Protections for Manipulation and Bribery in Single-Peaked and Nearly Single-Peaked Electorates
- Blog: Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard
- Blog: Border basis detection is NP-complete
- Blog: Complexity of Decentralized Control: Special Cases
- Blog: How many candidates are needed to make elections hard to manipulate?
- Blog: Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule
- Blog: On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI
- Blog: Smoothing the gap between NP and ER
- Blog: Computational Aspects of Multi-Winner Approval Voting
- Blog: Combinatorial Auctions with k-wise Dependent Valuations
- Blog: Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
- Blog: Strong NP-Hardness Result for Regularized $L_q$-Minimization Problems with Concave Penalty Functions
- Blog: Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations
- Blog: The Complexity of Online Manipulation of Sequential Elections
- Blog: Computational complexity in electronic structure
Showing 60 of 299 papers.
History & citation
Current · Permanent link
- The Gap Between Worst-Case Hardness and Practical Voting Security merged into this direction (84% overlap)
- The Practical Tractability of Theoretically Hard Problems merged into this direction (74% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_worst_case_complexity_gap_3b3ef542,
title = {worst-case complexity gap},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/worst-case-complexity-gap/rdr_3b3ef542f83c47eca9e1a86121a0adfe},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}This exact version (version 1, frozen text):
@misc{lacuna_worst_case_complexity_gap_3b3ef542_v1,
title = {worst-case complexity gap},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/worst-case-complexity-gap/rdr_3b3ef542f83c47eca9e1a86121a0adfe/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}