Polylogarithms and the Asymptotic Formula for the Moments of Lebesgue’s Singular Function

Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t ? 1), where p, q > 0, q = 1 ? p, p ≠ q. The variables M _n = ∫₀¹t ⁿ dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\), where the function τ(x) is periodic in log₂x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){|_{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\), \({z_k} = \frac{{2\pi ik}}{{1n2}}\), k ≠ 0. The proof is based on poissonization and the Mellin transform.     

New bounds for the controller problem

The (M, W)-controller, originally studied by Afek, Awerbuch, Plotkin, and Saks, is a basic distributed tool that provides an abstraction for managing the consumption of a global resource in a distributed dynamic network. The input to the controller arrives online in the form of requests presented at arbitrary nodes. A request presented at node u corresponds to the ??desire?? of some entity to consume one unit of the global resource at u and the controller should handle this request within finite time either by granting it with a permit or by denying it. Initially, M permits (corresponding to M units of the global resource) are stored at a designated root node. Throughout the execution permits can be transported from place to place along the network??s links so that they can be granted to requests presented at various nodes; when a permit is granted to some request, it is eliminated from the network. The fundamental rule of an (M, W)-controller is that a request should not be denied unless it is certain that at least M ? W permits are eventually granted. The most efficient (M, W)-controller known to date has message complexity ${O (N\log^{2} N \log \frac{M}{W + 1})}$ , where N is the number of nodes that ever existed in the network (the dynamic network may undergo node insertions and deletions). In this paper we establish two new lower bounds on the message complexity of the controller problem. We first prove a simple lower bound stating that any (M, W)-controller must send ${\Omega (N \log \frac{M}{W + 1})}$ messages. Second, for the important case when W is proportional to M (this is the common case in most applications), we use a surprising reduction from the (centralized) monotonic labeling problem to show that any (M, W)-controller must send ??(N log N) messages. In fact, under a long lasting conjecture regarding the complexity of the monotonic labeling problem, this lower bound is improved to a tight ??(N log² N). The proof of this lower bound requires that N =?O(M) which turns out to be somewhat inevitable due to a new construction of an (M, M/2)-controller with message complexity O(N log² M).     

Pseudorandom generators for combinatorial checkerboards

We define a combinatorial checkerboard to be a function f : {1, . . . , m} ^d → {1,?1} of the form ${f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)}$ for some functions f _i : {1, . . . , m} → {1,?1}. This is a variant of combinatorial rectangles, which can be defined in the same way but using {0, 1} instead of {1,?1}. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case m = 2. We construct a pseudorandom generator that ${\epsilon}$ -fools all combinatorial checkerboards with seed length ${O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2} \frac{1}{\epsilon}\bigr)}$ . Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length ${O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)}$ . Our seed length is better except when ${\frac{1}{\epsilon}\geq d^{\omega(\log d)}}$ .     

Calculating the n-dimensional fast Fourier transform

The one-dimensional fast Fourier transform (FFT) is the most popular tool for calculating the multidimensional Fourier transform. As a rule, to estimate the n-dimensional FFT, a standard method of combining one-dimensional FFTs, the so-called “by rows and columns” algorithm, is used in the literature. For fast calculations, different researchers try to use parallel calculation tools, the most successful of which are searches for the algorithms related to the computing device architecture: cluster, video card, GPU, etc. [1, 2]. The possibility of paralleling another algorithm for FFT calculation, which is an n-dimensional analog of the Cooley-Tukey algorithm [3, 4], is studied in this paper. The focus is on studying the analog of the Cooley-Tukey algorithm because the number of operations applied to calculate the n-dimensional FFT is considerably less than in the conventional algorithm nN ⁿ log₂ N of addition operations and 1/2N ^{n + 1}log₂ N of multiplication operations of addition operations and $\frac{{2^n - 1}} {{2^n }}N^n \log _2 N$ of multiplication operations against: N ^{n + 1}log₂ N of addition operations and 1/2N ^{n + 1}log₂ N of in combining one-dimensional FFTs.     

Tile Complexity of Approximate Squares

