License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06451.5
URN: urn:nbn:de:0030-drops-9749
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/974/
Go to the corresponding Portal |
Hesse, William
Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures
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.
BibTeX - Entry
@InProceedings{hesse:DagSemProc.06451.5,
author = {Hesse, William},
title = {{Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures}},
booktitle = {Circuits, Logic, and Games},
pages = {1--3},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2007},
volume = {6451},
editor = {Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2007/974},
URN = {urn:nbn:de:0030-drops-9749},
doi = {10.4230/DagSemProc.06451.5},
annote = {Keywords: Boolean Functions, auxiliary data, circuit complexity, lower bounds}
}
Keywords: |
|
Boolean Functions, auxiliary data, circuit complexity, lower bounds |
Collection: |
|
06451 - Circuits, Logic, and Games |
Issue Date: |
|
2007 |
Date of publication: |
|
23.04.2007 |