Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the complexity of partial derivatives
71
0
0.0
(
0
)
Added by
Pascal Koiran
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the trace method, recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.A slightly shorter version of this paper was presented at STACS17. In this new version we have corrected a typo in Section 4.1, and added a reference to Shitovs work on tensor rank.
rate research
Read More
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(fcirc g)ll R(f) R(g)$. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$). Second, we show that for all $f$ and $g$, $R(fcirc g)=Omega(mathop{noisyR}(f)cdot R(g))$, where $mathop{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(cdot)$ satisfying $R(fcirc g)=Omega(M(f)R(g))$ for all $f$ and $g$, it must hold that $mathop{noisyR}(f)=Omega(M(f))$ for all $f$. We also give a clean characterization of the measure $mathop{noisyR}(f)$: it satisfies $mathop{noisyR}(f)=Theta(R(fcirc gapmaj_n)/R(gapmaj_n))$, where $n$ is the input size of $f$ and $gapmaj_n$ is the $sqrt{n}$-gap majority function on $n$ bits.
We answer a question of K. Mulmuley: In [Efremenko-Landsberg-Schenck-Weyman] it was shown that the method of shifted partial derivatives cannot be used to separate the padded permanent from the determinant. Mulmuley asked if this no-go result could be extended to a model without padding. We prove this is indeed the case using the iterated matrix multiplication polynomial. We also provide several examples of polynomials with maximal space of partial derivatives, including the complete symmetric polynomials. We apply Koszul flattenings to these polynomials to have the first explicit sequence of polynomials with symmetric border rank lower bounds higher than the bounds attainable via partial derivatives.
We provide two sufficient and necessary conditions to characterize any $n$-bit partial Boolean function with exact quantum 1-query complexity. Using the first characterization, we present all $n$-bit partial Boolean functions that depend on $n$ bits and have exact quantum 1-query complexity. Due to the second characterization, we construct a function $F$ that maps any $n$-bit partial Boolean function to some integer, and if an $n$-bit partial Boolean function $f$ depends on $k$ bits and has exact quantum 1-query complexity, then $F(f)$ is non-positive. In addition, we show that the number of all $n$-bit partial Boolean functions that depend on $k$ bits and have exact quantum 1-query complexity is not bigger than $n^{2}2^{2^{n-1}(1+2^{2-k})+2n^{2}}$ for all $ngeq 3$ and $kgeq 2$.
Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no $O(3^{(1-epsilon)n} text{poly}(s))$ time algorithm, for any $epsilon > 0$, that detects logic hazards in Boolean circuits of size $s$ on $n$ variables under the assumption that the strong exponential time hypothesis is true. This lower bound holds even when the input circuits are restricted to be formulas of depth four. We also present a polynomial time algorithm for detecting $1$-hazards in DNF (or, $0$-hazards in CNF) formulas. Since $0$-hazards in DNF (or, $1$-hazards in CNF) formulas are easy to eliminate, this algorithm can be used to detect whether a given DNF or CNF formula has a hazard in practice.
Let $fsubseteq{0,1}^ntimesXi$ be a relation and $g:{0,1}^mto{0,1,*}$ be a promise function. This work investigates the randomised query complexity of the relation $fcirc g^nsubseteq{0,1}^{mcdot n}timesXi$, which can be viewed as one of the most general cases of composition in the query model (letting $g$ be a relation seems to result in a rather unnatural definition of $fcirc g^n$). We show that for every such $f$ and $g$, $$mathcal R(fcirc g^n) in Omega(mathcal R(f)cdotsqrt{mathcal R(g)}),$$ where $mathcal R$ denotes the randomised query complexity. On the other hand, we demonstrate a relation $f_0$ and a promise function $g_0$, such that $mathcal R(f_0)inTheta(sqrt n)$, $mathcal R(g_0)inTheta(n)$ and $mathcal R(f_0circ g_0^n)inTheta(n)$ $-$ that is, our composition statement is tight. To the best of our knowledge, there was no known composition theorem for the randomised query complexity of relations or promise functions (and for the special case of total functions our lower bound gives multiplicative improvement of $sqrt{log n}$).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
