Search Results

Documents authored by Engels, Christian

Found 2 Possible Name Variants:

Engels, Christian

Document
DOI: 10.4230/LIPIcs.IPEC.2019.3
Parameterized Valiant’s Classes

Authors: Markus Bläser and Christian Engels

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolean counting classes #FPT and #W[t], and define appropriate reductions and completeness notions. Our main contribution is the VW[1]-completeness proof of the parameterized clique family. This proof is far more complicated than in the Boolean world. It requires some new concepts like composition theorems for bounded exponential sums and Boolean-arithmetic formulas. In addition, we also look at two polynomials linked to the permanent with vastly different parameterized complexity.
Cite as

Markus Bläser and Christian Engels. Parameterized Valiant’s Classes. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.IPEC.2019.3,
  author =	{Bl\"{a}ser, Markus and Engels, Christian},
  title =	{{Parameterized Valiant’s Classes}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.3},
  URN =		{urn:nbn:de:0030-drops-114648},
  doi =		{10.4230/LIPIcs.IPEC.2019.3},
  annote =	{Keywords: Algebraic complexity theory, parameterized complexity theory, Valiant’s classes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.555
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals

Authors: Markus Blaeser and Christian Engels

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We construct a hitting set generator for sparse multivariate polynomials over the reals. The seed length of our generator is O(log^2 (mn/epsilon)) where m is the number of monomials, n is number of variables, and 1 - epsilon is the hitting probability. The generator can be evaluated in time polynomial in log m, n, and log 1/epsilon. This is the first hitting set generator whose seed length is independent of the degree of the polynomial. The seed length of the best generator so far by Klivans and Spielman [STOC 2001] depends logarithmically on the degree. From this, we get a randomized algorithm for testing sparse black box polynomial identities over the reals using O(log^2 (mn/epsilon)) random bits with running time polynomial in log m, n, and log(1/epsilon). We also design a deterministic test with running time ~O(m^3 n^3). Here, the ~O-notation suppresses polylogarithmic factors. The previously best deterministic test by Lipton and Vishnoi [SODA 2003] has a running time that depends polynomially on log delta, where $delta$ is the degree of the black box polynomial.
Cite as

Markus Blaeser and Christian Engels. Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 555-566, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{blaeser_et_al:LIPIcs.STACS.2011.555,
  author =	{Blaeser, Markus and Engels, Christian},
  title =	{{Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{555--566},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.555},
  URN =		{urn:nbn:de:0030-drops-30433},
  doi =		{10.4230/LIPIcs.STACS.2011.555},
  annote =	{Keywords: Descartes’ rule of signs, polynomial identity testing, sparse polynomials, black box testing}
}

Engels, Christiane

Document
DOI: 10.4230/LIPIcs.TIME.2018.11
Algebraic Operators for Processing Sets of Temporal Intervals in Relational Databases

Authors: Andreas Dohr, Christiane Engels, and Andreas Behrend

Published in: LIPIcs, Volume 120, 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Abstract
The efficient management of temporal data has become increasingly important for many database applications. Most commercial systems already allow the management of temporal data but the operational support for processing this data is still rather limited. One particular reason is that many extension proposals typically require considerable modifications of the underlying database engine. In this paper, we propose a lightweight solution where temporal operators are realized using a library of user-defined functions. This way the complexity of temporal queries can be drastically reduced leading to more readable and less error-prone code without touching the database system. Our experiments show that the proposed operators significantly outperform temporal queries formulated in pure SQL. In addition, we investigate the possibility to incorporate algebraic optimization strategies directly into our operator definitions which allow for further performance improvements.
Cite as

Andreas Dohr, Christiane Engels, and Andreas Behrend. Algebraic Operators for Processing Sets of Temporal Intervals in Relational Databases. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dohr_et_al:LIPIcs.TIME.2018.11,
  author =	{Dohr, Andreas and Engels, Christiane and Behrend, Andreas},
  title =	{{Algebraic Operators for Processing Sets of Temporal Intervals in Relational Databases}},
  booktitle =	{25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Alechina, Natasha and N{\o}rv\r{a}g, Kjetil and Penczek, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2018.11},
  URN =		{urn:nbn:de:0030-drops-97769},
  doi =		{10.4230/LIPIcs.TIME.2018.11},
  annote =	{Keywords: Temporal Databases, Relational Operators, Situation Calculus}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact