Search results for "lower bound"
showing 10 items of 269 documents
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 …
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…
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…
Bounding the number of vertices in the degree graph of a finite group
2020
Abstract Let G be a finite group, and let cd ( G ) denote the set of degrees of the irreducible complex characters of G . The degree graph Δ ( G ) of G is defined as the simple undirected graph whose vertex set V ( G ) consists of the prime divisors of the numbers in cd ( G ) , two distinct vertices p and q being adjacent if and only if pq divides some number in cd ( G ) . In this note, we provide an upper bound on the size of V ( G ) in terms of the clique number ω ( G ) (i.e., the maximum size of a subset of V ( G ) inducing a complete subgraph) of Δ ( G ) . Namely, we show that | V ( G ) | ≤ max { 2 ω ( G ) + 1 , 3 ω ( G ) − 4 } . Examples are given in order to show that the bound is bes…
Quantitative lower bounds to the Euclidean and the Gaussian Cheeger constants
2020
We provide a quantitative lower bound to the Cheeger constant of a set $\Omega$ in both the Euclidean and the Gaussian settings in terms of suitable asymmetry indexes. We provide examples which show that these quantitative estimates are sharp.
F-signature of pairs: Continuity, p-fractals and minimal log discrepancies
2011
This paper contains a number of observations on the {$F$-signature} of triples $(R,\Delta,\ba^t)$ introduced in our previous joint work. We first show that the $F$-signature $s(R,\Delta,\ba^t)$ is continuous as a function of $t$, and for principal ideals $\ba$ even convex. We then further deduce, for fixed $t$, that the $F$-signature is lower semi-continuous as a function on $\Spec R$ when $R$ is regular and $\ba$ is principal. We also point out the close relationship of the signature function in this setting to the works of Monsky and Teixeira on Hilbert-Kunz multiplicity and $p$-fractals. Finally, we conclude by showing that the minimal log discrepancy of an arbitrary triple $(R,\Delta,\b…
Reciprocal lower bound on modulus of curve families in metric surfaces
2019
We prove that any metric space $X$ homeomorphic to $\mathbb{R}^2$ with locally finite Hausdorff 2-measure satisfies a reciprocal lower bound on modulus of curve families associated to a quadrilateral. More precisely, let $Q \subset X$ be a topological quadrilateral with boundary edges (in cyclic order) denoted by $\zeta_1, \zeta_2, \zeta_3, \zeta_4$ and let $\Gamma(\zeta_i, \zeta_j; Q)$ denote the family of curves in $Q$ connecting $\zeta_i$ and $\zeta_j$; then $\text{mod} \Gamma(\zeta_1, \zeta_3; Q) \text{mod} \Gamma(\zeta_2, \zeta_4; Q) \geq 1/\kappa$ for $\kappa = 2000^2\cdot (4/\pi)^2$. This answers a question concerning minimal hypotheses under which a metric space admits a quasiconfor…
Accessible parts of boundary for simply connected domains
2018
For a bounded simply connected domain $\Omega\subset\mathbb{R}^2$, any point $z\in\Omega$ and any $0<\alpha<1$, we give a lower bound for the $\alpha$-dimensional Hausdorff content of the set of points in the boundary of $\Omega$ which can be joined to $z$ by a John curve with a suitable John constant depending only on $\alpha$, in terms of the distance of $z$ to $\partial\Omega$. In fact this set in the boundary contains the intersection $\partial\Omega_z\cap\partial\Omega$ of the boundary of a John sub-domain $\Omega_z$ of $\Omega$, centered at $z$, with the boundary of $\Omega$. This may be understood as a quantitative version of a result of Makarov. This estimate is then applied to obta…