The Experts below are selected from a list of 674889 Experts worldwide ranked by ideXlab platform
Amir Shpilka - One of the best experts on this subject based on the ideXlab platform.
-
sylvester gallai type theorems for quadratic Polynomials
Symposium on the Theory of Computing, 2019Co-Authors: Amir ShpilkaAbstract:We prove Sylvester-Gallai type theorems for quadratic Polynomials. Specifically, we prove that if a finite collection Q, of irreducible Polynomials of degree at most 2, satisfy that for every two Polynomials Q1,Q2∈ Q there is a third Polynomial Q3∈Q so that whenever Q1 and Q2 vanish then also Q3 vanishes, then the linear span of the Polynomials in Q has dimension O(1). We also prove a colored version of the theorem: If three finite sets of quadratic Polynomials satisfy that for every two Polynomials from distinct sets there is a Polynomial in the third set satisfying the same vanishing condition then all Polynomials are contained in an O(1)-dimensional space. This answers affirmatively two conjectures of Gupta [Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014] that were raised in the context of solving certain depth-4 Polynomial identities. To obtain our main theorems we prove a new result classifying the possible ways that a quadratic Polynomial Q can vanish when two other quadratic Polynomials vanish. Our proofs also require robust versions of a theorem of Edelstein and Kelly (that extends the Sylvester-Gallai theorem to colored sets).
-
Sylvester-Gallai type theorems for quadratic Polynomials
arXiv: Combinatorics, 2019Co-Authors: Amir ShpilkaAbstract:We prove Sylvester-Gallai type theorems for quadratic Polynomials. Specifically, we prove that if a finite collection $\mathcal Q$, of irreducible Polynomials of degree at most $2$, satisfy that for every two Polynomials $Q_1,Q_2\in {\mathcal Q}$ there is a third Polynomial $Q_3\in{\mathcal Q}$ so that whenever $Q_1$ and $Q_2$ vanish then also $Q_3$ vanishes, then the linear span of the Polynomials in ${\mathcal Q}$ has dimension $O(1)$. We also prove a colored version of the theorem: If three finite sets of quadratic Polynomials satisfy that for every two Polynomials from distinct sets there is a Polynomial in the third set satisfying the same vanishing condition then all Polynomials are contained in an $O(1)$-dimensional space. This answers affirmatively two conjectures of Gupta [ECCC 2014] that were raised in the context of solving certain depth-$4$ Polynomial identities. To obtain our main theorems we prove a new result classifying the possible ways that a quadratic Polynomial $Q$ can vanish when two other quadratic Polynomials vanish. Our proofs also require robust versions of a theorem of Edelstein and Kelly (that extends the Sylvester-Gallai theorem to colored sets).
-
on the relation between Polynomial identity testing and finding variable disjoint factors
International Colloquium on Automata Languages and Programming, 2010Co-Authors: Amir Shpilka, Ilya VolkovichAbstract:We say that a Polynomial f(x1, ..., xn) is indecomposable if it cannot be written as a product of two Polynomials that are defined over disjoint sets of variables. The Polynomial decomposition problem is defined to be the task of finding the indecomposable factors of a given Polynomial. Note that for multilinear Polynomials, factorization is the same as decomposition, as any two different factors are variable disjoint. In this paper we show that the problem of derandomizing Polynomial identity testing is essentially equivalent to the problem of derandomizing algorithms for Polynomial decomposition. More accurately, we show that for any reasonable circuit class there is a deterministic Polynomial time (black-box) algorithm for Polynomial identity testing of that class if and only if there is a deterministic Polynomial time (black-box) algorithm for factoring a Polynomial, computed in the class, to its indecomposable components. An immediate corollary is that Polynomial identity testing and Polynomial factorization are equivalent (up to a Polynomial overhead) for multilinear Polynomials. In addition, we observe that derandomizing the Polynomial decomposition problem is equivalent, in the sense of Kabanets and Impagliazzo [1], to proving arithmetic circuit lower bounds for NEXP. Our approach uses ideas from [2], that showed that the Polynomial identity testing problem for a circuit class C is essentially equivalent to the problem of deciding whether a circuit from C computes a Polynomial that has a read-once arithmetic formula.
-
on the relation between Polynomial identity testing and finding variable disjoint factors
International Colloquium on Automata Languages and Programming, 2010Co-Authors: Amir Shpilka, Ilya VolkovichAbstract:We say that a Polynomial f(x1, ..., xn) is indecomposable if it cannot be written as a product of two Polynomials that are defined over disjoint sets of variables. The Polynomial decomposition problem is defined to be the task of finding the indecomposable factors of a given Polynomial. Note that for multilinear Polynomials, factorization is the same as decomposition, as any two different factors are variable disjoint. In this paper we show that the problem of derandomizing Polynomial identity testing is essentially equivalent to the problem of derandomizing algorithms for Polynomial decomposition. More accurately, we show that for any reasonable circuit class there is a deterministic Polynomial time (black-box) algorithm for Polynomial identity testing of that class if and only if there is a deterministic Polynomial time (black-box) algorithm for factoring a Polynomial, computed in the class, to its indecomposable components. An immediate corollary is that Polynomial identity testing and Polynomial factorization are equivalent (up to a Polynomial overhead) for multilinear Polynomials. In addition, we observe that derandomizing the Polynomial decomposition problem is equivalent, in the sense of Kabanets and Impagliazzo [1], to proving arithmetic circuit lower bounds for NEXP. Our approach uses ideas from [2], that showed that the Polynomial identity testing problem for a circuit class C is essentially equivalent to the problem of deciding whether a circuit from C computes a Polynomial that has a read-once arithmetic formula.
Zhixiang Chen - One of the best experts on this subject based on the ideXlab platform.
-
approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate Polynomials
Journal of Combinatorial Optimization, 2013Co-Authors: Zhixiang ChenAbstract:This paper is our third step towards developing a theory of testing monomials in multivariate Polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a ?Σ? Polynomial. We first prove that the first problem is #P-hard and then devise a O ?(3 n s(n)) upper bound for this problem for any Polynomial represented by an arithmetic circuit of size s(n). Later, this upper bound is improved to O ?(2 n ) for ?Σ? Polynomials. We then design fully Polynomial-time randomized approximation schemes for this problem for ?Σ Polynomials. On the negative side, we prove that, even for ?Σ? Polynomials with terms of degree ?2, the first problem cannot be approximated at all for any approximation factor ?1, nor "weakly approximated" in a much relaxed setting, unless P=NP. For the second problem, we first give a Polynomial time ?-approximation algorithm for ?Σ? Polynomials with terms of degrees no more a constant ??2. On the inapproximability side, we give a n (1??)/2 lower bound, for any ?>0, on the approximation factor for ?Σ? Polynomials. When terms in these Polynomials are constrained to degrees ?2, we prove a 1.0476 lower bound, assuming P?NP; and a higher 1.0604 lower bound, assuming the Unique Games Conjecture.
-
approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate Polynomials
Conference on Combinatorial Optimization and Applications, 2010Co-Authors: Zhixiang ChenAbstract:This paper is our third step towards developing a theory of testing monomials in multivariate Polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a ΠΣΠ Polynomial. We first prove that the first problem is #P-hard and then devise a O*(3n s(n)) upper bound for this problem for any Polynomial represented by an arithmetic circuit of size s(n). Later, this upper bound is improved to O*(2n) for ΠΣΠ Polynomials. We then design fully Polynomial-time randomized approximation schemes for this problem for ΠΣ Polynomials. On the negative side, we prove that, even for ΠΣΠ Polynomials with terms of degree ≤ 2, the first problem cannot be approximated at all for any approximation factor ≥ 1, nor "weakly approximated" in a much relaxed setting, unless P=NP. For the second problem, we first give a Polynomial time λ-approximation algorithm for ΠΣΠ Polynomials with terms of degrees no more a constant λ ≥ 2. On the inapproximability side, we give a n(1-e)/2 lower bound, for any e > 0, on the approximation factor for ΠΣΠ Polynomials. When the degrees of the terms in these Polynomials are constrained as le; 2, we prove a 1.0476 lower bound, assuming P ≠ NP; and a higher 1.0604 lower bound, assuming the Unique Games Conjecture.
-
approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate Polynomials
arXiv: Computational Complexity, 2010Co-Authors: Zhixiang ChenAbstract:This paper is our third step towards developing a theory of testing monomials in multivariate Polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a $\Pi\Sigma\Pi$ Polynomial. We first prove that the first problem is \#P-hard and then devise a $O^*(3^ns(n))$ upper bound for this problem for any Polynomial represented by an arithmetic circuit of size $s(n)$. Later, this upper bound is improved to $O^*(2^n)$ for $\Pi\Sigma\Pi$ Polynomials. We then design fully Polynomial-time randomized approximation schemes for this problem for $\Pi\Sigma$ Polynomials. On the negative side, we prove that, even for $\Pi\Sigma\Pi$ Polynomials with terms of degree $\le 2$, the first problem cannot be approximated at all for any approximation factor $\ge 1$, nor {\em "weakly approximated"} in a much relaxed setting, unless P=NP. For the second problem, we first give a Polynomial time $\lambda$-approximation algorithm for $\Pi\Sigma\Pi$ Polynomials with terms of degrees no more a constant $\lambda \ge 2$. On the inapproximability side, we give a $n^{(1-\epsilon)/2}$ lower bound, for any $\epsilon >0,$ on the approximation factor for $\Pi\Sigma\Pi$ Polynomials. When terms in these Polynomials are constrained to degrees $\le 2$, we prove a $1.0476$ lower bound, assuming $P\not=NP$; and a higher $1.0604$ lower bound, assuming the Unique Games Conjecture.
Juris Smotrovs - One of the best experts on this subject based on the ideXlab platform.
-
Polynomials quantum query complexity and grothendieck s inequality
Conference on Computational Complexity, 2016Co-Authors: Scott Aaronson, Andris Ambainis, Jānis Iraids, Martins Kokainis, Juris SmotrovsAbstract:We show an equivalence between 1-query quantum algorithms and representations by degree-2 Polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by e < 1/2 iff f can be approximated by a degree-2 Polynomial with error bounded by e' < 1/2. This result holds for two different notions of approximation by a Polynomial: the standard definition of Nisan and Szegedy [21] and the approximation by block-multilinear Polynomials recently introduced by Aaronson and Ambainis [1]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to Polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for Polynomials of higher degree. First, there is a total Boolean function which requires [EQUATION] quantum queries but can be represented by a block-multilinear Polynomial of degree [EQUATION]. Thus, in the general case (for an arbitrary number of queries), block-multilinear Polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a Polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [1], showing that one can estimate the value of any bounded degree-k Polynomial p: {0, 1}n → [-1, 1] with [EQUATION] queries.
-
Polynomials quantum query complexity and grothendieck s inequality
arXiv: Quantum Physics, 2015Co-Authors: Scott Aaronson, Andris Ambainis, Jānis Iraids, Martins Kokainis, Juris SmotrovsAbstract:We show an equivalence between 1-query quantum algorithms and representations by degree-2 Polynomials. Namely, a partial Boolean function $f$ is computable by a 1-query quantum algorithm with error bounded by $\epsilon<1/2$ iff $f$ can be approximated by a degree-2 Polynomial with error bounded by $\epsilon'<1/2$. This result holds for two different notions of approximation by a Polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear Polynomials recently introduced by Aaronson and Ambainis (STOC'2015, arXiv:1411.5729). We also show two results for Polynomials of higher degree. First, there is a total Boolean function which requires $\tilde{\Omega}(n)$ quantum queries but can be represented by a block-multilinear Polynomial of degree $\tilde{O}(\sqrt{n})$. Thus, in the general case (for an arbitrary number of queries), block-multilinear Polynomials are not equivalent to quantum algorithms. Second, for any constant degree $k$, the two notions of approximation by a Polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem of Aaronson and Ambainis, showing that one can estimate the value of any bounded degree-$k$ Polynomial $p:\{0, 1\}^n \rightarrow [-1, 1]$ with $O(n^{1-\frac{1}{2k}})$ queries.
Ilya Volkovich - One of the best experts on this subject based on the ideXlab platform.
-
on the relation between Polynomial identity testing and finding variable disjoint factors
International Colloquium on Automata Languages and Programming, 2010Co-Authors: Amir Shpilka, Ilya VolkovichAbstract:We say that a Polynomial f(x1, ..., xn) is indecomposable if it cannot be written as a product of two Polynomials that are defined over disjoint sets of variables. The Polynomial decomposition problem is defined to be the task of finding the indecomposable factors of a given Polynomial. Note that for multilinear Polynomials, factorization is the same as decomposition, as any two different factors are variable disjoint. In this paper we show that the problem of derandomizing Polynomial identity testing is essentially equivalent to the problem of derandomizing algorithms for Polynomial decomposition. More accurately, we show that for any reasonable circuit class there is a deterministic Polynomial time (black-box) algorithm for Polynomial identity testing of that class if and only if there is a deterministic Polynomial time (black-box) algorithm for factoring a Polynomial, computed in the class, to its indecomposable components. An immediate corollary is that Polynomial identity testing and Polynomial factorization are equivalent (up to a Polynomial overhead) for multilinear Polynomials. In addition, we observe that derandomizing the Polynomial decomposition problem is equivalent, in the sense of Kabanets and Impagliazzo [1], to proving arithmetic circuit lower bounds for NEXP. Our approach uses ideas from [2], that showed that the Polynomial identity testing problem for a circuit class C is essentially equivalent to the problem of deciding whether a circuit from C computes a Polynomial that has a read-once arithmetic formula.
-
on the relation between Polynomial identity testing and finding variable disjoint factors
International Colloquium on Automata Languages and Programming, 2010Co-Authors: Amir Shpilka, Ilya VolkovichAbstract:We say that a Polynomial f(x1, ..., xn) is indecomposable if it cannot be written as a product of two Polynomials that are defined over disjoint sets of variables. The Polynomial decomposition problem is defined to be the task of finding the indecomposable factors of a given Polynomial. Note that for multilinear Polynomials, factorization is the same as decomposition, as any two different factors are variable disjoint. In this paper we show that the problem of derandomizing Polynomial identity testing is essentially equivalent to the problem of derandomizing algorithms for Polynomial decomposition. More accurately, we show that for any reasonable circuit class there is a deterministic Polynomial time (black-box) algorithm for Polynomial identity testing of that class if and only if there is a deterministic Polynomial time (black-box) algorithm for factoring a Polynomial, computed in the class, to its indecomposable components. An immediate corollary is that Polynomial identity testing and Polynomial factorization are equivalent (up to a Polynomial overhead) for multilinear Polynomials. In addition, we observe that derandomizing the Polynomial decomposition problem is equivalent, in the sense of Kabanets and Impagliazzo [1], to proving arithmetic circuit lower bounds for NEXP. Our approach uses ideas from [2], that showed that the Polynomial identity testing problem for a circuit class C is essentially equivalent to the problem of deciding whether a circuit from C computes a Polynomial that has a read-once arithmetic formula.
G T Zhou - One of the best experts on this subject based on the ideXlab platform.
-
orthogonal Polynomials for power amplifier modeling and predistorter design
IEEE Transactions on Vehicular Technology, 2004Co-Authors: Raviv Raich, Hua Qian, G T ZhouAbstract:The Polynomial model is commonly used in power amplifier (PA) modeling and predistorter design. However, the conventional Polynomial model exhibits numerical instabilities when higher order terms are included. In this paper, we introduce a novel set of orthogonal Polynomials, which can be used for PA as well as predistorter modeling. Theoretically, the conventional and orthogonal Polynomial models are "equivalent" and, thus, should behave similarly. In practice, however, the two approaches can perform quite differently in the presence of finite precision processing. Simulation results show that the orthogonal Polynomials can alleviate the numerical instability problem associated with the conventional Polynomials and generally yield better PA modeling accuracy as well as predistortion linearization performance.
-
digital baseband predistortion of nonlinear power amplifiers using orthogonal Polynomials
International Conference on Acoustics Speech and Signal Processing, 2003Co-Authors: Raviv Raich, Hua Qian, G T ZhouAbstract:The Polynomial model is commonly used in predistorter design. However, the conventional Polynomial model exhibits numerical instabilities when high-order terms are included. We introduce a novel set of orthogonal Polynomial basis functions for predistorter modeling. Theoretically, the conventional and the orthogonal Polynomial models are "equivalent", and thus should have the same performance. In practice, however, the two approaches can perform quite differently in the presence of quantization noise and with finite precision processing. Simulation results show that the orthogonal Polynomials can alleviate the numerical instability problem associated with the conventional Polynomials and generally yield better predistortion linearization performance.
