4 Search Results for "Little, Thomas C."

Document
DOI: 10.4230/LIPIcs.ITCS.2020.10
Kronecker Powers of Tensors and Strassen’s Laser Method

Authors: Austin Conner, Joseph M. Landsberg, Fulvio Gesmundo, and Emanuele Ventura

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We answer a question, posed implicitly in [P. Bürgisser et al., 1997] and explicitly in [M. Bläser, 2013], showing the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of the border rank of the tensor for all q>2, a negative result for complexity theory. We further show that when q>4, the analogous result holds for the Kronecker cube. In the positive direction, we enlarge the list of explicit tensors potentially useful for the laser method. We observe that a well-known tensor, the 3 × 3 determinant polynomial regarded as a tensor, det_3 ∈ C^9 ⊗ C^9 ⊗ C^9, could potentially be used in the laser method to prove the exponent of matrix multiplication is two. Because of this, we prove new upper bounds on its Waring rank and rank (both 18), border rank and Waring border rank (both 17), which, in addition to being promising for the laser method, are of interest in their own right. We discuss "skew" cousins of the little Coppersmith-Winograd tensor and indicate why they may be useful for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C^3 ⊗ C^3 ⊗ C^3.
Cite as

Austin Conner, Joseph M. Landsberg, Fulvio Gesmundo, and Emanuele Ventura. Kronecker Powers of Tensors and Strassen’s Laser Method. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 10:1-10:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{conner_et_al:LIPIcs.ITCS.2020.10,
  author =	{Conner, Austin and Landsberg, Joseph M. and Gesmundo, Fulvio and Ventura, Emanuele},
  title =	{{Kronecker Powers of Tensors and Strassen’s Laser Method}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{10:1--10:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.10},
  URN =		{urn:nbn:de:0030-drops-116956},
  doi =		{10.4230/LIPIcs.ITCS.2020.10},
  annote =	{Keywords: Matrix multiplication complexity, Tensor rank, Asymptotic rank, Laser method}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.100
Balanced Partitions of Trees and Applications

Authors: Andreas Emil Feldmann and Luca Foschini

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We study the k-BALANCED PARTITIONING problem in which the vertices of a graph are to be partitioned into k sets of size at most ceil(n/k) while minimising the cut size, which is the number of edges connecting vertices in different sets. The problem is well studied for general graphs, for which it cannot be approximated within any factor in polynomial time. However, little is known about restricted graph classes. We show that for trees k-BALANCED PARTITIONING remains surprisingly hard. In particular, approximating the cut size is APX-hard even if the maximum degree of the tree is constant. If instead the diameter of the tree is bounded by a constant, we show that it is NP-hard to approximate the cut size within n^c, for any constant c<1. In the face of the hardness results, we show that allowing near-balanced solutions, in which there are at most (1+eps)ceil(n/k) vertices in any of the k sets, admits a PTAS for trees. Remarkably, the computed cut size is no larger than that of an optimal balanced solution. In the final section of our paper, we harness results on embedding graph metrics into tree metrics to extend our PTAS for trees to general graphs. In addition to being conceptually simpler and easier to analyse, our scheme improves the best factor known on the cut size of near-balanced solutions from O(log^{1.5}(n)/eps^2) [Andreev and Räcke TCS 2006] to 0(log n), for weighted graphs. This also settles a question posed by Andreev and Räcke of whether an algorithm with approximation guarantees on the cut size independent from eps exists.
Cite as

Andreas Emil Feldmann and Luca Foschini. Balanced Partitions of Trees and Applications. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 100-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{feldmann_et_al:LIPIcs.STACS.2012.100,
  author =	{Feldmann, Andreas Emil and Foschini, Luca},
  title =	{{Balanced Partitions of Trees and Applications}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{100--111},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.100},
  URN =		{urn:nbn:de:0030-drops-34081},
  doi =		{10.4230/LIPIcs.STACS.2012.100},
  annote =	{Keywords: balanced partitioning, bicriteria approximation, hardness of approximation, tree embeddings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2484
An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem

Authors: François Le Gall

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
In this paper we consider the problem of testing whether two finite groups are isomorphic. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. Le Gall has constructed an efficient classical algorithm for a class of groups corresponding to one of the most natural ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group $A$ by a cyclic group $\Int_m$ with the order of $A$ coprime with $m$. More precisely, the running time of that algorithm is almost linear in the order of the input groups. In this paper we present a \emph{quantum} algorithm solving the same problem in time polynomial in the \emph{logarithm} of the order of the input groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian group isomorphism problem exponentially faster than the best known classical algorithms.
Cite as

François Le Gall. An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 549-560, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{legall:LIPIcs.STACS.2010.2484,
  author =	{Le Gall, Fran\c{c}ois},
  title =	{{An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{549--560},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2484},
  URN =		{urn:nbn:de:0030-drops-24843},
  doi =		{10.4230/LIPIcs.STACS.2010.2484},
  annote =	{Keywords: Quantum algorithms, group isomorphism problem, black-box groups}
}
Document
DOI: 10.4230/DagSemRep.184
Multimedia Synchronization and Resource Management in Advanced Multimedia Environments (Dagstuhl Seminar 9727)

Authors: Nicolas Georganas, Thomas C. Little, Kurt Rothermel, and Ralf Steinmetz

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

Abstract
Cite as

Nicolas Georganas, Thomas C. Little, Kurt Rothermel, and Ralf Steinmetz. Multimedia Synchronization and Resource Management in Advanced Multimedia Environments (Dagstuhl Seminar 9727). Dagstuhl Seminar Report 184, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{georganas_et_al:DagSemRep.184,
  author =	{Georganas, Nicolas and Little, Thomas C. and Rothermel, Kurt and Steinmetz, Ralf},
  title =	{{Multimedia Synchronization and Resource Management in Advanced Multimedia Environments (Dagstuhl Seminar 9727)}},
  pages =	{1--14},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{184},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.184},
  URN =		{urn:nbn:de:0030-drops-150718},
  doi =		{10.4230/DagSemRep.184},
}
  • Refine by Author
  • 1 Conner, Austin
  • 1 Feldmann, Andreas Emil
  • 1 Foschini, Luca
  • 1 Georganas, Nicolas
  • 1 Gesmundo, Fulvio
  • Show More...

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

  • Refine by Keyword
  • 1 Asymptotic rank
  • 1 Laser method
  • 1 Matrix multiplication complexity
  • 1 Quantum algorithms
  • 1 Tensor rank
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 1997
  • 1 2010
  • 1 2012
  • 1 2020

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