1 Search Results for "Hesse, William"


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

Authors: William Hesse

Published in: Dagstuhl Seminar Proceedings, Volume 6451, Circuits, Logic, and Games (2007)


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.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.5},
  URN =		{urn:nbn:de:0030-drops-9749},
  doi =		{10.4230/DagSemProc.06451.5},
  annote =	{Keywords: Boolean Functions, auxiliary data, circuit complexity, lower bounds}
}
  • Refine by Author
  • 1 Hesse, William

  • Refine by Classification

  • Refine by Keyword
  • 1 Boolean Functions
  • 1 auxiliary data
  • 1 circuit complexity
  • 1 lower bounds

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2007

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail