License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-9749
URL: http://drops.dagstuhl.de/opus/volltexte/2007/974/
Hesse, William

Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures

pdf-format:
Dokument 1.pdf (65 KB)

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:DSP:2007:974,
  author =	{William Hesse},
  title =	{Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures},
  booktitle =	{Circuits, Logic, and Games},
  year =	{2007},
  editor =	{Thomas Schwentick and Denis Th{\'e}rien and Heribert Vollmer },
  number =	{06451},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/974},
  annote =	{Keywords: Boolean Functions, auxiliary data, circuit complexity, lower bounds}
}

Keywords: Boolean Functions, auxiliary data, circuit complexity, lower bounds
Seminar: 06451 - Circuits, Logic, and Games
Issue date: 2007
Date of publication: 23.04.2007

DROPS-Home | Fulltext Search | Imprint Published by LZI