27 Search Results for "Kaltofen, Erich"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.44
Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields

Authors: Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We construct explicit pseudorandom generators that fool n-variate polynomials of degree at most d over a finite field 𝔽_q. The seed length of our generators is O(d log n + log q), over fields of size exponential in d and characteristic at least d(d-1)+1. Previous constructions such as Bogdanov’s (STOC 2005) and Derksen and Viola’s (FOCS 2022) had either suboptimal seed length or required the field size to depend on n. Our approach follows Bogdanov’s paradigm while incorporating techniques from Lecerf’s factorization algorithm (J. Symb. Comput. 2007) and insights from the construction of Derksen and Viola regarding the role of indecomposability of polynomials.
Cite as

Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk. Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dwivedi_et_al:LIPIcs.APPROX/RANDOM.2024.44,
  author =	{Dwivedi, Ashish and Guo, Zeyu and Volk, Ben Lee},
  title =	{{Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.44},
  URN =		{urn:nbn:de:0030-drops-210370},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.44},
  annote =	{Keywords: Pseudorandom Generators, Low Degree Polynomials}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.75
Derandomizing Multivariate Polynomial Factoring for Low Degree Factors

Authors: Pranjal Dutta, Amit Sinhababu, and Thomas Thierauf

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Kaltofen [STOC 1986] gave a randomized algorithm to factor multivariate polynomials given by algebraic circuits. We derandomize the algorithm in some special cases. For an n-variate polynomial f of degree d from a class 𝒞 of algebraic circuits, we design a deterministic algorithm to find all its irreducible factors of degree ≤ δ, for constant δ. The running time of this algorithm stems from a deterministic PIT algorithm for class 𝒞 and a deterministic algorithm that tests divisibility of f by a polynomial of degree ≤ δ. By using the PIT algorithm for constant-depth circuits by Limaye, Srinivasan and Tavenas [FOCS 2021] and the divisibility results by Forbes [FOCS 2015], this generalizes and simplifies a recent result by Kumar, Ramanathan and Saptharishi [SODA 2024]. They designed a subexponential-time algorithm that, given a blackbox access to f computed by a constant-depth circuit, outputs its irreducible factors of degree ≤ δ. When the input f is sparse, the time complexity of our algorithm depends on a whitebox PIT algorithm for ∑_i m_i g_i^{d_i}, where m_i are monomials and deg(g_i) ≤ δ. All the previous algorithms required a blackbox PIT algorithm for the same class. Our second main result considers polynomials f, where each irreducible factor has degree at most δ. We show that all the irreducible factors with their multiplicities can be computed in polynomial time with blackbox access to f. Finally, we consider factorization of sparse polynomials. We show that in order to compute all the sparse irreducible factors efficiently, it suffices to derandomize irreducibility preserving bivariate projections for sparse polynomials.
Cite as

