ﻻ يوجد ملخص باللغة العربية
The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problems hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $Omega(N^{1/5}/log N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainiss adversary theorem.
We show that any quantum circuit of treewidth $t$, built from $r$-qubit gates, requires at least $Omega(frac{n^{2}}{2^{O(rcdot t)}cdot log^4 n})$ gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function $f:{+1,-1}^n to {+1,-1}$, the Fourier entropy of $f$ is at most its influence up to a universal constant factor. While the FEI conjecture has been proved for many cla
Hr{a}stad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $O(p^{2})$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave
Computing the reversal distances of signed permutations is an important topic in Bioinformatics. Recently, a new lower bound for the reversal distance was obtained via the plane permutation framework. This lower bound appears different from the exist
A classical result for the simple symmetric random walk with $2n$ steps is that the number of steps above the origin, the time of the last visit to the origin, and the time of the maximum height all have exactly the same distribution and converge whe