BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this paper, we devise three deterministic algorithms for solving the m-set k-packing, m-dimensional k-matching, and t-dominating set problems in time O∗(5.44mk), O∗(5.44(m−1)k) and O∗(5.44t), respectively. Although recently there has been remarkable progress on randomized solutions to those problems, our bounds make good improvements on the best known bounds for deterministic solutions to those problems.
In this paper, we devise two algorithms for the problem of testing q-monomials of degree k in any multivariate polynomial represented by a circuit, regardless of the primality of q. One is an O∗(2k) time randomized algorithm. The other is an O∗(12.8k) time deterministic algorithm for the same q-monomial testing problem but requiring the polynomials to be represented by tree-like circuits. Several applications of q-monomial testing are also given, including a deterministic O∗(12.8mk) upper bound for the m-set k-packing problem.
Given any fixed integer q≥2, a q-monomial is of the format xi1s1xi2s2...xitst such that 1≤sj≤q−1, 1≤j≤t. q-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and q-monomails for prime q in multivariate polynomials relies on the property that Zq is a field when q≥2 is prime. When q>2 is not prime, it remains open whether the problem of testing q-monomials can be solved in some compatible complexity. In this paper, we present a randomized O∗(7.15k) algorithm for testing q-monomials of degree k that are found in a multivariate polynomial that is represented by a tree-like circuit with a polynomial size, thus giving a positive, affirming answer to the above question. Our algorithm works regardless of the primality of q and improves upon the time complexity of the previously known algorithm for testing q-monomials for prime q>7.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.