6 Search Results for "Lickteig, Thomas"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.49
Debordering Closure Results in Determinantal and Pfaffian Ideals

Authors: Anakin Dey and Zeyu Guo

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
One important question in algebraic complexity is understanding the complexity of polynomial ideals (Grochow, Bulletin of EATCS 131, 2020). Andrews and Forbes (STOC 2022) studied the determinantal ideals I^{det}_{n,m,r} generated by the r× r minors of n× m matrices. Over fields of characteristic zero or of sufficiently large characteristic, they showed that for any nonzero f ∈ I^{det}_{n,m,r}, the determinant of a t × t matrix of variables with t = Θ{r^{1/3}} is approximately computed by a constant-depth, polynomial-size f-oracle algebraic circuit, in the sense that the determinant lies in the border of such circuits. An analogous result was also obtained for Pfaffians in the same paper. In this work, we deborder the result of Andrews and Forbes by showing that when f has polynomial degree, the determinant is in fact exactly computed by a constant-depth, polynomial-size f-oracle algebraic circuit. We further establish an analogous result for Pfaffian ideals. Our results are established using the isolation lemma, combined with a careful analysis of straightening-law expansions of polynomials in determinantal and Pfaffian ideals.
Cite as

Anakin Dey and Zeyu Guo. Debordering Closure Results in Determinantal and Pfaffian Ideals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ITCS.2026.49,
  author =	{Dey, Anakin and Guo, Zeyu},
  title =	{{Debordering Closure Results in Determinantal and Pfaffian Ideals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.49},
  URN =		{urn:nbn:de:0030-drops-253363},
  doi =		{10.4230/LIPIcs.ITCS.2026.49},
  annote =	{Keywords: Algebraic circuit complexity, Isolation lemma, Debordering}
}
Document
DOI: 10.4230/DagSemProc.04061.1
04061 Abstracts Collection – Real Computation and Complexity

Authors: Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo

Published in: Dagstuhl Seminar Proceedings, Volume 4061, Real Computation and Complexity (2006)

Abstract
From 01.02.04 to 06.02.04, the Dagstuhl Seminar 04061 ``Real Computation and Complexity'' 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

Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo. 04061 Abstracts Collection – Real Computation and Complexity. In Real Computation and Complexity. Dagstuhl Seminar Proceedings, Volume 4061, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lickteig_et_al:DagSemProc.04061.1,
  author =	{Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel},
  title =	{{04061 Abstracts Collection – Real Computation and Complexity}},
  booktitle =	{Real Computation and Complexity},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{4061},
  editor =	{Thomas Lickteig and Klaus Meer and Luis Miguel Pardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04061.1},
  URN =		{urn:nbn:de:0030-drops-4584},
  doi =		{10.4230/DagSemProc.04061.1},
  annote =	{Keywords: Real algebraic complexity and lower bounds, numerical methods, homotopy methods, condition as complexity ingredient, symbolic methods, bit complexity}
}
Document
DOI: 10.4230/DagSemProc.04061.2
04061 Summary – Real Computation and Complexity

Authors: Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo

Published in: Dagstuhl Seminar Proceedings, Volume 4061, Real Computation and Complexity (2006)

Abstract
The seminar "Real Computation and Complexity" was intended as a meeting place of several tendencies in the complexity analysis of algorithms in real computation. One main idea therefore was to bring together scientists with rather different backgrounds such as numerical analysis, symbolic computing, real and complex algebraic geometry, logic, differential algebra and computational complexity. This broadness guaranteed to get a thorough overview of current results, methods and trends in the area. It allowed as well to discuss main problems related to all aspects of real computation and complexity from different perspectives.
Cite as

Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo. 04061 Summary – Real Computation and Complexity. In Real Computation and Complexity. Dagstuhl Seminar Proceedings, Volume 4061, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lickteig_et_al:DagSemProc.04061.2,
  author =	{Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel},
  title =	{{04061 Summary – Real Computation and Complexity}},
  booktitle =	{Real Computation and Complexity},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{4061},
  editor =	{Thomas Lickteig and Klaus Meer and Luis Miguel Pardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04061.2},
  URN =		{urn:nbn:de:0030-drops-4994},
  doi =		{10.4230/DagSemProc.04061.2},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemRep.407
Real Computation and Complexity (Dagstuhl Seminar 04061)

Authors: Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo. Real Computation and Complexity (Dagstuhl Seminar 04061). Dagstuhl Seminar Report 407, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2004)

Copy BibTex To Clipboard

@TechReport{lickteig_et_al:DagSemRep.407,
  author =	{Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel},
  title =	{{Real Computation and Complexity (Dagstuhl Seminar 04061)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2004},
  type = 	{Dagstuhl Seminar Report},
  number =	{407},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.407},
  URN =		{urn:nbn:de:0030-drops-152874},
  doi =		{10.4230/DagSemRep.407},
}
Document
DOI: 10.4230/DagSemRep.214
Real Computation and Complexity (Dagstuhl Seminar 98241)

Authors: Felipe Cucker, Thomas Lickteig, Marie-Francoise Roy, and Michael Shub

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Felipe Cucker, Thomas Lickteig, Marie-Francoise Roy, and Michael Shub. Real Computation and Complexity (Dagstuhl Seminar 98241). Dagstuhl Seminar Report 214, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1999)

Copy BibTex To Clipboard

@TechReport{cucker_et_al:DagSemRep.214,
  author =	{Cucker, Felipe and Lickteig, Thomas and Roy, Marie-Francoise and Shub, Michael},
  title =	{{Real Computation and Complexity (Dagstuhl Seminar 98241)}},
  pages =	{1--15},
  ISSN =	{1619-0203},
  year =	{1999},
  type = 	{Dagstuhl Seminar Report},
  number =	{214},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.214},
  URN =		{urn:nbn:de:0030-drops-151006},
  doi =		{10.4230/DagSemRep.214},
}
Document
DOI: 10.4230/DagSemRep.131
Real Computation and Complexity (Dagstuhl Seminar 9545)

Authors: Felipe Cucker, Thomas Lickteig, and Michael Shub

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Felipe Cucker, Thomas Lickteig, and Michael Shub. Real Computation and Complexity (Dagstuhl Seminar 9545). Dagstuhl Seminar Report 131, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{cucker_et_al:DagSemRep.131,
  author =	{Cucker, Felipe and Lickteig, Thomas and Shub, Michael},
  title =	{{Real Computation and Complexity (Dagstuhl Seminar 9545)}},
  pages =	{1--14},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{131},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.131},
  URN =		{urn:nbn:de:0030-drops-150187},
  doi =		{10.4230/DagSemRep.131},
}
  • Refine by Type
  • 6 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2006
  • 1 2004
  • 1 1999
  • 1 1996

  • Refine by Author
  • 5 Lickteig, Thomas
  • 3 Meer, Klaus
  • 3 Pardo, Luis Miguel
  • 2 Cucker, Felipe
  • 2 Shub, Michael
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 3 DagSemRep
  • 2 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Algebraic complexity theory

  • Refine by Keyword
  • 1 Algebraic circuit complexity
  • 1 Debordering
  • 1 Isolation lemma
  • 1 Real algebraic complexity and lower bounds
  • 1 bit complexity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact