Zobrazeno 1 - 10
of 590
pro vyhledávání: '"Shpilka, A."'
Autor:
Arazi, Leah London, Shpilka, Amir
This paper studies the hazard-free formula complexity of Boolean functions. As our main result, we prove that unate functions are the only Boolean functions for which the monotone formula complexity of the hazard-derivative equals the hazard-free for
Externí odkaz:
http://arxiv.org/abs/2411.09026
In this paper, we prove super-polynomial lower bounds for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering ($\sum \mathsf{smABP}$). Specifically, we give an explicit $nd$-variate
Externí odkaz:
http://arxiv.org/abs/2312.15874
Constructing Reed--Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. For the special case of two-dimensional RS-codes, it is known [CST23] that an $[n,2]_q$ RS-code that can cor
Externí odkaz:
http://arxiv.org/abs/2311.02771
Autor:
Nahshon, Ido, Shpilka, Amir
We prove that for monic polynomials $f, g \in \mathbb{C}[x]$ such that $g$ divides $f$, the $\ell_2$-norm of the quotient polynomial $f/g$ is bounded by $\lVert f \rVert_1 \cdot \tilde{O}(\lVert{g}\rVert_0^3\text{deg}^2{ f})^{\lVert{g}\rVert_0 - 1}$.
Externí odkaz:
http://arxiv.org/abs/2308.03885
Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic complexity theory (constructing fast matrix multiplication algorithms)
Externí odkaz:
http://arxiv.org/abs/2306.01718
We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box ac
Externí odkaz:
http://arxiv.org/abs/2209.04177
We say that two given polynomials $f, g \in R[X]$, over a ring $R$, are equivalent under shifts if there exists a vector $a \in R^n$ such that $f(X+a) = g(X)$. Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SICOMP, 1995), and Grigoriev a
Externí odkaz:
http://arxiv.org/abs/2207.10588
Autor:
Peleg, Shir, Shpilka, Amir
In this work, we extend the robust version of the Sylvester-Gallai theorem, obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and Wigderson, to the case of quadratic polynomials. Specifically, we prove that if $\mathcal{Q}\subset
Externí odkaz:
http://arxiv.org/abs/2202.04932
In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over $\mathbb{F}_q$, for $q=\text{poly}(1/\varepsilon)$, that
Externí odkaz:
http://arxiv.org/abs/2201.06130
In this work, we study the performance of Reed--Solomon codes against adversarial insertion-deletion (insdel) errors. We prove that over fields of size $n^{O(k)}$ there are $[n,k]$ Reed-Solomon codes that can decode from $n-2k+1$ insdel errors and he
Externí odkaz:
http://arxiv.org/abs/2107.05699