LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 286-288 of 486

    • Embedding Cryptographic Trapdoors in Arbirtrary Knapsack Systems 

      Shamir, Adi (1982-09)
      In this paper we show that after sufficiently many modular multiplications, any knapsack system becomes a trapdoor system that can be used in pubic-key cryptography.

    • The Complexity of Evaluation Relational Queries 

      Cosmadakis, Stavros S. (1982-08)
      We show that, given a relation R, a relational query ? Involving only projection and join, and a conjectured result r, resting with ?(R)=r is D^p complete. Bounding the size of ?(R) from below (above) is NP-hard (co-NP-hard), ...

    • Two Remarks on the Power of Counting 

      Papadimitriou, Christos H.; Zachos, Stathis K. (1982-08)
      The relationship between the polynomial hierarchy and Valiant's class #P is at present unknown. We show that some low portions of the polynomial hierarchy, namely deterministic polynomial algorithms using an NP oracle at ...