Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAsymptotic Granularity Reduction and Its Application
116
0
0.0
(
0
)
Added by
Shenghui Su
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
It is well known that the inverse function of y = x with the derivative y = 1 is x = y, the inverse function of y = c with the derivative y = 0 is inexistent, and so on. Hence, on the assumption that the noninvertibility of the univariate increasing function y = f(x) with x > 0 is in direct proportion to the growth rate reflected by its derivative, the authors put forward a method of comparing difficulties in inverting two functions on a continuous or discrete interval called asymptotic granularity reduction (AGR) which integrates asymptotic analysis with logarithmic granularities, and is an extension and a complement to polynomial time (Turing) reduction (PTR). Prove by AGR that inverting y = x ^ x (mod p) is computationally harder than inverting y = g ^ x (mod p), and inverting y = g ^ (x ^ n) (mod p) is computationally equivalent to inverting y = g ^ x (mod p), which are compatible with the results from PTR. Besides, apply AGR to the comparison of inverting y = x ^ n (mod p) with y = g ^ x (mod p), y = g ^ (g1 ^ x) (mod p) with y = g ^ x (mod p), and y = x ^ n + x + 1 (mod p) with y = x ^ n (mod p) in difficulty, and observe that the results are consistent with existing facts, which further illustrates that AGR is suitable for comparison of inversion problems in difficulty. Last, prove by AGR that inverting y = (x ^ n)(g ^ x) (mod p) is computationally equivalent to inverting y = g ^ x (mod p) when PTR can not be utilized expediently. AGR with the assumption partitions the complexities of problems more detailedly, and finds out some new evidence for the security of cryptosystems.
rate research
Read More
We introduce a continuous-time analog solver for MaxSAT, a quintessential class of NP-hard discrete optimization problems, where the task is to find a truth assignment for a set of Boolean variables satisfying the maximum number of given logical constraints. We show that the scaling of an invariant of the solvers dynamics, the escape rate, as function of the number of unsatisfied clauses can predict the global optimum value, often well before reaching the corresponding state. We demonstrate the performance of the solver on hard MaxSAT competition problems. We then consider the two-color Ramsey number $R(m,m)$ problem, translate it to SAT, and apply our algorithm to the still unknown $R(5,5)$. We find edge colorings without monochromatic 5-cliques for complete graphs up to 42 vertices, while on 43 vertices we find colorings with only two monochromatic 5-cliques, the best coloring found so far, supporting the conjecture that $R(5,5) = 43$.
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.
We discuss, without assuming asymptotic flatness, a gravitational lens for an observer and source that are within a finite distance from a lens object. The proposed lens equation is consistent with the deflection angle of light that is defined for nonasymptotic observer and source by Takizawa et al. [Phys. Rev. D 101, 104032 (2020)] based on the Gauss-Bonnet theorem with using the optical metric. This lens equation, though it is shown to be equivalent to the Bozza lens equation[Phys. Rev. D 78, 103005 (2008)], is linear in the deflection angle. Therefore, the proposed equation is more convenient for the purpose of doing an iterative analysis. As an explicit example of an asymptotically nonflat spacetime, we consider a static and spherically symmetric solution in Weyl conformal gravity, especially a case that $gamma$ parameter in the Weyl gravity model is of the order of the inverse of the present Hubble radius. For this case, we examine iterative solutions for the finite-distance lens equation up to the third order. The effect of the Weyl gravity on the lensed image position begins at the third order and it is linear in the impact parameter of light. The deviation of the lensed image position from the general relativistic one is $sim 10^{-2}$ microarcsecond for the lens and source with a separation angle of $sim 1$ arcminute, where we consider a cluster of galaxies with $10^{14} M_{odot}$ at $sim 1$ Gpc for instance. The deviation becomes $sim 10^{-1}$ microarcseconds, even if the separation angle is $sim 10$ arcminutes. Therefore, effects of the Weyl gravity model are negligible in current and near-future observations of gravitational lensing. On the other hand, the general relativistic corrections at the third order $sim 0.1$ milliarcseconds can be relevant with VLBI observations.
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time $n^{Omega(log{n})}$ (so that the state-of-the-art running time of $n^{O(log n)}$ is optimal up to a constant in the exponent). We provide two sets of applications of the new hypothesis. First, we show that SPCH implies (nearly) tight inapproximability results for the following well-studied problems in terms of the parameter $k$: Densest $k$-Subgraph, Smallest $k$-Edge Subgraph, Densest $k$-Subhypergraph, Steiner $k$-Forest, and Directed Steiner Network with $k$ terminal pairs. For example, we show, under SPCH, that no polynomial time algorithm achieves $o(k)$-approximation for Densest $k$-Subgraph. This inapproximability ratio improves upon the previous best $k^{o(1)}$ factor from (Chalermsook et al., FOCS 2017). Furthermore, our lower bounds hold even against fixed-parameter tractable algorithms with parameter $k$. Our second application focuses on the complexity of graph pattern detection. For both induced and non-induced graph pattern detection, we prove hardness results under SPCH, which improves the running time lower bounds obtained by (Dalirrooyfard et al., STOC 2019) under the Exponential Time Hypothesis.
We have developed a new method, close in philosophy to the photometric redshift technique, which can be applied to spectral data of very low signal-to-noise ratio. Using it we intend to measure redshifts while minimising the dangers posed by the usual extraction techniques. GRB afterglows have generally very simple optical spectra over which the separate effects of absorption and reddening in the GRB host, the intergalactic medium, and our own Galaxy are superimposed. We model all these effects over a series of template afterglow spectra to produce a set of clean spectra that reproduce what would reach our telescope. We also model carefully the effects of the telescope-spectrograph combination and the properties of noise in the data, which are then applied on the template spectra. The final templates are compared to the two-dimensional spectral data, and the basic parameters (redshift, spectral index, Hydrogen absorption column) are estimated using statistical tools. We show how our method works by applying it to our data of the NIR afterglow of GRB090423. At z ~ 8.2, this was the most distant object ever observed. We use the spectrum taken by our team with the Telescopio Nazionale Galileo to derive the GRB redshift and its intrinsic neutral Hydrogen column density. Our best fit yields z=8.4^+0.05/-0.03 and N(HI)<5x10^20 cm^-2, but with a highly non-Gaussian uncertainty including the redshift range z [6.7, 8.5] at the 2-sigma confidence level. Our method will be useful to maximise the recovered information from low-quality spectra, particularly when the set of possible spectra is limited or easily parameterisable while at the same time ensuring an adequate confidence analysis.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
