اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSeveral Separations Based on a Partial Boolean Function
66
0
0.0
(
0
)
تأليف
Kaspars Balodis
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We show a partial Boolean function $f$ together with an input $xin f^{-1}left(*right)$ such that both $C_{bar{0}}left(f,xright)$ and $C_{bar{1}}left(f,xright)$ are at least $Cleft(fright)^{2-oleft(1right)}$. Due to recent results by Ben-David, G{o}{o}s, Jain, and Kothari, this result implies several other separations in query and communication complexity. For example, it gives a function $f$ with $C(f)=Omega(deg^{2-oleft(1right)}(f))$ where $C$ and $deg$ denote certificate complexity and polynomial degree of $f$. (This is the first improvement over a separation between $C(f)$ and $deg(f)$ by Kushilevitz and Nisan in 1995.) Other implications of this result are an improved separation between sensitivity and polynomial degree, a near-optimal lower bound on conondeterministic communication complexity for Clique vs. Independent Set problem and a near-optimal lower bound on complexity of Alon--Saks--Seymour problem in graph theory.
قيم البحث
اقرأ أيضاً
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND g
ates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537ldots})$. We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $Omega(n/log(n))$ while its zero-error randomized query complexity is $tilde O(sqrt{n})$. We further show that the quantum query complexity of the same function is $tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total boolean function $g$ on $n$ variables that has zero-error randomized query complexity $Omega(n/log(n))$ and bounded-error randomized query complexity $R(g) = tilde O(sqrt{n})$. This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is $Q_E(g) = tilde O(sqrt{n})$. These two functions show that the relations $D(f) = O(R_1(f)^2)$ and $R_0(f) = tilde O(R(f)^2)$ are optimal, up to poly-logarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between $Q$ and $R_0$, a $3/2$-power separation between $Q_E$ and $R$, and a 4th power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by goos, Pitassi, and Watson which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.
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$.
Let $mathcal{F}_{n}^*$ be the set of Boolean functions depending on all $n$ variables. We prove that for any $fin mathcal{F}_{n}^*$, $f|_{x_i=0}$ or $f|_{x_i=1}$ depends on the remaining $n-1$ variables, for some variable $x_i$. This existent result
suggests a possible way to deal with general Boolean functions via its subfunctions of some restrictions. As an application, we consider the degree lower bound of representing polynomials over finite rings. Let $fin mathcal{F}_{n}^*$ and denote the exact representing degree over the ring $mathbb{Z}_m$ (with the integer $m>2$) as $d_m(f)$. Let $m=Pi_{i=1}^{r}p_i^{e_i}$, where $p_i$s are distinct primes, and $r$ and $e_i$s are positive integers. If $f$ is symmetric, then $mcdot d_{p_1^{e_1}}(f)... d_{p_r^{e_r}}(f) > n$. If $f$ is non-symmetric, by the second moment method we prove almost always $mcdot d_{p_1^{e_1}}(f)... d_{p_r^{e_r}}(f) > lg{n}-1$. In particular, as $m=pq$ where $p$ and $q$ are arbitrary distinct primes, we have $d_p(f)d_q(f)=Omega(n)$ for symmetric $f$ and $d_p(f)d_q(f)=Omega(lg{n}-1)$ almost always for non-symmetric $f$. Hence any $n$-variate symmetric Boolean function can have exact representing degree $o(sqrt{n})$ in at most one finite field, and for non-symmetric functions, with $o(sqrt{lg{n}})$-degree in at most one finite field.
Global dynamics of a non-linear Cellular Automata is, in general irregular, asymmetric and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable. In the past efforts have been made to systematize non-linear CA evol
utions in the light of Boolean derivatives and Jacobian Matrices. In this paper two different efforts have been made: first we try to systematize non-linear CA evolution in the light of deviant states and non-deviant states. For all the non-deviant states the nearest linear rule matrix is applicable where as for the deviant states we have a set of other matrices. Second using algebraic manipulation, an efficient algorithm is proposed by which every Non-linear Boolean function can be characterized by a sequence of binary matrices.
Block sensitivity ($bs(f)$), certificate complexity ($C(f)$) and fractional certificate complexity ($C^*(f)$) are three fundamental combinatorial measures of complexity of a boolean function $f$. It has long been known that $bs(f) leq C^{ast}(f) leq
C(f) =O(bs(f)^2)$. We provide an infinite family of examples for which $C(f)$ grows quadratically in $C^{ast}(f)$ (and also $bs(f)$) giving optimal separations between these measures. Previously the biggest separation known was $C(f)=C^{ast}(f)^{log_{4.5}5}$. We also give a family of examples for which $C^{ast}(f)=Omega(bs(f)^{3/2})$. These examples are obtained by composing boolean functions in various ways. Here the composition $f circ g$ of $f$ with $g$ is obtained by substituting for each variable of $f$ a copy of $g$ on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure $s(f)$. The measures $s(f)$, $C(f)$ and $C^{ast}(f)$ behave nicely under composition: they are submultiplicative (where measure $m$ is submultiplicative if $m(f circ g) leq m(f)m(g)$) with equality holding under some fairly general conditions. The measure $bs(f)$ is qualitatively different: it is not submultiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure $m$ at function $f$, $m^{lim}(f)$ to be the limit as $k$ grows of $m(f^{(k)})^{1/k}$, where $f^{(k)}$ is the iterated composition of $f$ with itself $k$-times. For any function $f$ we show that $bs^{lim}(f) = (C^*)^{lim}(f)$ and characterize $s^{lim}(f), (C^*)^{lim}(f)$, and $C^{lim}(f)$ in terms of the largest eigenvalue of a certain set of $2times 2$ matrices associated with $f$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