Pranjal Dutta, Amit Sinhababu, and Thomas Thierauf. Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 75:1-75:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.APPROX/RANDOM.2024.75,
  author =	{Dutta, Pranjal and Sinhababu, Amit and Thierauf, Thomas},
  title =	{{Derandomizing Multivariate Polynomial Factoring for Low Degree Factors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{75:1--75:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.75},
  URN =		{urn:nbn:de:0030-drops-210687},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.75},
  annote =	{Keywords: algebraic complexity, factoring, low degree, weight isolation, divisibility}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.25
On the Degree of Polynomials Computing Square Roots Mod p

Authors: Kiran S. Kedlaya and Swastik Kopparty

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
For an odd prime p, we say f(X) ∈ F_p[X] computes square roots in F_p if, for all nonzero perfect squares a ∈ F_p, we have f(a)² = a. When p ≡ 3 mod 4, it is well known that f(X) = X^{(p+1)/4} computes square roots. This degree is surprisingly low (and in fact lowest possible), since we have specified (p-1)/2 evaluations (up to sign) of the polynomial f(X). On the other hand, for p ≡ 1 mod 4 there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in F_p. We show that for all p ≡ 1 mod 4, the degree of a polynomial computing square roots has degree at least p/3. Our main new ingredient is a general lemma which may be of independent interest: powers of a low degree polynomial cannot have too many consecutive zero coefficients. The proof method also yields a robust version: any polynomial that computes square roots for 99% of the squares also has degree almost p/3. In the other direction, Agou, Deliglése, and Nicolas [Agou et al., 2003] showed that for infinitely many p ≡ 1 mod 4, the degree of a polynomial computing square roots can be as small as 3p/8.
Cite as

Kiran S. Kedlaya and Swastik Kopparty. On the Degree of Polynomials Computing Square Roots Mod p. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kedlaya_et_al:LIPIcs.CCC.2024.25,
  author =	{Kedlaya, Kiran S. and Kopparty, Swastik},
  title =	{{On the Degree of Polynomials Computing Square Roots Mod p}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.25},
  URN =		{urn:nbn:de:0030-drops-204219},
  doi =		{10.4230/LIPIcs.CCC.2024.25},
  annote =	{Keywords: Algebraic Computation, Polynomials, Computing Square roots, Reed-Solomon Codes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.31
Low-Depth Algebraic Circuit Lower Bounds over Any Field

Authors: Michael A. Forbes

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
The recent breakthrough of Limaye, Srinivasan and Tavenas [Limaye et al., 2022] (LST) gave the first super-polynomial lower bounds against low-depth algebraic circuits, for any field of zero (or sufficiently large) characteristic. It was an open question to extend this result to small-characteristic ([Limaye et al., 2022; Govindasamy et al., 2022; Fournier et al., 2023]), which in particular is relevant for an approach to prove superpolynomial AC⁰[p]-Frege lower bounds ([Govindasamy et al., 2022]). In this work, we prove super-polynomial algebraic circuit lower bounds against low-depth algebraic circuits over any field, with the same parameters as LST (or even matching the improved parameters of Bhargav, Dutta, and Saxena [Bhargav et al., 2022]). We give two proofs. The first is logical, showing that even though the proof of LST naively fails in small characteristic, the proof is sufficiently algebraic that generic transfer results imply the result over characteristic zero implies the result over all fields. Motivated by this indirect proof, we then proceed to give a second constructive proof, replacing the field-dependent set-multilinearization result of LST with a set-multilinearization that works over any field, by using the Binet-Minc identity [Minc, 1979].
Cite as

Michael A. Forbes. Low-Depth Algebraic Circuit Lower Bounds over Any Field. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{forbes:LIPIcs.CCC.2024.31,
  author =	{Forbes, Michael A.},
  title =	{{Low-Depth Algebraic Circuit Lower Bounds over Any Field}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.31},
  URN =		{urn:nbn:de:0030-drops-204271},
  doi =		{10.4230/LIPIcs.CCC.2024.31},
  annote =	{Keywords: algebraic circuits, lower bounds, low-depth circuits, positive characteristic}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.86
Problems on Group-Labeled Matroid Bases

Authors: Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed.
Cite as

Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz. Problems on Group-Labeled Matroid Bases. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 86:1-86:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{horsch_et_al:LIPIcs.ICALP.2024.86,
  author =	{H\"{o}rsch, Florian and Imolay, Andr\'{a}s and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s},
  title =	{{Problems on Group-Labeled Matroid Bases}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{86:1--86:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.86},
  URN =		{urn:nbn:de:0030-drops-202299},
  doi =		{10.4230/LIPIcs.ICALP.2024.86},
  annote =	{Keywords: matroids, matroid intersection, congruency constraint, exact-weight constraint, additive combinatorics, algebraic algorithm, strongly base orderability}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.16
NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials

Authors: Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
An s-sparse polynomial has at most s monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial f is equivalent to (i.e., in the orbit of) some s-sparse polynomial. In other words, given f ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-3 arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest s₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{1/3 - ε} is NP-hard for any ε > 0; observe that s-factor approximation is trivial as the input is s-sparse. Finally, we show that for any constant σ ≥ 6, checking if a polynomial (given in sparse representation) is in the orbit of some support-σ polynomial is NP-hard. Support of a polynomial f is the maximum number of variables present in any monomial of f. These results are obtained via direct reductions from the 3-SAT problem.
Cite as

Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16,
  author =	{Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit},
  title =	{{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16},
  URN =		{urn:nbn:de:0030-drops-201598},
  doi =		{10.4230/LIPIcs.ICALP.2024.16},
  annote =	{Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.543
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}
}
Document
DOI: 10.4230/DagSemProc.09471.1
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
DOI: 10.4230/DagSemProc.09471.2
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
DOI: 10.4230/DagSemProc.09471.3
Interval Approaches to Reliable Control of Dynamical Systems

Authors: Andreas Rauh and Ekaterina Auer

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

Abstract
Recently, we presented an implementation of interval-based algorithms which can be applied in real-time to control dynamical processes and to estimate internal states and disturbances. The approach is based on verified methods for sets of algebraic equations, ordinary differential equations as well as differential-algebraic equations. Due to this fact, the same program code can be used for two different tasks. On the one hand, we can use it online to estimate non-measurable internal system states which are necessary for nonlinear model-based control strategies. On the other hand, we can verify the admissibility and feasibility of these control strategies offline. Although we use the same code for the online and offline tasks, there is an important difference between them. While the computing time is of minor importance in offline applications, we have to guarantee that the necessary online computations are completed successfully in a predefined time interval. For that reason, the role of verification is slightly different depending on the task. In offline applications, our goal is to compute tightest possible bounds for the sets of all solutions to the control problem under consideration. In contrast to that, we restrict the online mode to a search for a single solution that matches all demands on feasibility of control inputs and admissibility of the trajectories of the state variables in a reliable way. To highlight the practical applicability of the underlying computational routines, we present the following cases for the use of verified solvers in real-time [1-3]. Case 1: Direct computation of feedforward control strategies with the help of differential-algebraic equation solvers. In this application, both verified and non-verified solvers can be used to determine open-loop control strategies for a dynamical system such that its output coincides with a predefined time response within given tolerances. This procedure corresponds to a numerical inversion of the dynamics of the system to be controlled. In this case, verified solvers are used to prove the existence of a control law within given physical bounds for the admissible range of the system inputs. Case 2: If measured data and their time derivatives are available, the same procedures as in case 1 can be used to estimate non-measured state variables as well as non-measurable disturbances. Since the verified algorithms used in this context are capable of propagating bounded measurement uncertainties, the quality of the state and disturbance estimates can be expressed in terms of the resulting interval widths. Moreover, assumptions about the parameters and the structure of the underlying model can be verified. Case 3: Routines for verified sensitivity analysis provide further information on the influence of variations of control inputs on the trajectories of the state variables. We present novel procedures implementing a sensitivity-based framework for model-predictive control. These procedures can be integrated directly in a feedback control structure. Sometimes it is necessary to combine verified and non-verified algorithms to solve a given control problem. In this case, it is important to certify the results of the algorithm appropriately. Based on the four-tier hierarchy presented in earlier works [4], we develop a measure for characterizing such mixed approaches. The presentation is concluded with simulation and experimental results for the example of temperature control of a distributed heating system. [1] Rauh, Andreas; Auer, Ekaterina: Applications of Verified DAE Solvers in Engineering, Intl. Workshop on Verified Computations and Related Topics, COE Lecture Note Vol. 15: Kyushu University, pp. 88-96, Karlsruhe, Germany, 2009. [2] Rauh, Andreas; Menn, Ingolf; Aschemann, Harald: Robust Control with State and Disturbance Estimation for Distributed Parameter Systems, Proc. of 15th Intl. Workshop on Dynamics and Control 2009, pp. 135-142, Tossa de Mar, Spain, 2009. [3] Rauh, Andreas; Auer, Ekaterina; Aschemann, Harald: Real-Time Application of Interval Methods for Robust Control of Dynamical Systems, CD-Proc. of IEEE Intl. Conference on Methods and Models in Automation and Robotics MMAR 2009, Miedzyzdroje, Poland, 2009. [4] Auer, Ekaterina; Luther, Wolfram: Numerical Verification Assessment in Computational Biomechanics, in A. Cuyt, W. Krämer, W. Luther, P. Markstein: Numerical Validation in Current Hardware Architectures, LNCS 5492, pp. 145-160, Springer-Verlag, Berlin, Heidelberg, 2009.
Cite as

Andreas Rauh and Ekaterina Auer. Interval Approaches to Reliable Control of Dynamical Systems. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{rauh_et_al:DagSemProc.09471.3,
  author =	{Rauh, Andreas and Auer, Ekaterina},
  title =	{{Interval Approaches to Reliable Control of Dynamical Systems}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  pages =	{1--28},
  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.3},
  URN =		{urn:nbn:de:0030-drops-25120},
  doi =		{10.4230/DagSemProc.09471.3},
  annote =	{Keywords: Robust control, Ordinary differential equations, Differential-algebraic equations}
}
Document
DOI: 10.4230/DagSemProc.09471.4
Verification and Validation for Femur Prosthesis Surgery

Authors: Ekaterina Auer, Roger Cuypers, Eva Dyllong, Stefan Kiel, and Wolfram Luther

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

Abstract
In this paper, we describe how verified methods we are developing in the course of the project TellHim&S (Interval Based Methods For Adaptive Hierarchical Models In Modeling And Simulation Systems) can be applied in the context of the biomechanical project PROREOP (Development of a new prognosis system to optimize patient-specific pre- operative surgical planning for the human skeletal system). On the one hand, it includes the use of verified hierarchical structures for reliable geometric modeling, object decomposition, distance computation and path planning. On the other hand, we cover such tasks as verification and validation assessment and propagation of differently described uncertainties through system models in engineering or mechanics.
Cite as

Ekaterina Auer, Roger Cuypers, Eva Dyllong, Stefan Kiel, and Wolfram Luther. Verification and Validation for Femur Prosthesis Surgery. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{auer_et_al:DagSemProc.09471.4,
  author =	{Auer, Ekaterina and Cuypers, Roger and Dyllong, Eva and Kiel, Stefan and Luther, Wolfram},
  title =	{{Verification and Validation for Femur Prosthesis Surgery}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  pages =	{1--22},
  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.4},
  URN =		{urn:nbn:de:0030-drops-25133},
  doi =		{10.4230/DagSemProc.09471.4},
  annote =	{Keywords: Graphical interface construction, superquadrics, 3D modeling, biomedical engineering}
}
Document
DOI: 10.4230/DagSemProc.06271.4
Bounds and algebraic algorithms in differential algebra: the ordinary case

Authors: Marc Moreno Maza, Oleg Golubitsky, Marina V. Kondratieva, and Alexey Ovchinnikov

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

Abstract
Consider the Rosenfeld-Groebner algorithm for computing a regular decomposition of a radical differential ideal generated by a set of ordinary differential polynomials. This algorithm inputs a system of differential polynomials and a ranking on derivatives and constructs finitely many regular systems equivalent to the original one. The property of regularity allows to check consistency of the systems and membership to the corresponding differential ideals. We propose a bound on the orders of derivatives occurring in all intermediate and final systems computed by the Rosenfeld-Groebner algorithm and outline its proof. We also reduce the problem of conversion of a regular decomposition of a radical differential ideal from one ranking to another to a purely algebraic problem.
Cite as

Marc Moreno Maza, Oleg Golubitsky, Marina V. Kondratieva, and Alexey Ovchinnikov. Bounds and algebraic algorithms in differential algebra: the ordinary case. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{morenomaza_et_al:DagSemProc.06271.4,
  author =	{Moreno Maza, Marc and Golubitsky, Oleg and Kondratieva, Marina V. and Ovchinnikov, Alexey},
  title =	{{Bounds and algebraic algorithms in differential algebra: the ordinary case}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  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.4},
  URN =		{urn:nbn:de:0030-drops-10219},
  doi =		{10.4230/DagSemProc.06271.4},
  annote =	{Keywords: Differential algebra, Rosenfeld Groebner Algorithm}
}
Document
DOI: 10.4230/DagSemProc.06271.15
Two Families of Algorithms for Symbolic Polynomials

Authors: Stephen M. Watt

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

Abstract
We wish to work with polynomials where the exponents are not known in advance, such as $x^{2n} - 1$. There are various operations we will want to be able to do, such as squaring the value to get $x^{4n}-2x^{2n}+1$, or differentiating it to get $2nx^{2n-1}$. Expressions of this sort arise frequently in practice, for example in the analysis of algorithms, and it is very difficult to work with them effectively in current computer algebra systems. We consider the case where multivariate polynomials can have exponents which are themselves integer-valued multivariate polynomials, and we present algorithms to compute their GCD and factorization. The algorithms fall into two families: algebraic extension methods and interpolation methods. The first family of algorithms uses the algebraic independence of $x$, $x^n$, $x^{n^2}$, $x^{nm}, etc, to solve related problems with more indeterminates. Some subtlety is needed to avoid problems with fixed divisors of the exponent polynomials. The second family of algorithms uses evaluation and interpolation of the exponent polynomials. While these methods can run into unlucky evaluation points, in many cases they can be more appealing. Additionally, we also treat the case of symbolic exponents on rational coefficients (e.g. $4^{n^2+n}-81$) and show how to avoid integer factorization.
Cite as

Stephen M. Watt. Two Families of Algorithms for Symbolic Polynomials. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{watt:DagSemProc.06271.15,
  author =	{Watt, Stephen M.},
  title =	{{Two Families of Algorithms for Symbolic Polynomials}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--20},
  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.15},
  URN =		{urn:nbn:de:0030-drops-7933},
  doi =		{10.4230/DagSemProc.06271.15},
  annote =	{Keywords: Computer algebra, symbolic computation, factorization, gcd, symbolic exponents}
}
Document
DOI: 10.4230/DagSemProc.06271.1
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
DOI: 10.4230/DagSemProc.06271.13
Pivot-Free Block Matrix Inversion

Authors: Stephen M. Watt

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

Abstract
We present a pivot-free deterministic algorithm for the inversion of block matrices. The method is based on the Moore-Penrose inverse and is applicable over certain general classes of rings. This improves on previous methods that required at least one invertible on-diagonal block, and that otherwise required row- or column-based pivoting, disrupting the block structure. Our method is applicable to any invertible matrix and does not require any particular blocks to invertible. This is achieved at the cost of two additional specialized matrix multiplications and, in some cases, requires the inversion to be performed in an extended ring.
Cite as

Stephen M. Watt. Pivot-Free Block Matrix Inversion. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{watt:DagSemProc.06271.13,
  author =	{Watt, Stephen M.},
  title =	{{Pivot-Free Block Matrix Inversion}},
  booktitle =	{Challenges in Symbolic Computation Software},
  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.13},
  URN =		{urn:nbn:de:0030-drops-7806},
  doi =		{10.4230/DagSemProc.06271.13},
  annote =	{Keywords: Linear algebra, block matrices, matrix inverse}
}
  • Refine by Author
  • 5 Watt, Stephen M.
  • 4 Kaltofen, Erich
  • 2 Auer, Ekaterina
  • 2 Brown, Malcolm B.
  • 2 Decker, Wolfram
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Algebraic complexity theory
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Computing methodologies → Number theory algorithms
  • 1 Computing methodologies → Representation of mathematical functions
  • 1 Mathematics of computing → Coding theory
  • Show More...

  • Refine by Keyword
  • 4 computer algebra
  • 2 Symbolic computation
  • 2 Verification methods
  • 2 algebraic complexity
  • 2 combinatorial methods in algebra
  • Show More...

  • Refine by Type
  • 27 document

  • Refine by Publication Year
  • 15 2006
  • 6 2024
  • 4 2010
  • 1 2007
  • 1 2011

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 Imprint Privacy Contact