On approximation by circle plus-OBDDs
2007 | journal article. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Documents & Media
Details
- Authors
- Brosenne, Henrik ; Damm, Carsten ; Homeister, Matthias; Waack, Stephan
- Abstract
- We show that for every V-OBDD of quasipolynomial size there is a circle plus-OBDD of quasipolynornial size computing the same function up to a small fraction of the inputs. We also prove that the final step in the approximation cannot be improved and discuss possibilities of proving non-approximability results and connections to lower bounds on matrix rigidity. (c) 2006 Elsevier B.V. All rights reserved.
- Issue Date
- 2007
- Journal
- Information Processing Letters
- ISSN
- 0020-0190
- Language
- English