On the Shortest Linear Straight-Line Program for Computing Linear Forms

Boyar, Joan; Matthews, Philip; Peralta, Rene

doi:https://doi.org/10.1007/978-3-540-85238-4_13

Conference Proceedings

On the Shortest Linear Straight-Line Program for Computing Linear Forms

Documentation Topics

Published: August 29, 2008

Author(s)

Joan Boyar (University of Southern Denmark), Philip Matthews (University of Southern Denmark), Rene Peralta (NIST)

Conference

Name: 33rd International Symposium, MFCS 2008
Dates: August 25-29, 2008
Location: Toru'n, Poland
Citation: Mathematical Foundations of Computer Science 2008, Lecture Notes in Computer Science vol. 5162, pp. 168-179

Announcement

Abstract

We study the complexity of the Shortest Linear Program (SLP) problem, which is to the number of linear operations necessary to compute a set of linear forms. SLP is shown to be NP-hard. Furthermore, a special case of the corresponding decision problem is shown to be Max SNP-Complete. Algorithms producing cancellation-free straight-line programs, those in which there is never any cancellation of variables in GF(2) have been proposed for circuit minimization for various cryptographic applications. We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to non-trivial inputs.

Keywords

approximation ratio; circuit complexity; linear programs; MAX SNP-Complete; NP-HARD

Control Families

None selected

Documentation

Publication:
Conference Proceedings (DOI)

Supplemental Material:
None available

Document History:
08/29/08: Conference Proceedings (Final)

Topics

Security and Privacy
cryptography

Technologies
circuits; complexity