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

July 19, 2023: URLs for CSRC publication details pages have changed. Legacy URLs should automatically redirect to the new URLs. However, links to the actual publications have NOT changed (e.g., DOIs and PDFs on nvlpubs.nist.gov). Please send inquiries to csrc-inquiry@nist.gov.

Conference Paper

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: 08/25/2008 - 08/29/2008
Location: Toru'n, Poland
Citation: Mathematical Foundations of Computer Science 2008, vol. 5162, pp. 168-179

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:
https://doi.org/10.1007/978-3-540-85238-4_13

Supplemental Material:
None available

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

Topics

Security and Privacy

cryptography

Technologies

circuits, complexity