Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInstruction sequence size complexity of parity
186
0
0.0
(
0
)
Added by
Kees Middelburg
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Each Boolean function can be computed by a single-pass instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. Auxiliary Boolean registers are not necessary for this. In the current paper, we show that, in the case of the parity functions, shorter instruction sequences are possible with the use of an auxiliary Boolean register in the presence of instructions to complement the content of auxiliary Boolean registers. This result supports, in a setting where programs are instruction sequences acting on Boolean registers, a basic intuition behind the storage of auxiliary data, namely the intuition that this makes possible a reduction of the size of a program.
rate research
Read More
We present an approach to non-uniform complexity in which single-pass instruction sequences play a key part, and answer various questions that arise from this approach. We introduce several kinds of non-uniform complexity classes. One kind includes a counterpart of the well-known non-uniform complexity class P/poly and another kind includes a counterpart of the well-known non-uniform complexity class NP/poly. Moreover, we introduce a general notion of completeness for the non-uniform complexity classes of the latter kind. We also formulate a counterpart of the well-known complexity theoretic conjecture that NP is not included in P/poly. We think that the presented approach opens up an additional way of investigating issues concerning non-uniform complexity.
We develop theory concerning non-uniform complexity in a setting in which the notion of single-pass instruction sequence considered in program algebra is the central notion. We define counterparts of the complexity classes P/poly and NP/poly and formulate a counterpart of the complexity theoretic conjecture that NP is not included in P/poly. In addition, we define a notion of completeness for the counterpart of NP/poly using a non-uniform reducibility relation and formulate complexity hypotheses which concern restrictions on the instruction sequences used for computation. We think that the theory developed opens up an additional way of investigating issues concerning non-uniform complexity.
Programming language concepts are used to give some new perspectives on a long-standing open problem: is logspace = ptime ?
We prove a new lower bound on the parity decision tree complexity $mathsf{D}_{oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $mathsf{D}_{oplus}(f)geq k+1$. This lower bound is an improvement of lower bounds through the sparsity of $f$ and through the degree of $f$ over $mathbb{F}_2$. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is $n - mathsf{B}(n)+1$, where $mathsf{B}(n)$ is the number of ones in the binary representation of $n$. For recursive majority the complexity is $frac{n+1}{2}$. Finally, we provide an example of a function for which our lower bound is not tight. Our results imply new lower bound of $n - mathsf{B}(n)$ on the multiplicative complexity of majority.
In this note, we study the relation between the parity decision tree complexity of a boolean function $f$, denoted by $mathrm{D}_{oplus}(f)$, and the $k$-party number-in-hand multiparty communication complexity of the XOR functions $F(x_1,ldots, x_k)= f(x_1opluscdotsoplus x_k)$, denoted by $mathrm{CC}^{(k)}(F)$. It is known that $mathrm{CC}^{(k)}(F)leq kcdotmathrm{D}_{oplus}(f)$ because the players can simulate the parity decision tree that computes $f$. In this note, we show that [mathrm{D}_{oplus}(f)leq Obig(mathrm{CC}^{(4)}(F)^5big).] Our main tool is a recent result from additive combinatorics due to Sanders. As $mathrm{CC}^{(k)}(F)$ is non-decreasing as $k$ grows, the parity decision tree complexity of $f$ and the communication complexity of the corresponding $k$-argument XOR functions are polynomially equivalent whenever $kgeq 4$. Remark: After the first version of this paper was finished, we discovered that Hatami and Lovett had already discovered the same result a few years ago, without writing it up.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
