Search results for "upper"
showing 10 items of 987 documents
All Classical Adversary Methods Are Equivalent for Total Functions
2017
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity canno…
Quantum lower bound for inverting a permutation with advice
2014
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…
A Quantum Lovasz Local Lemma
2012
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most $2^k/(e \cdot k)$ of them, has a joint satisfiable state. We then …
Quasi conjunction, quasi disjunction, t-norms and t-conorms: Probabilistic aspects
2013
We make a probabilistic analysis related to some inference rules which play an important role in nonmonotonic reasoning. In a coherence-based setting, we study the extensions of a probability assessment defined on $n$ conditional events to their quasi conjunction, and by exploiting duality, to their quasi disjunction. The lower and upper bounds coincide with some well known t-norms and t-conorms: minimum, product, Lukasiewicz, and Hamacher t-norms and their dual t-conorms. On this basis we obtain Quasi And and Quasi Or rules. These are rules for which any finite family of conditional events p-entails the associated quasi conjunction and quasi disjunction. We examine some cases of logical de…
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…
Random Walk in a N-cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations
2017
Designing a pseudorandom number generator (PRNG) is a difficult and complex task. Many recent works have considered chaotic functions as the basis of built PRNGs: the quality of the output would indeed be an obvious consequence of some chaos properties. However, there is no direct reasoning that goes from chaotic functions to uniform distribution of the output. Moreover, embedding such kind of functions into a PRNG does not necessarily allow to get a chaotic output, which could be required for simulating some chaotic behaviors. In a previous work, some of the authors have proposed the idea of walking into a $\mathsf{N}$-cube where a balanced Hamiltonian cycle has been removed as the basis o…
The DMT of Real and Quaternionic Lattice Codes and DMT Classification of Division Algebra Codes
2021
In this paper we consider the diversity-multiplexing gain tradeoff (DMT) of so-called minimum delay asymmetric space-time codes. Such codes are less than full dimensional lattices in their natural ambient space. Apart from the multiple input single output (MISO) channel there exist very few methods to analyze the DMT of such codes. Further, apart from the MISO case, no DMT optimal asymmetric codes are known. We first discuss previous criteria used to analyze the DMT of space-time codes and comment on why these methods fail when applied to asymmetric codes. We then consider two special classes of asymmetric codes where the code-words are restricted to either real or quaternion matrices. We p…
Exponential sums related to Maass forms
2019
We estimate short exponential sums weighted by the Fourier coefficients of a Maass form. This requires working out a certain transformation formula for non-linear exponential sums, which is of independent interest. We also discuss how the results depend on the growth of the Fourier coefficients in question. As a byproduct of these considerations, we can slightly extend the range of validity of a short exponential sum estimate for holomorphic cusp forms. The short estimates allow us to reduce smoothing errors. In particular, we prove an analogue of an approximate functional equation previously proven for holomorphic cusp form coefficients. As an application of these, we remove the logarithm …
Robust H;<inf>&#x221E;</inf> filtering for 2-D FM systems: A finite frequency approach
2012
This paper investigates the problem of robust H; ∞ filtering for uncertain two-dimensional (2-D) discrete systems in the Fornasini-Marchesini local state-space (FM LSS) model with polytopic uncertain parameters. The goal of the paper is to design filters such that the finite frequency (FF) H; ∞ norm of the filtering error system has a specified upper bound for all uncertainties. A generalized bounded real lemma (BRL) is first derived for FF H; ∞ performance analysis of nominal 2-D FM LSS systems, and then a method, in terms of solving optimization problems with LMI constraints, is presented for robust FF H; ∞ filter analysis and design. An illustrative example is given to show the improveme…
Virtual simulation of an osseointegrated trans-humeral prosthesis: A falling scenario
2018
Abstract Introduction Traditional prosthetic solutions expose the amputee to numerous problems that limit his ability to safely perform the normal activities of daily life. In order to eliminate the problems related to the use of the traditional prosthesis with socket, a new technique was developed for fixing the prosthesis to the amputees based on the principle of osseointegration. The aim of this paper is to study and analyze the stress distribution on the interface between a trans-humeral osseointegrated prosthetic implant and the residual bone, identifying the most stressed areas and thus foreseeing possible failure phenomena of the entire prosthetic system and, after, to compare the st…