On approximation by circle plus-OBDDs
2007 | Zeitschriftenartikel. Eine Publikation mit Affiliation zur Georg-August-Universität Göttingen.
Spring zu: Zitieren & Links | Dokumente & Medien | Details | Versionsgeschichte
Dokumente & Medien
Details
- Autor(en)
- Brosenne, Henrik ; Damm, Carsten ; Homeister, Matthias; Waack, Stephan
- Zusammenfassung
- 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.
- Erscheinungsdatum
- 2007
- Zeitschrift
- Information Processing Letters
- ISSN
- 0020-0190
- Sprache
- Englisch