| 2009 |
|---|
| 96 | EE | Dorothea Baumeister,
Felix Brandt,
Felix A. Fischer,
Jörg Rothe:
Deciding Membership in Minimal Upward Covering Sets is Complete for Parallel Access to NP
CoRR abs/0901.3692: (2009) |
| 95 | EE | Claudia Lindner,
Jörg Rothe:
Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols
CoRR abs/0902.0620: (2009) |
| 94 | EE | Dorothea Baumeister,
Jörg Rothe:
Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem.
Fundam. Inform. 91(1): 35-51 (2009) |
| 2008 |
|---|
| 93 | EE | Piotr Faliszewski,
Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Copeland Voting Fully Resists Constructive Control.
AAIM 2008: 165-176 |
| 92 | EE | Dorothea Baumeister,
Jörg Rothe:
The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions.
LATA 2008: 76-87 |
| 91 | EE | Gábor Erdélyi,
Markus Nowak,
Jörg Rothe:
Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control.
MFCS 2008: 311-322 |
| 90 | EE | Gábor Erdélyi,
Markus Nowak,
Jörg Rothe:
Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
CoRR abs/0806.0535: (2008) |
| 89 | EE | Gábor Erdélyi,
Lane A. Hemaspaandra,
Jörg Rothe,
Holger Spakowski:
Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
CoRR abs/0806.2555: (2008) |
| 88 | EE | Piotr Faliszewski,
Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Llull and Copeland Voting Computationally Resist Bribery and Control
CoRR abs/0809.4484: (2008) |
| 87 | EE | Lane A. Hemaspaandra,
Jörg Rothe,
Amitabh Saxena:
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions.
Theor. Comput. Sci. 401(1-3): 27-35 (2008) |
| 2007 |
|---|
| 86 | | Piotr Faliszewski,
Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Llull and Copeland Voting Broadly Resist Bribery and Control.
AAAI 2007: 724-730 |
| 85 | EE | Gábor Erdélyi,
Lane A. Hemaspaandra,
Jörg Rothe,
Holger Spakowski:
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time.
FCT 2007: 300-311 |
| 84 | EE | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
IJCAI 2007: 1308-1314 |
| 83 | EE | Dorothea Baumeister,
Jörg Rothe:
Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem.
MCU 2007: 134-145 |
| 82 | EE | Dagmar Bruß,
Gábor Erdélyi,
Tim Meyer,
Tobias Riege,
Jörg Rothe:
Quantum cryptography: A survey.
ACM Comput. Surv. 39(2): (2007) |
| 81 | EE | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Anyone but him: The complexity of precluding an alternative.
Artif. Intell. 171(5-6): 255-285 (2007) |
| 80 | EE | Dorothea Baumeister,
Jörg Rothe:
Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem
CoRR abs/0705.0915: (2007) |
| 79 | EE | Dorothea Baumeister,
Jörg Rothe:
The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions
CoRR abs/0711.1827: (2007) |
| 78 | EE | Piotr Faliszewski,
Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Copeland Voting Fully Resists Constructive Control
CoRR abs/0711.4759: (2007) |
| 77 | EE | Gábor Erdélyi,
Lane A. Hemaspaandra,
Jörg Rothe,
Holger Spakowski:
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
CoRR abs/cs/0703097: (2007) |
| 76 | EE | Tobias Riege,
Jörg Rothe,
Holger Spakowski,
Masaki Yamamoto:
An improved exact algorithm for the domatic number problem.
Inf. Process. Lett. 101(3): 101-106 (2007) |
| 75 | EE | Jörg Rothe:
Review of "Complexity and Cryptography: An Introduction by John Talbot and Dominic Welsh", Cambridge University Press, 2006, 292 pages.
SIGACT News 38(2): 16-20 (2007) |
| 2006 |
|---|
| 74 | EE | Tobias Riege,
Jörg Rothe,
Holger Spakowski,
Masaki Yamamoto:
An Improved Exact Algorithm for the Domatic Number Problem
CoRR abs/cs/0603060: (2006) |
| 73 | EE | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
CoRR abs/cs/0608057: (2006) |
| 72 | EE | Piotr Faliszewski,
Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
A Richer Understanding of the Complexity of Election Systems
CoRR abs/cs/0609112: (2006) |
| 71 | EE | Tobias Riege,
Jörg Rothe:
Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.
Electronic Colloquium on Computational Complexity (ECCC) 13(036): (2006) |
| 70 | EE | Tobias Riege,
Jörg Rothe:
Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
Electronic Colloquium on Computational Complexity (ECCC) 13(078): (2006) |
| 69 | EE | André Große,
Jörg Rothe,
Gerd Wechsung:
On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P.
Inf. Process. Lett. 99(6): 215-221 (2006) |
| 68 | EE | Tobias Riege,
Jörg Rothe:
Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey.
J. UCS 12(5): 551-578 (2006) |
| 67 | EE | Jörg Rothe,
Hiroki Arimura:
Computational Challenges of Massive Data Sets and Randomness in Computation (J.UCS Special Issue on the First and Second Japanese-German Frontiers of Science Symposia).
J. UCS 12(6): 579-580 (2006) |
| 66 | EE | Tobias Riege,
Jörg Rothe:
Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
J. UCS 12(6): 725-745 (2006) |
| 65 | EE | Lane A. Hemaspaandra,
Kari Pasanen,
Jörg Rothe:
If P neq NP then some strongly noninvertible functions are invertible.
Theor. Comput. Sci. 362(1-3): 54-62 (2006) |
| 64 | EE | Tobias Riege,
Jörg Rothe:
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
Theory Comput. Syst. 39(5): 635-668 (2006) |
| 2005 |
|---|
| 63 | | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Anyone but Him: The Complexity of Precluding an Alternative.
AAAI 2005: 95-101 |
| 62 | EE | Lane A. Hemaspaandra,
Jörg Rothe,
Amitabh Saxena:
Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory.
ICTCS 2005: 265-279 |
| 61 | EE | Tobias Riege,
Jörg Rothe:
An Exact 2.9416n Algorithm for the Three Domatic Number Problem.
MFCS 2005: 733-744 |
| 60 | EE | Lane A. Hemaspaandra,
Jörg Rothe,
Amitabh Saxena:
Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory
CoRR abs/cs/0503049: (2005) |
| 59 | EE | Tobias Riege,
Jörg Rothe:
An Exact 2.9416n Algorithm for the Three Domatic Number Problem
CoRR abs/cs/0506090: (2005) |
| 58 | EE | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Anyone but Him: The Complexity of Precluding an Alternative
CoRR abs/cs/0507027: (2005) |
| 57 | EE | Gábor Erdélyi,
Tobias Riege,
Jörg Rothe:
Quantum Cryptography: A Survey
Electronic Colloquium on Computational Complexity (ECCC)(146): (2005) |
| 2004 |
|---|
| 56 | EE | Jörg Rothe:
Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy.
Algebraic Methods in Computational Complexity 2004 |
| 2003 |
|---|
| 55 | EE | Jörg Rothe:
Exact complexity of Exact-Four-Colorability.
Inf. Process. Lett. 87(1): 7-12 (2003) |
| 54 | EE | Jörg Rothe,
Holger Spakowski,
Jörg Vogel:
Exact Complexity of the Winner Problem for Young Elections.
Theory Comput. Syst. 36(4): 375-386 (2003) |
| 2002 |
|---|
| 53 | | Jörg Rothe,
Holger Spakowski,
Jörg Vogel:
Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.
IFIP TCS 2002: 310-322 |
| 52 | EE | Edith Hemaspaandra,
Jörg Rothe,
Holger Spakowski:
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
WG 2002: 258-269 |
| 51 | EE | Jörg Rothe:
Some facets of complexity theory and cryptography: A five-lecture tutorial.
ACM Comput. Surv. 34(4): 504-549 (2002) |
| 50 | EE | Tobias Riege,
Jörg Rothe:
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem
CoRR cs.CC/0212016: (2002) |
| 49 | EE | Tobias Riege,
Jörg Rothe:
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem
Electronic Colloquium on Computational Complexity (ECCC)(068): (2002) |
| 48 | EE | Jörg Rothe,
Lane A. Hemaspaandra:
On characterizing the existence of partial one-way permutations.
Inf. Process. Lett. 82(3): 165-171 (2002) |
| 47 | EE | Jörg Rothe:
Kryptographische Protokolle und Null-Information.
Informatik Spektrum 25(2): 120-131 (2002) |
| 46 | EE | André Große,
Jörg Rothe,
Gerd Wechsung:
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones.
Theory Comput. Syst. 35(1): 81-93 (2002) |
| 2001 |
|---|
| 45 | EE | Lane A. Hemaspaandra,
Kari Pasanen,
Jörg Rothe:
If P != NP Then Some Strongly Noninvertible Functions Are Invertible.
FCT 2001: 162-171 |
| 44 | EE | André Große,
Jörg Rothe,
Gerd Wechsung:
Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.
ICTCS 2001: 339-356 |
| 43 | EE | André Große,
Jörg Rothe,
Gerd Wechsung:
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
CoRR cs.CC/0106041: (2001) |
| 42 | EE | André Große,
Jörg Rothe,
Gerd Wechsung:
A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
CoRR cs.CC/0106045: (2001) |
| 41 | EE | Jörg Rothe:
Exact Complexity of Exact-Four-Colorability
CoRR cs.CC/0109018: (2001) |
| 40 | EE | Edith Hemaspaandra,
Jörg Rothe,
Holger Spakowski:
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP
CoRR cs.CC/0110025: (2001) |
| 39 | EE | Jörg Rothe:
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
CoRR cs.CC/0111056: (2001) |
| 38 | EE | Jörg Rothe,
Holger Spakowski,
Jörg Vogel:
Exact Complexity of the Winner Problem for Young Elections
CoRR cs.CC/0112021: (2001) |
| 37 | EE | Jörg Rothe:
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
Electronic Colloquium on Computational Complexity (ECCC)(096): (2001) |
| 2000 |
|---|
| 36 | EE | Jörg Rothe:
Heuristics Versus Completeness for Graph Coloring.
Chicago J. Theor. Comput. Sci. 2000: (2000) |
| 35 | EE | Lane A. Hemaspaandra,
Kari Pasanen,
Jörg Rothe:
If P \neq NP then Some Strongly Noninvertible Functions are Invertible
CoRR cs.CC/0010011: (2000) |
| 34 | | Judy Goldsmith,
Mitsunori Ogihara,
Jörg Rothe:
Tally NP Sets and Easy Census Functions.
Inf. Comput. 158(1): 29-52 (2000) |
| 33 | EE | Rajesh P. N. Rao,
Jörg Rothe,
Osamu Watanabe:
Corrigendum to "Upward separation for FewP and related classes".
Inf. Process. Lett. 74(1-2): 89 (2000) |
| 32 | EE | Lane A. Hemaspaandra,
Jörg Rothe:
A second step towards complexity-theoretic analogs of Rice's Theorem.
Theor. Comput. Sci. 244(1-2): 205-217 (2000) |
| 31 | EE | Lane A. Hemaspaandra,
Jörg Rothe:
Characterizing the existence of one-way permutations.
Theor. Comput. Sci. 244(1-2): 257-261 (2000) |
| 1999 |
|---|
| 30 | EE | Bernd Borchert,
Lane A. Hemaspaandra,
Jörg Rothe:
Restrictive Acceptance Suffices for Equivalence Problems.
FCT 1999: 124-135 |
| 29 | EE | Lane A. Hemaspaandra,
Jörg Rothe:
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
CoRR cs.CC/9907033: (1999) |
| 28 | EE | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
Polynomial-Time Multi-Selectivity
CoRR cs.CC/9907034: (1999) |
| 27 | EE | Lane A. Hemaspaandra,
Jörg Rothe,
Gerd Wechsung:
Easy Sets and Hard Certificate Schemes
CoRR cs.CC/9907035: (1999) |
| 26 | EE | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP
CoRR cs.CC/9907036: (1999) |
| 25 | EE | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
Boolean Operations, Joins, and the Extended Low Hierarchy
CoRR cs.CC/9907037: (1999) |
| 24 | EE | Lane A. Hemaspaandra,
Jörg Rothe:
A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem
CoRR cs.CC/9907038: (1999) |
| 23 | EE | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Raising NP Lower Bounds to Parallel NP Lower Bounds
CoRR cs.CC/9907039: (1999) |
| 22 | EE | Jörg Rothe,
Lane A. Hemaspaandra:
Characterizations of the Existence of Partial and Total One-Way Permutations
CoRR cs.CC/9907040: (1999) |
| 21 | EE | Bernd Borchert,
Lane A. Hemaspaandra,
Jörg Rothe:
Restrictive Acceptance Suffices for Equivalence Problems
CoRR cs.CC/9907041: (1999) |
| 20 | EE | Alina Beygelzimer,
Lane A. Hemaspaandra,
Christopher M. Homan,
Jörg Rothe:
One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties
CoRR cs.CC/9911007: (1999) |
| 19 | | Jörg Rothe:
Immunity and simplicity for exact counting and other counting classes.
ITA 33(2): 159-176 (1999) |
| 18 | | Lane A. Hemaspaandra,
Jörg Rothe:
Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory.
J. Comput. Syst. Sci. 58(3): 648-659 (1999) |
| 1998 |
|---|
| 17 | EE | Lane A. Hemaspaandra,
Jörg Rothe:
A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem.
MFCS 1998: 418-426 |
| 16 | EE | Judy Goldsmith,
Mitsunori Ogihara,
Jörg Rothe:
Tally NP Sets and Easy Census Functions.
MFCS 1998: 483-492 |
| 15 | EE | Lane A. Hemaspaandra,
Jörg Rothe:
Creating Strong Total Commutative Associative Complexity-Theoretic One-Way Functions from Any Complexity-Theoretic One-Way Function
CoRR cs.CC/9808003: (1998) |
| 14 | EE | Jörg Rothe:
Immunity and Simplicity for Exact Counting and Other Counting Classes
CoRR cs.CC/9809001: (1998) |
| 13 | EE | Judy Goldsmith,
Mitsunori Ogihara,
Jörg Rothe:
Tally NP Sets and Easy Census Functions
CoRR cs.CC/9809002: (1998) |
| 12 | EE | Edith Hemaspaandra,
Jörg Rothe:
Recognizing when Greed can Approximate Maximum Independent Sets is Complete for Parallel Access to NP.
Inf. Process. Lett. 65(3): 151-156 (1998) |
| 11 | EE | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
Boolean Operations, Joins, and the Extended Low Hierarchy.
Theor. Comput. Sci. 205(1-2): 317-327 (1998) |
| 1997 |
|---|
| 10 | | Lane A. Hemaspaandra,
Jörg Rothe,
Gerd Wechsung:
On Sets with Easy Certificates and the Existence of One-Way Permutations.
CIAC 1997: 264-275 |
| 9 | | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP.
ICALP 1997: 214-224 |
| 8 | EE | Lane A. Hemaspaandra,
Jörg Rothe,
Gerd Wechsung:
Easy Sets and Hard Certificate Schemes.
Acta Inf. 34(11): 859-879 (1997) |
| 7 | EE | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Jörg Rothe:
Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP.
J. ACM 44(6): 806-825 (1997) |
| 6 | EE | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
Polynomial-Time Multi-Selectivity.
J. UCS 3(3): 197-229 (1997) |
| 5 | | Lane A. Hemaspaandra,
Jörg Rothe:
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets.
SIAM J. Comput. 26(3): 634-653 (1997) |
| 1996 |
|---|
| 4 | | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
The Join Can Lower Complexity.
COCOON 1996: 260-267 |
| 3 | EE | Bernd Borchert,
Lane A. Hemaspaandra,
Jörg Rothe:
Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems
Electronic Colloquium on Computational Complexity (ECCC) 3(45): (1996) |
| 1995 |
|---|
| 2 | | Lane A. Hemaspaandra,
Jörg Rothe:
Intersection Suffices for Boolean Hierarchy Equivalence.
COCOON 1995: 430-435 |
| 1994 |
|---|
| 1 | | Rajesh P. N. Rao,
Jörg Rothe,
Osamu Watanabe:
Upward Separation for FewP and Related Classes.
Inf. Process. Lett. 52(4): 175-180 (1994) |
