Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFault-Tolerant Modular Reconstruction of Rational Numbers
544
0
0.0
(
0
)
Authors
John Abbott
Ask ChatGPT about the research
No Arabic abstract
In this paper we present two efficient methods for reconstructing a rational number from several residue-modulus pairs, some of which may be incorrect. One method is a natural generalization of that presented by Wang, Guy and Davenport in cite{WGD1982} (for reconstructing a rational number from textit{correct} modular images), and also of an algorithm presented in cite{Abb1991} for reconstructing an textit{integer} value from several residue-modulus pairs, some of which may be incorrect.
rate research
Read More
Let $b ge 2$ and $ell ge 1$ be integers. We establish that there is an absolute real number $K$ such that all the partial quotients of the rational number $$ prod_{h = 0}^ell , (1 - b^{-2^h}), $$ of denominator $b^{2^{ell+1} - 1}$, do not exceed $exp(K (log b)^2 sqrt{ell} 2^{ell/2})$.
For a nonincreasing function $psi$, let $textrm{Exact}(psi)$ be the set of complex numbers that are approximable by complex rational numbers to order $psi$ but to no better order. In this paper, we obtain the Hausdorff dimension and packing dimension of $textrm{Exact}(psi)$ when $psi(x)=o(x^{-2})$. We also prove that the lower bound of the Hausdorff dimension is greater than $2-tau/(1-2tau)$ when $tau=limsup_{xtoinfty}psi(x)x^2$ small enough.
In this work, we initiate the study of fault tolerant Max Cut, where given an edge-weighted undirected graph $G=(V,E)$, the goal is to find a cut $Ssubseteq V$ that maximizes the total weight of edges that cross $S$ even after an adversary removes $k$ vertices from $G$. We consider two types of adversaries: an adaptive adversary that sees the outcome of the random coin tosses used by the algorithm, and an oblivious adversary that does not. For any constant number of failures $k$ we present an approximation of $(0.878-epsilon)$ against an adaptive adversary and of $alpha_{GW}approx 0.8786$ against an oblivious adversary (here $alpha_{GW}$ is the approximation achieved by the random hyperplane algorithm of [Goemans-Williamson J. ACM `95]). Additionally, we present a hardness of approximation of $alpha_{GW}$ against both types of adversaries, rendering our results (virtually) tight. The non-linear nature of the fault tolerant objective makes the design and analysis of algorithms harder when compared to the classic Max Cut. Hence, we employ approaches ranging from multi-objective optimization to LP duality and the ellipsoid algorithm to obtain our results.
A $k$-spanner of a graph $G$ is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of $k$, and a $k$-emulator is similar but not required to be a subgraph of $G$. A classic theorem by Thorup and Zwick [JACM 05] shows that, despite the extra flexibility available to emulators, the size/stretch tradeoffs for spanners and emulators are equivalent. Our main result is that this equivalence in tradeoffs no longer holds in the commonly-studied setting of graphs with vertex failures. That is: we introduce a natural definition of vertex fault-tolerant emulators, and then we show a three-way tradeoff between size, stretch, and fault-tolerance for these emulators that polynomially surpasses the tradeoff known to be optimal for spanners. We complement our emulator upper bound with a lower bound construction that is essentially tight (within $log n$ factors of the upper bound) when the stretch is $2k-1$ and $k$ is either a fixed odd integer or $2$. We also show constructions of fault-tolerant emulators with additive error, demonstrating that these also enjoy significantly improved tradeoffs over those available for fault-tolerant additive spanners.
It is now widely accepted that the CMOS technology implementing irreversible logic will hit a scaling limit beyond 2016, and that the increased power dissipation is a major limiting factor. Reversible computing can potentially require arbitrarily small amounts of energy. Recently several nano-scale devices which have the potential to scale, and which naturally perform reversible logic, have emerged. This paper addresses several fundamental issues that need to be addressed before any nano-scale reversible computing systems can be realized, including reliability and performance trade-offs and architecture optimization. Many nano-scale devices will be limited to only near neighbor interactions, requiring careful optimization of circuits. We provide efficient fault-tolerant (FT) circuits when restricted to both 2D and 1D. Finally, we compute bounds on the entropy (and hence, heat) generated by our FT circuits and provide quantitative estimates on how large can we make our circuits before we lose any advantage over irreversible computing.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
