DagSemProc.06451.5.pdf
- Filesize: 65 kB
- 3 pages
Document
Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6451
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2007-04-23
Cite As Get BibTex
William Hesse. Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.06451.5
Abstract
While researching dynamic data structures of polynomial size that are updated by extremely simple circuits, we have come across many interesting algebraic problems. Some of these simple questions about small sums and products in an algebra would give lower bounds on the complexity of dynamic data structures.
Subject Classification
Keywords
- Boolean Functions
- auxiliary data
- circuit complexity
- lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads