An unconditional proof of the Andr���COort conjecture for Hilbert modular surfaces

We give an unconditional proof of the André?COort conjecture for Hilbert modular surfaces asserting that an algebraic curve contained in such a surface and containing an infinite set of special points, is special. The proof relies on a combination of Galois-theoretic techniques and results from the theory of o-minimal structures.     

Semi-Lagrangian semi-implicit time-splitting scheme for a regional model of the atmosphere

Semi-Lagrangian semi-implicit (SLSI) method is currently one of the most efficient approaches for numerical solution of the atmosphere dynamics equations. In this research we apply splitting techniques in the context of a two-time-level SLSI scheme in order to simplify the treatment of the slow physical modes and optimize the solution of the elliptic equations related to implicit part of the scheme. The performed numerical experiments show the accuracy and computational efficiency of the scheme.     

Upper Bounds for α-Domination Parameters

We provide a new upper bound for the α-domination number in terms of a parameter α, 0 < α ≤ 1, and graph vertex degrees. This result generalises the well-known Caro-Roditty bound for the domination number of a graph. The same probabilistic construction is used to generalise another well-known upper bound for the classical domination in graphs. Using a different probabilistic construction, we prove similar upper bounds for the α-rate domination number, which combines the concepts of α-domination and k-tuple domination.     

On Topological Lower Bounds for Algebraic Computation Trees

We prove that the height of any algebraic computation tree for deciding membership in a semialgebraic set \(\Sigma \subset {\mathbb R}^n\) is bounded from below by

$$\begin{aligned} \frac{c_1\log (\mathrm{b}_m(\Sigma ))}{m+1} -c_2n, \end{aligned}$$

where \(\mathrm{b}_m(\Sigma )\) is the mth Betti number of \(\Sigma \) with respect to “ordinary” (singular) homology and \(c_1,\ c_2\) are some (absolute) positive constants. This result complements the well-known lower bound by Yao (J Comput Syst Sci 55:36–43, 1997) for locally closed semialgebraic sets in terms of the total Borel–Moore Betti number. We also prove that if \(\rho :\> {\mathbb R}^n \rightarrow {\mathbb R}^{n-r}\) is the projection map, then the height of any tree deciding membership in \(\Sigma \) is bounded from below by

$$\begin{aligned} \frac{c_1\log (\mathrm{b}_m(\rho (\Sigma )))}{(m+1)^2} -\frac{c_2n}{m+1} \end{aligned}$$

for some positive constants \(c_1,\ c_2\). We illustrate these general results by examples of lower complexity bounds for some specific computational problems.

     

Application of p-Adic Wavelets to Model Reaction–Diffusion Dynamics in Random Porous Media

Fourier and more generally wavelet analysis over the fields of p-adic numbers are widely used in physics, biology and cognitive science, and recently in geophysics. In this note we present a model of the reaction–diffusion dynamics in random porous media, e.g., flow of fluid (oil, water or emulsion) in a a complex network of pores with known topology. Anomalous diffusion in the model is represented by the system of two equations of reaction–diffusion type, for the part of fluid not bound to solid’s interface (e.g., free oil) and for the part bound to solid’s interface (e.g., solids–bound oil). Our model is based on the p-adic (treelike) representation of pore-networks. We present the system of two p-adic reaction–diffusion equations describing propagation of fluid in networks of pores in random media and find its stationary solutions by using theory of p-adic wavelets. The use of p-adic wavelets (generalizing classical wavelet theory) gives a possibility to find the stationary solution in the analytic form which is typically impossible for anomalous diffusion in the standard representation based on the real numbers.     

A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

In this paper we propose a variant of the random coordinate descent method for solving linearly constrained convex optimization problems with composite objective functions. If the smooth part of the objective function has Lipschitz continuous gradient, then we prove that our method obtains an ?-optimal solution in $\mathcal{O}(n^{2}/\epsilon)$ iterations, where n is the number of blocks. For the class of problems with cheap coordinate derivatives we show that the new method is faster than methods based on full-gradient information. Analysis for the rate of convergence in probability is also provided. For strongly convex functions our method converges linearly. Extensive numerical tests confirm that on very large problems, our method is much more numerically efficient than methods based on full gradient information.     

On modular inequalities in variable L p spaces

We show that the Hardy-Littlewood maximal operator and a class of Calderón-Zygmund singular integrals satisfy the strong type modular inequality in variable L^p spaces if and only if the variable exponent p(x) ∼ const. Received: 15 September 2004