Zobrazeno 1 - 10
of 5 998
pro vyhledávání: '"algebraic complexity"'
Autor:
Bürgisser, Peter
The purpose of this overview is to explain the enormous impact of Les Valiant's eponymous short conference contribution from 1979 on the development of algebraic complexity.
Comment: 49 pages, 4 figures. To appear in "Foundations of Computation
Comment: 49 pages, 4 figures. To appear in "Foundations of Computation
Externí odkaz:
http://arxiv.org/abs/2406.06217
Autor:
Shahverdi, Vahid
In this paper, we study linear convolutional networks with one-dimensional filters and arbitrary strides. The neuromanifold of such a network is a semialgebraic set, represented by a space of polynomials admitting specific factorizations. Introducing
Externí odkaz:
http://arxiv.org/abs/2401.16613
Publikováno v:
15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pp. 43:1-43:23
We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet m
Externí odkaz:
http://arxiv.org/abs/2311.17019
On the minimal algebraic complexity of the rank-one approximation problem for general inner products
We study the algebraic complexity of Euclidean distance minimization from a generic tensor to a variety of rank-one tensors. The Euclidean Distance (ED) degree of the Segre-Veronese variety counts the number of complex critical points of this optimiz
Externí odkaz:
http://arxiv.org/abs/2309.15105
Autor:
Garg, Ankit, Ikenmeyer, Christian, Makam, Visu, Oliveira, Rafael, Walter, Michael, Wigderson, Avi
Publikováno v:
35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics, vol. 169, 2020, pp. 12:1 - 12:17
We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized such encodings for invariant rings of $\SL_n(\C)$-representations. We pr
Externí odkaz:
http://arxiv.org/abs/1910.01251
Autor:
Mahajan, Meena, Saurabh, Nitin
We provide a list of new natural $\mathsf{VNP}$-intermediate polynomial families, based on basic (combinatorial) $\mathsf{NP}$-complete problems that are complete under parsimonious reductions. Over finite fields, these families are in $\mathsf{VNP}$
Externí odkaz:
http://arxiv.org/abs/1603.04606
Computing Delaunay triangulations in $\mathbb{R}^d$ involves evaluating the so-called in\_sphere predicate that determines if a point $x$ lies inside, on or outside the sphere circumscribing $d+1$ points $p_0,\ldots ,p_d$. This predicate reduces to e
Externí odkaz:
http://arxiv.org/abs/1505.05454
The algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century that metamathematical problems have led to the in