7 Search Results for "de Vries, Gert-Jan"


Document
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors

Authors: Harm Derksen, Visu Makam, and Jeroen Zuiddam

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
Since the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to understand which algebraic problems (be it bilinear maps like matrix multiplication in Strassen’s work, or the determinant and permanent polynomials in Valiant’s) can be reduced to each other (under the appropriate notion of reduction). In this paper we work in the setting of bilinear maps and with the usual notion of reduction that allows applying linear maps to the inputs and output of a bilinear map in order to compute another bilinear map. As our main result we determine precisely how many independent scalar multiplications can be reduced to a given bilinear map (this number is called the subrank, and extends the concept of matrix diagonalization to tensors), for essentially all (i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map T : V × V → V where dim(V) = n that θ(√n) independent scalar multiplications can be reduced to T. Our result significantly improves on the previous upper bound from the work of Strassen (1991) and Bürgisser (1990) which was n^{2/3 + o(1)}. Our result is very precise and tight up to an additive constant. Our full result is much more general and applies not only to bilinear maps and 3-tensors but also to k-tensors, for which we find that the generic subrank is θ(n^{1/(k-1)}). Moreover, as an application we prove that the subrank is not additive under the direct sum. The subrank plays a central role in several areas of complexity theory (matrix multiplication algorithms, barrier results) and combinatorics (e.g., the cap set problem and sunflower problem). As a consequence of our result we obtain several large separations between the subrank and tensor methods that have received much interest recently, notably the slice rank (Tao, 2016), analytic rank (Gowers-Wolf, 2011; Lovett, 2018; Bhrushundi-Harsha-Hatami-Kopparty-Kumar, 2020), geometric rank (Kopparty-Moshkovitz-Zuiddam, 2020), and G-stable rank (Derksen, 2020). Our proofs of the lower bounds rely on a new technical result about an optimal decomposition of tensor space into structured subspaces, which we think may be of independent interest.

Cite as

Harm Derksen, Visu Makam, and Jeroen Zuiddam. Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{derksen_et_al:LIPIcs.CCC.2022.9,
  author =	{Derksen, Harm and Makam, Visu and Zuiddam, Jeroen},
  title =	{{Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.9},
  URN =		{urn:nbn:de:0030-drops-165716},
  doi =		{10.4230/LIPIcs.CCC.2022.9},
  annote =	{Keywords: tensors, bilinear maps, complexity, subrank, diagonalization, generic tensors, random tensors, reduction, slice rank}
}
Document
PACE Solver Description
PACE Solver Description: tdULL

Authors: Ruben Brokkelkamp, Raymond van Venetië, Mees de Vries, and Jan Westerdiep

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
We describe tdULL, an algorithm for computing treedepth decompositions of minimal depth. An implementation was submitted to the exact track of PACE 2020. tdULL is a branch and bound algorithm branching on inclusion-minimal separators.

Cite as

Ruben Brokkelkamp, Raymond van Venetië, Mees de Vries, and Jan Westerdiep. PACE Solver Description: tdULL. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 29:1-29:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{brokkelkamp_et_al:LIPIcs.IPEC.2020.29,
  author =	{Brokkelkamp, Ruben and van Veneti\"{e}, Raymond and de Vries, Mees and Westerdiep, Jan},
  title =	{{PACE Solver Description: tdULL}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{29:1--29:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.29},
  URN =		{urn:nbn:de:0030-drops-133326},
  doi =		{10.4230/LIPIcs.IPEC.2020.29},
  annote =	{Keywords: PACE 2020, treedepth, treedepth decomposition, vertex ranking, minimal separators, branch and bound}
}
Document
On Undefined and Meaningless in Lambda Definability

Authors: Fer-Jan de Vries

Published in: LIPIcs, Volume 52, 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)


Abstract
We distinguish between undefined terms as used in lambda definability of partial recursive functions and meaningless terms as used in infinite lambda calculus for the infinitary terms models that generalise the Bohm model. While there are uncountable many known sets of meaningless terms, there are four known sets of undefined terms. Two of these four are sets of meaningless terms. In this paper we first present set of sufficient conditions for a set of lambda terms to serve as set of undefined terms in lambda definability of partial functions. The four known sets of undefined terms satisfy these conditions. Next we locate the smallest set of meaningless terms satisfying these conditions. This set sits very low in the lattice of all sets of meaningless terms. Any larger set of meaningless terms than this smallest set is a set of undefined terms. Thus we find uncountably many new sets of undefined terms. As an unexpected bonus of our careful analysis of lambda definability we obtain a natural modification, strict lambda-definability, which allows for a Barendregt style of proof in which the representation of composition is truly the composition of representations.

Cite as

Fer-Jan de Vries. On Undefined and Meaningless in Lambda Definability. In 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 52, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{devries:LIPIcs.FSCD.2016.18,
  author =	{de Vries, Fer-Jan},
  title =	{{On Undefined and Meaningless in Lambda Definability}},
  booktitle =	{1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-010-1},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{52},
  editor =	{Kesner, Delia and Pientka, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2016.18},
  URN =		{urn:nbn:de:0030-drops-59785},
  doi =		{10.4230/LIPIcs.FSCD.2016.18},
  annote =	{Keywords: lambda calculus, lambda definability, partial recursive function, undefined term, meaningless term}
}
Document
Approximation of Nested Fixpoints – A Coalgebraic View of Parametric Dataypes

Authors: Alexander Kurz, Alberto Pardo, Daniela Petrisan, Paula Severi, and Fer-Jan de Vries

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)


Abstract
The question addressed in this paper is how to correctly approximate infinite data given by systems of simultaneous corecursive definitions. We devise a categorical framework for reasoning about regular datatypes, that is, datatypes closed under products, coproducts and fixpoints. We argue that the right methodology is on one hand coalgebraic (to deal with possible nontermination and infinite data) and on the other hand 2-categorical (to deal with parameters in a disciplined manner). We prove a coalgebraic version of Bekic lemma that allows us to reduce simultaneous fixpoints to a single fix point. Thus a possibly infinite object of interest is regarded as a final coalgebra of a many-sorted polynomial functor and can be seen as a limit of finite approximants. As an application, we prove correctness of a generic function that calculates the approximants on a large class of data types.

Cite as

Alexander Kurz, Alberto Pardo, Daniela Petrisan, Paula Severi, and Fer-Jan de Vries. Approximation of Nested Fixpoints – A Coalgebraic View of Parametric Dataypes. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 205-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{kurz_et_al:LIPIcs.CALCO.2015.205,
  author =	{Kurz, Alexander and Pardo, Alberto and Petrisan, Daniela and Severi, Paula and de Vries, Fer-Jan},
  title =	{{Approximation of Nested Fixpoints – A Coalgebraic View of Parametric Dataypes}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{205--220},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.205},
  URN =		{urn:nbn:de:0030-drops-55351},
  doi =		{10.4230/LIPIcs.CALCO.2015.205},
  annote =	{Keywords: coalgebra, Bekic lemma, infinite data, functional programming, type theory}
}
Document
Meaningless Sets in Infinitary Combinatory Logic

Authors: Paula Severi and Fer-Jan de Vries

Published in: LIPIcs, Volume 15, 23rd International Conference on Rewriting Techniques and Applications (RTA'12) (2012)


Abstract
In this paper we study meaningless sets in infinitary combinatory logic. So far only a handful of meaningless sets were known. We show that there are uncountably many meaningless sets. As an application to the semantics of finite combinatory logics, we show that there exist uncountably many combinatory algebras that are not a lambda algebra. We also study ways of weakening the axioms of meaningless sets to get, not only sufficient, but also necessary conditions for having confluence and normalisation.

Cite as

Paula Severi and Fer-Jan de Vries. Meaningless Sets in Infinitary Combinatory Logic. In 23rd International Conference on Rewriting Techniques and Applications (RTA'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 15, pp. 288-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{severi_et_al:LIPIcs.RTA.2012.288,
  author =	{Severi, Paula and de Vries, Fer-Jan},
  title =	{{Meaningless Sets in Infinitary Combinatory Logic}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12)},
  pages =	{288--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-38-5},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{15},
  editor =	{Tiwari, Ashish},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2012.288},
  URN =		{urn:nbn:de:0030-drops-34993},
  doi =		{10.4230/LIPIcs.RTA.2012.288},
  annote =	{Keywords: Infinitary Rewriting, Combinatory Logic, Meaningless Sets, Confluence, Normalisation}
}
Document
Weakening the Axiom of Overlap in Infinitary Lambda Calculus

Authors: Paula Severi and Fer-Jan de Vries

Published in: LIPIcs, Volume 10, 22nd International Conference on Rewriting Techniques and Applications (RTA'11) (2011)


Abstract
In this paper we present a set of necessary and sufficient conditions on a set of lambda terms to serve as the set of meaningless terms in an infinitary bottom extension of lambda calculus. So far only a set of sufficient conditions was known for choosing a suitable set of meaningless terms to make this construction produce confluent extensions. The conditions covered the three main known examples of sets of meaningless terms. However, the much later construction of many more examples of sets of meaningless terms satisfying the sufficient conditions renewed the interest in the necessity question and led us to reconsider the old conditions. The key idea in this paper is an alternative solution for solving the overlap between beta reduction and bottom reduction. This allows us to reformulate the Axiom of Overlap, which now determines together with the other conditions a larger class of sets of meaningless terms. We show that the reformulated conditions are not only sufficient but also necessary for obtaining a confluent and normalizing infinitary lambda beta bottom calculus. As an interesting consequence of the necessity proof we obtain for infinitary lambda calculus with beta and bot reduction that confluence implies normalization.

Cite as

Paula Severi and Fer-Jan de Vries. Weakening the Axiom of Overlap in Infinitary Lambda Calculus. In 22nd International Conference on Rewriting Techniques and Applications (RTA'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 10, pp. 313-328, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{severi_et_al:LIPIcs.RTA.2011.313,
  author =	{Severi, Paula and de Vries, Fer-Jan},
  title =	{{Weakening the Axiom of Overlap in Infinitary Lambda Calculus}},
  booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
  pages =	{313--328},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-30-9},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{10},
  editor =	{Schmidt-Schauss, Manfred},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2011.313},
  URN =		{urn:nbn:de:0030-drops-31312},
  doi =		{10.4230/LIPIcs.RTA.2011.313},
  annote =	{Keywords: Infinitary Lambda Calculus, Confluence, Normalization}
}
Document
Analysis of Robust Soft Learning Vector Quantization and an application to Facial Expression Recognition

