pith. sign in

Lane A. Hemaspaandra

Identifiers

  • name variant Lane A. Hemaspaandra 0.60 · backfill

Papers (78)

  1. Linked Fates: How Small of an Ambiguity Increase Can Make the Difference Between Equaling and Separating from P? cs.CC · 2026 · author #3
  2. Axiomatic Tools for Separating Electoral Control Types, with Applications to Concrete Systems cs.GT · 2026 · author #5
  3. The Power of Self-Reducibility: Selectivity, Information, and Approximation cs.CC · 2019 · author #1
  4. Team Diagonalization cs.CC · 2018 · author #1
  5. The Robustness of LWPP and WPP, with an Application to Graph Reconstruction cs.CC · 2017 · author #2
  6. Credimus cs.CC · 2017 · author #2
  7. Computational Social Choice and Computational Complexity: BFFs? cs.MA · 2017 · author #1
  8. Existence versus Exploitation: The Opacity of Backbones and Backdoors Under a Weak Assumption cs.AI · 2017 · author #1
  9. Closure and Nonclosure Properties of the Compressible and Rankable Sets cs.LO · 2016 · author #2
  10. Recursion-Theoretic Ranking and Compression cs.LO · 2016 · author #1
  11. The Opacity of Backbones cs.AI · 2016 · author #1
  12. More Natural Models of Electoral Control by Partition cs.GT · 2014 · author #3
  13. Beautiful Structures: An Appreciation of the Contributions of Alan Selman cs.CC · 2014 · author #1
  14. A Control Dichotomy for Pure Scoring Rules cs.GT · 2014 · author #2
  15. The Complexity of Online Manipulation of Sequential Elections cs.GT · 2013 · author #2
  16. Control in the Presence of Manipulators: Cooperative and Competitive Cases cs.GT · 2013 · author #3
  17. Weighted Electoral Control cs.GT · 2013 · author #3
  18. X THEN X: Manipulation of Same-System Runoff Elections cs.GT · 2013 · author #3
  19. An Atypical Survey of Typical-Case Heuristic Algorithms cs.CC · 2012 · author #1
  20. Schulze and Ranked-Pairs Voting are Fixed-Parameter Tractable to Bribe, Manipulate, and Control cs.GT · 2012 · author #1
  21. The Complexity of Online Voter Control in Sequential Elections cs.GT · 2012 · author #2
  22. The Complexity of Online Manipulation of Sequential Elections cs.GT · 2012 · author #2
  23. The Complexity of Controlling Candidate-Sequential Elections cs.GT · 2012 · author #2
  24. Search versus Decision for Election Manipulation Problems cs.GT · 2012 · author #2
  25. Barbosa, Uniform Polynomial Time Bounds, and Promises cs.CC · 2011 · author #1
  26. The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates cs.GT · 2011 · author #3
  27. A Note on Nonuniform versus Uniform ACC^k Circuits for NE cs.CC · 2010 · author #1
  28. Multimode Control Attacks on Elections cs.GT · 2010 · author #3
  29. Llull and Copeland Voting Computationally Resist Bribery and Control cs.GT · 2008 · author #3
  30. Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas cs.CC · 2008 · author #2
  31. The Complexity of Power-Index Comparison cs.CC · 2008 · author #2
  32. Copeland Voting Fully Resists Constructive Control cs.GT · 2007 · author #3
  33. On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time cs.GT · 2007 · author #2
  34. A Richer Understanding of the Complexity of Election Systems cs.GT · 2006 · author #3
  35. How Hard Is Bribery in Elections? cs.GT · 2006 · author #3
  36. Hybrid Elections Broaden Complexity-Theoretic Resistance to Control cs.GT · 2006 · author #2
  37. The Consequences of Eliminating NP Solutions cs.CC · 2006 · author #2
  38. Query-Monotonic Turing Reductions cs.CC · 2006 · author #1
  39. Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners cs.DS · 2005 · author #2
  40. Cluster Computing and the Power of Edge Recognition cs.CC · 2005 · author #1
  41. Open Questions in the Theory of Semifeasible Computation cs.CC · 2005 · author #2
  42. The Complexity of Kings cs.CC · 2005 · author #2
  43. P-Selectivity, Immunity, and the Power of One Bit cs.CC · 2005 · author #1
  44. Dichotomy for Voting Systems cs.GT · 2005 · author #2
  45. Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory cs.CC · 2005 · author #1
  46. The Complexity of Computing the Size of an Interval cs.CC · 2005 · author #1
  47. Algebraic Properties for Selector Functions cs.CC · 2005 · author #1
  48. Overhead-Free Computation, DCFLs, and CFLs cs.CC · 2004 · author #1
  49. All Superlinear Inverse Schemes are coNP-Hard cs.CC · 2004 · author #2
  50. Complexity Results in Graph Reconstruction cs.CC · 2004 · author #2
  51. Using the No-Search Easy-Hard Technique for Downward Collapse cs.CC · 2001 · author #2
  52. P-Immune Sets with Holes Lack Self-Reducibility Properties cs.CC · 2001 · author #1
  53. A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions cs.CC · 2000 · author #2
  54. If P \neq NP then Some Strongly Noninvertible Functions are Invertible cs.CC · 2000 · author #1
  55. A Moment of Perfect Clarity I: The Parallel Census Technique cs.CC · 2000 · author #2
  56. Take-home Complexity cs.CY · 2000 · author #1
  57. Translating Equality Downwards cs.CC · 1999 · author #2
  58. A Downward Collapse within the Polynomial Hierarchy cs.CC · 1999 · author #2
  59. Self-Specifying Machines cs.CC · 1999 · author #1
  60. Query Order and the Polynomial Hierarchy cs.CC · 1999 · author #2
  61. An Introduction to Query Order cs.CC · 1999 · author #2
  62. R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness cs.CC · 1999 · author #2
  63. What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses cs.CC · 1999 · author #2
  64. Query Order cs.CC · 1999 · author #1
  65. Restrictive Acceptance Suffices for Equivalence Problems cs.CC · 1999 · author #2
  66. Characterizations of the Existence of Partial and Total One-Way Permutations cs.CC · 1999 · author #2
  67. Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets cs.CC · 1999 · author #1
  68. Raising NP Lower Bounds to Parallel NP Lower Bounds cs.CC · 1999 · author #2
  69. A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem cs.CC · 1999 · author #1
  70. Boolean Operations, Joins, and the Extended Low Hierarchy cs.CC · 1999 · author #1
  71. Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP cs.CC · 1999 · author #2
  72. Easy Sets and Hard Certificate Schemes cs.CC · 1999 · author #1
  73. Polynomial-Time Multi-Selectivity cs.CC · 1999 · author #1
  74. Robust Reductions cs.CC · 1999 · author #2
  75. On Bounded-Weight Error-Correcting Codes cs.IT · 1999 · author #3
  76. Writing and Editing Complexity Theory: Tales and Tools cs.GL · 1998 · author #1
  77. Downward Collapse from a Weaker Hypothesis cs.CC · 1998 · author #2
  78. Creating Strong Total Commutative Associative Complexity-Theoretic One-Way Functions from Any Complexity-Theoretic One-Way Function cs.CC · 1998 · author #1

Mentions

  • 2606.20399 #3 · arxiv_oai · confidence 0.70 Lane A. Hemaspaandra
  • 2606.12039 #5 · arxiv_oai · confidence 0.70 Lane A. Hemaspaandra
  • 1410.2652 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1406.4106 #1 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1404.4560 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1310.6997 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1308.0544 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1305.0943 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1301.6118 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1210.8099 #1 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1210.6963 #1 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1203.0411 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1202.6655 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1202.6649 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1202.6641 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1106.1150 #1 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1105.5032 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1012.0556 #1 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 1007.1800 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 0809.4484 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 0806.2555 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 0801.4585 #2 · backfill · confidence 0.70 Lane A. Hemaspaandra
  • 0711.4759 #3 · backfill · confidence 0.70 Lane A. Hemaspaandra

Frequent Coauthors