On the shortest linear straight-line program for computing linear forms

Published

August 29, 2008

Author(s)

Joan Boyar, Philip Matthews, Rene Peralta

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.

Proceedings Title

Mathematical Foundations of Computer Science 2008 (Lecture Notes in Computer Science)

Volume

5162

Conference Dates

August 25-29, 2008

Conference Location

Torun, PL

Conference Title

33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008)

Pub Type

Conferences

Download Paper

DOI Link

Keywords

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

Citation

Boyar, J. , Matthews, P. and Peralta, R. (2008), On the shortest linear straight-line program for computing linear forms, Mathematical Foundations of Computer Science 2008 (Lecture Notes in Computer Science), Torun, PL, [online], https://doi.org/10.1007/978-3-540-85238-4_13 (Accessed April 23, 2024)