Search Results

Documents authored by Kaltofen, Erich


Found 2 Possible Name Variants:

Kaltofen, Erich L.

Document
Symmetric Determinantal Representation of Weakly-Skew Circuits

Authors: Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier

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


Abstract
We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weakly-skew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly-skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Buergisser on the VNP-completeness of the partial permanent. In particular, we show that the partial permanent cannot be VNP-complete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.

Cite as

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier. Symmetric Determinantal Representation of Weakly-Skew Circuits. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 543-554, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.STACS.2011.543,
  author =	{Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha},
  title =	{{Symmetric Determinantal Representation of Weakly-Skew Circuits}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{543--554},
  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.543},
  URN =		{urn:nbn:de:0030-drops-30426},
  doi =		{10.4230/LIPIcs.STACS.2011.543},
  annote =	{Keywords: algebraic complexity, determinant and permanent of symmetric matrices, formulas, skew circuits, Valiant’s classes}
}

Kaltofen, Erich

Document
09471 Abstracts Collection – Computer-assisted proofs - tools, methods and applications

Authors: Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump

Published in: Dagstuhl Seminar Proceedings, Volume 9471, Computer-assisted proofs - tools, methods and applications (2010)


Abstract
From 15.11. to 20.11.2009, the Dagstuhl Seminar 09471 ``Computer-assisted proofs - tools, methods and applications '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump. 09471 Abstracts Collection – Computer-assisted proofs - tools, methods and applications. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{brown_et_al:DagSemProc.09471.1,
  author =	{Brown, Malcolm B. and Kaltofen, Erich and Oishi, Shin'ichi and Rump, Siegfried M.},
  title =	{{09471 Abstracts Collection – Computer-assisted proofs - tools, methods and applications}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9471},
  editor =	{B. Malcolm Brown and Erich Kaltofen and Shin'ichi Oishi and Siegfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09471.1},
  URN =		{urn:nbn:de:0030-drops-25328},
  doi =		{10.4230/DagSemProc.09471.1},
  annote =	{Keywords: Verification methods, computer algebra, computer-assisted proofs}
}
Document
09471 Executive Summary – Computer-assisted proofs - tools, methods and applications

Authors: Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump

Published in: Dagstuhl Seminar Proceedings, Volume 9471, Computer-assisted proofs - tools, methods and applications (2010)


Abstract
From November 15-20, 2009, the Dagstuhl seminar on "Computer-assisted proofs - tools, methods and applications" continued a series of previous successful seminars. Participants from 10 different countries presented recent results in verification methods, computer algebra, and other computer-assisted-proof related areas. We had lively talks and discussions, during the regular times for talks, during meals and afterwards. In the following links to abstracts and/or the presentation are given were applicable.

Cite as

Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump. 09471 Executive Summary – Computer-assisted proofs - tools, methods and applications. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{brown_et_al:DagSemProc.09471.2,
  author =	{Brown, Malcolm B. and Kaltofen, Erich and Oishi, Shin'ichi and Rump, Siegfried M.},
  title =	{{09471 Executive Summary – Computer-assisted proofs - tools, methods and applications}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9471},
  editor =	{B. Malcolm Brown and Erich Kaltofen and Shin'ichi Oishi and Siegfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09471.2},
  URN =		{urn:nbn:de:0030-drops-25316},
  doi =		{10.4230/DagSemProc.09471.2},
  annote =	{Keywords: Verification methods, computer algebra, computer-assisted proofs}
}
Document
06271 Abstracts Collection – Challenges in Symbolic Computation Software

Authors: Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)


Abstract
From 02.07.06 to 07.07.06, the Dagstuhl Seminar 06271 ``Challenges in Symbolic Computation Software'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt. 06271 Abstracts Collection – Challenges in Symbolic Computation Software. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{decker_et_al:DagSemProc.06271.1,
  author =	{Decker, Wolfram and Dewar, Mike and Kaltofen, Erich and Watt, Stephen M.},
  title =	{{06271 Abstracts Collection – Challenges in Symbolic Computation Software}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.1},
  URN =		{urn:nbn:de:0030-drops-7814},
  doi =		{10.4230/DagSemProc.06271.1},
  annote =	{Keywords: Symbolic computation, computer algebra, computational algebraic geometry, combinatorial methods in algebra, hybrid, symbolic-numerical methods, algorithm design, symbolic computation languages, systems and user interfaces}
}
Document
06271 Executive Summary - Challenges in Symbolic Computation Software

Authors: Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)


Abstract
Symbolic computation software allows mathematicians, scientists, engineers, or educators to deal with elaborate calculations using a computer. The applications range from introducing the experimental method in fields of pure mathematics to practical applications, for instance, in cryptology, robotics, or signal theory. The software includes mainstream commercial products such as Maple or Mathematica and highly specialized, public domain systems such as CoCoa, Macaulay2, or Singular. Symbolic computation software implements a variety of sophisticated algorithms on polynomials, matrices, combinatorial structures, and other mathematical objects in a multitude of different dense, sparse, or implicit (black box) representations. The subject of the seminar was innovation in algorithms and software, bringing algorithm designers, software builders, and software users together.

Cite as

Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt. 06271 Executive Summary - Challenges in Symbolic Computation Software. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{decker_et_al:DagSemProc.06271.2,
  author =	{Decker, Wolfram and Dewar, Mike and Kaltofen, Erich and Watt, Stephen M.},
  title =	{{06271 Executive Summary - Challenges in Symbolic Computation Software}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.2},
  URN =		{urn:nbn:de:0030-drops-7778},
  doi =		{10.4230/DagSemProc.06271.2},
  annote =	{Keywords: Symbolic computation, computer algebra, computational algebraic geometry, combinatorial methods in algebra, hybrid symbolic-numerical methods, algori}
}
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