Title: Detecting Monomials with k Distinct Variables.
Abstract: We study the complexity of detecting monomials with special properties in the sum-product expansion of a polynomial represented by an arithmetic circuit of size polynomial in the number of input variables and using only multiplication and addition. We focus on monomial properties expressed in terms of the number of distinct variables occurring in a monomial. Our first result is a randomized FPT algorithm for detection of a monomial having at least k distinct variables, parametrized with respect to k. For a more restricted class of circuits, we can also provide a deterministic FPT algorithm for detection of a monomial having at most k distinct variables parametrized by the degree of the polynomial represented by the input circuit. Furthermore, we derive several hardness results on detection of monomials with such properties within exact, parametrized and approximation complexity. In particular, we observe that the detection of a monomial having at most k distinct variables is W 2 -hard for the parameter k. An O * ( 2 k ) -time detection of a monomial with ?k variables in a polynomial given by a circuit.An O * ( 2 l ) -time detection of a monomial with ?k variables in a restricted l-degree polynomial.Detecting a monomial with ?k distinct variables is W 2 -hard with respect to k.Finding min ? k s.t. there is a monomial with ?k variables is inapproximable within O ( 2 log 1 - ? ? n ) .Finding max ? k s.t. there is a monomial with ?k variables is inapproximable within 1 - 1 e + ? .
Publication Year: 2013
Publication Date: 2013-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot