CaltechAUTHORS
Published January 2002 | Version public
Journal Article Metadata-only

A Permanent Algorithm with exp[Ω ((n^(1/3))/(2 ln n))] Expected Speedup for 0-1 Matrices

Creators

  • 1. ROR icon California Institute of Technology

Abstract

This paper outlines a permanent algorithm with mildly exponential expected speedup over Ryser's inclusion and exclusion algorithm for 0-1 matrices. The algorithm is based on a finite-difference formula that is a generalization of Ryser's formula. The matrix is augmented by a column of entries selected to produce zero-valued terms in the formula. The algorithm achieves speedup by avoiding computation of many zero-valued terms.

Additional Information

© 2002 Springer. Received January 14, 1998; revised October 21, 1999. Communicated by A. Borodin. Online publication October 5, 2001. The first author thanks the second author for his guidance, insights, and example. We thank an anonymous referee for invaluable contributions to the development and presentation of these results.

Additional details

Identifiers

Eprint ID
101386
Resolver ID
CaltechAUTHORS:20200219-114918580

Dates

Created
2020-02-19
Created from EPrint's datestamp field
Updated
2021-11-16
Created from EPrint's last_modified field