The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, 1998) is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly under the rules of this model is programmable and can perform Turing universal computation. Many variations of this model have been proposed and the canonical problem of assembling squares has been studied extensively. We consider the problem of building approximate squares in TAM. Given any $\varepsilon \in (0,\frac{1}{4}]$ we show how to construct squares whose sides are within (1±ε)N of any given positive integer N using $O( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types. We prove a matching lower bound by showing that $\varOmega( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types are necessary almost always to build squares of required approximate dimensions. In comparison, the optimal construction for a square of side exactly N in TAM uses $O(\frac{\log N}{\log \log N})$ tile types. The question of constructing approximate squares has been recently studied in a modified tile assembly model involving concentration programming. All our results are trivially translated into the concentration programming model by assuming arbitrary (non-zero) concentrations for our tile types. Indeed, the non-zero concentrations could be chosen by an adversary and our results would still hold. Our construction can get highly accurate squares using very few tile types and are feasible starting from values of N that are orders of magnitude smaller than the best comparable constructions previously suggested. At an accuracy of ε=0.01, the number of tile types used to achieve a square of size 10⁷ is just 58 and our constructions are proven to work for all N≥13130. If the concentrations of the tile types are carefully chosen, we prove that our construction assembles an L×L square in optimal assembly time O(L) where (1?ε)N≤L≤(1+ε)N.     

Improved approximations for the minimum-cut ratio and the flux

LetC be any concurrent flow problem with integer demands and capacities on an undirected graphG. Kleinet al. [5] recently showed that the maximum throughputz ^* is Ω (S/(logC logD)), whereS is the minimum cut ratio,C is the sum of the capacities on the edges, andD is the sum of the demands of the commodities. They also presented a polynomial time algorithm which finds a cut whose ratio isS · O(logC logD). Leighton and Rao [8] have shown that for the concurrent flow problem with a unit demand between every pair of nodes,z ^* is Ω (S/logn), wheren is the number of nodes ofG. This leads to anO(logn) approximation of the flux of a graphG with uniform weights on the nodes. We show that for the problem in [5] the maximum throughputz ^* is Ω(S/(logn logD)), and we find a cut whose ratio isS · O (logn logD). For the special case in which the demands have the form $$demand between u and v = l(u) \cdot \frac{{l(v)}}{2},$$ wherel(u) is an assignment of a positive integer weight to nodeu, we show that the lower bound onz* can be improved to be Ω(S/logn). This generalizes the result of Leighton and Rao.     

Matching and spanning in certain planar graphs

Call a connected planar graphG legal if it has at least two nodes, no parallel edges or self-loops and at most two terminals (degree 1 nodes) and all terminals and degree 2 nodes are exterior. This class of graphs arose in connection with a two-dimensional generating system for modeling growth by binary cell division. Showing that any permitted pattern can be generated properly requires a matching or pairing lemma. The vertex set of a legal graph withn nodes can be split intop adjacent pairs ands singletons withs p, resulting in a matching which includes at least \(2\left[ {\frac{n}{3}} \right]\) nodes. This bound is sharp in the sense that there are legal graphs for which this matching is maximum. The matching can be implemented by a linear time algorithm. A legal graph witht terminals and n≥4 nodes has a spanning tree with at most \(\left[ {\frac{{n - t}}{2}} \right] + t\) terminals; this bound is sharp. Such a spanning tree can be constructed by an algorithm which operates in almost linear time.     

Stability Criteria for Finite Difference Approximations to Parabolic Systems—An Update

In a recent series of papers, Goldberg [G1, G2] and Sun and Yuan [SY] studied the L ₂-stability of a well-known family of finite difference approximations for the initial-value problem associated with the multispace-dimensional parabolic system $$\frac{{\partial {\text{u(x,}}\;t{\text{)}}}}{{\partial t}} = \sum\limits_{1 \leqslant {\kern 1pt} p{\kern 1pt} \leqslant {\kern 1pt} q{\kern 1pt} \leqslant {\kern 1pt} {\kern 1pt} s} {A_{pq} \frac{{\partial ^2 {\text{u(x,}}\;t{\text{)}}}}{{\partial x_p \partial x_q }}} + \sum\limits_{1 \leqslant {\kern 1pt} p{\kern 1pt} \leqslant {\kern 1pt} s} {B_p \frac{{\partial {\text{u(x,}}\;t{\text{)}}}}{{\partial x_p }} + C{\text{u(x,}}\;t{\text{)}}} $$ where A _pq ,B _p and C are constant matrices, A _pq being Hermitian. In the present paper we discuss these earlier results and complete the underlying theory by answering four open questions.     

Generalized cryptanalysis of RSA with small public exponent针对公钥e小于等于N的0.5次幂的RSA算法的广义密码分析

In this paper, we demonstrate that there exist weak keys in the RSA public-key cryptosystem with the public exponent e = N^α ≤ N^0.5. In 1999, Boneh and Durfee showed that when α ≈ 1 and the private exponent d = N^β < N^0.292, the system is insecure. Moreover, their attack is still effective for 0.5 < α < 1.875. We propose a generalized cryptanalytic method to attack the RSA cryptosystem with α ≤ 0.5. For \(c = \left\lfloor {\frac{{1 - \alpha }}{\alpha }} \right\rfloor \) and e^γc ≡ d (mod e^c), when γ, β satisfy \(\gamma < 1 + \frac{1}{c} - \frac{1}{{2\alpha c}}and\beta < \alpha c + \frac{7}{6} - \alpha \gamma c - \frac{1}{3}\sqrt {6\alpha + 6\alpha c + 1 - 6\alpha \gamma c} \), we can perform cryptanalytic attacks based on the LLL algorithm. The basic idea is an application of Coppersmith’s techniques and we further adapt the technique of unravelled linearization, which leads to an optimized lattice. Our advantage is that we achieve new attacks on RSA with α ≤ 0.5 and consequently, there exist weak keys in RSA for most α.     

Lower bounds for polynomial evaluation and interpolation problems

We show that there is a set of pointsp ₁,p ₂,...,p _n such that any arithmetic circuit of depthd for polynomial evaluation (or interpolation) at these points has size $$\Omega \left( {\frac{{n\log n}}{{\log (2 + d/\log n}}} \right).$$ Moreover, for circuits of sub-logarithmic depthd, we obtain a lower bound of Ω(dn ^1+1/d ) on its size.