35 citations · 200 across the 47 of their papers we have counts for
Showing 1998Show all
3 papers · 1 filter
cs.CC1998★ 1 cited
Tally NP Sets and Easy Census Functions
Judy Goldsmith, Mitsunori Ogihara, Joerg Rothe
We study the question of whether every P set has an easy (i.e., polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of languag…
cs.CC1998★ 1 cited
Immunity and Simplicity for Exact Counting and Other Counting Classes
Joerg Rothe
Ko [RAIRO 24, 1990] and Bruschi [TCS 102, 1992] showed that in some relativized world, PSPACE (in fact, ParityP) contains a set that is immune to the polynomial hierarchy (PH). In…
cs.CC1998
Creating Strong Total Commutative Associative Complexity-Theoretic One-Way Functions from Any Complexity-Theoretic One-Way Function
Lane A. Hemaspaandra, Joerg Rothe
Rabi and Sherman [RS97] presented novel digital signature and unauthenticated secret-key agreement protocols, developed by themselves and by Rivest and Sherman. These protocols use…