Zobrazeno 1 - 10
of 62
pro vyhledávání: '"Kayal, Neeraj"'
We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of
Externí odkaz:
http://arxiv.org/abs/2311.07284
We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [K
Externí odkaz:
http://arxiv.org/abs/2211.07691
We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can be written as $$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$ where each $c_i\in \mathbb{F}^{\times}$,
Externí odkaz:
http://arxiv.org/abs/2004.06898
We give a new elementary proof of the fact that the value of the least $k^{th}$ power non-residue in an arithmetic progression $\{bn+c\}_{n=0,1...}$, over a prime field $\F_p$, is bounded by $7/\sqrt{5} \cdot b \cdot \sqrt{p/k} + 4b + c$. Our proof i
Externí odkaz:
http://arxiv.org/abs/1104.4557
Publikováno v:
Annals of Mathematics, 2004 Sep 01. 160(2), 781-793.
Externí odkaz:
https://www.jstor.org/stable/3597229
Consider a homogeneous degree d polynomial f = T₁ + ⋯ + T_s, T_i = g_i(𝓁_{i,1}, …, 𝓁_{i, m}) where g_i’s are homogeneous m-variate degree d polynomials and 𝓁_{i,j}’s are linear polynomials in n variables. We design a (randomized) l
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c742ec0698b9a4af3f6f26a9de90ab03
Autor:
Kayal, Neeraj1 neeraka@microsoft.com, Saha, Chandan2 ch.saha@gmail.com
Publikováno v:
Theory of Computing Systems. Nov2017, Vol. 61 Issue 4, p1237-1251. 15p.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
The determinant polynomial Det_n(x) of degree n is the determinant of a n x n matrix of formal variables. A polynomial f is equivalent to Det_n(x) over a field F if there exists a A in GL(n^2,F) such that f = Det_n(A * x). Determinant equivalence tes
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::90acd0772aebfc8f3524a9a0cc4b8ec8
Publikováno v:
Theory of Computing
Theory of Computing, University of Chicago, Department of Computer Science, 2018, 14 (1), pp.1-46. ⟨10.4086/toc.2018.v014a016⟩
Theory of Computing, University of Chicago, Department of Computer Science, 2018, 14 (1), pp.1-46. ⟨10.4086/toc.2018.v014a016⟩
Let r >= 1 be an integer. Let us call a polynomial f (x(1), x(2),..., x(N)) is an element of Fx] a multi-r-ic polynomial if the degree of f with respect to any variable is at most r. (This generalizes the notion of multilinear polynomials.) We invest
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::a94f2b67889ab9a190e937720d32dad3
https://doi.org/10.4086/toc.2018.v014a016
https://doi.org/10.4086/toc.2018.v014a016