Search results for "Boolean function"
showing 10 items of 38 documents
Separations in Query Complexity Based on Pointer Functions
2015
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 gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. 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-quadra…
Exact quantum algorithms have advantage for almost all Boolean functions
2014
It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.
Superlinear advantage for exact quantum algorithms
2012
A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For total Boolean functions in the query model, the biggest known gap was just a factor of 2: PARITY of N inputs bits requires $N$ queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x_1, ..., x_N) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N qu…
Sensitivity versus block sensitivity of Boolean functions
2010
Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.
Forrelation
2014
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(√(N)log(N)) queries (improving an Ω(N[superscript 1/4]) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N[superscript 1-1/2t])-query randomized algorithm. Thus, resolving an open questi…
Supershape Recovery from 3D Data Sets
2006
In this paper, we apply supershapes and R-functions to surface recovery from 3D data sets. Individual supershapes are separately recovered from a segmented mesh. R-functions are used to perform Boolean operations between the reconstructed parts to obtain a single implicit equation of the reconstructed object that is used to define a global error reconstruction function. We present surface recovery results ranging from single synthetic data to real complex objects involving the composition of several supershapes and holes.
BMaD – A Boolean Matrix Decomposition Framework
2014
Boolean matrix decomposition is a method to obtain a compressed representation of a matrix with Boolean entries. We present a modular framework that unifies several Boolean matrix decomposition algorithms, and provide methods to evaluate their performance. The main advantages of the framework are its modular approach and hence the flexible combination of the steps of a Boolean matrix decomposition and the capability of handling missing values. The framework is licensed under the GPLv3 and can be downloaded freely at http://projects.informatik.uni-mainz.de/bmad.
Generalized person-by-person optimization in team problems with binary decisions
2008
In this paper, we extend the notion of person by person optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and sub- modularity. We also generalize the concept of pbp optimization to the case where the decision makers (DMs) make decisions sequentially in groups of m, we call it mbm optimization. The main contribution are certain sufficient conditions, verifiable in polynomial time, under which a pbp or an mbm optimization algorithm leads to the team-optimum. We also show that there exists a subclass of sub-modular team pr…
Quantum Query Algorithms for Conjunctions
2010
Every Boolean function can be presented as a logical formula in conjunctive normal form. Fast algorithm for conjunction plays significant role in overall algorithm for computing arbitrary Boolean function. First, we present a quantum query algorithm for conjunction of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p = 4/5, that improves the previous result. Then, we present the main result - generalization of our approach to design efficient quantum algorithms for computing conjunction of two Boolean functions. Finally, we demonstrate another kind of an algorithm for conjunction of two bits, that has a correct answer probability p = 9/10. Th…
On the collision property of chaotic iterations based post-treatments over cryptographic pseudorandom number generators
2018
International audience; There is not a proper mathematical definition of chaos, we have instead a quite big amount of definitions, each of one describes chaos in a more or less general context. Taking in account this, it is clear why it is hard to design an algorithm that produce random numbers, a kind of algorithm that could have plenty of concrete appliceautifat (anul)d bions. However we must use a finite state machine (e.g. a laptop) to produce such a sequence of random numbers, thus it is convenient, for obvious reasons, to redefine those aimed sequences as pseudorandom; also problems arise with floating point arithmetic if one wants to recover some real chaotic property (i.e. propertie…