Authors: Gert-Jan de Vries and Michael Biehl

Published in: Dagstuhl Seminar Proceedings, Volume 9081, Similarity-based learning on structures (2009)


Abstract
Learning Vector Quantization (LVQ) is a popular method for multiclass classification. Several variants of LVQ have been developed recently, of which Robust Soft Learning Vector Quantization (RSLVQ) is a promising one. Although LVQ methods have an intuitive design with clear updating rules, their dynamics are not yet well understood. In simulations within a controlled environment RSLVQ performed very close to optimal. This controlled environment enabled us to perform a mathematical analysis as a first step in obtaining a better theoretical understanding of the learning dynamics. In this talk I will discuss the theoretical analysis and its results. Moreover, I will focus on the practical application of RSLVQ to a real world dataset containing extracted features from facial expression data.

Cite as

Gert-Jan de Vries and Michael Biehl. Analysis of Robust Soft Learning Vector Quantization and an application to Facial Expression Recognition. In Similarity-based learning on structures. Dagstuhl Seminar Proceedings, Volume 9081, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{devries_et_al:DagSemProc.09081.4,
  author =	{de Vries, Gert-Jan and Biehl, Michael},
  title =	{{Analysis of Robust Soft Learning Vector Quantization and an application to Facial Expression Recognition}},
  booktitle =	{Similarity-based learning on structures},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9081},
  editor =	{Michael Biehl and Barbara Hammer and Sepp Hochreiter and Stefan C. Kremer and Thomas Villmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09081.4},
  URN =		{urn:nbn:de:0030-drops-20356},
  doi =		{10.4230/DagSemProc.09081.4},
  annote =	{Keywords: Learning Vector Quantization, Analysis, Facial Expression Recognition}
}
  • Refine by Author
  • 4 de Vries, Fer-Jan
  • 3 Severi, Paula
  • 1 Biehl, Michael
  • 1 Brokkelkamp, Ruben
  • 1 Derksen, Harm
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 2 Confluence
  • 1 Analysis
  • 1 Bekic lemma
  • 1 Combinatory Logic
  • 1 Facial Expression Recognition
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 1 2009
  • 1 2011
  • 1 2012
  • 1 2015
  • 1 2016
  • Show More...

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