Counting polycubes without the dimensionality curse

d-dimensional polycubes are the generalization of planar polyominoes to higher dimensions. That is, a d-D polycube of size n is a connected set of n cells of a d-dimensional hypercubic lattice, where connectivity is through (d−1)-dimensional faces of the cells. Computing A_d(n), the number of distinct d-dimensional polycubes of size n, is a long-standing elusive problem in discrete geometry. In a previous work we described the generalization from two to higher dimensions of a polyomino-counting algorithm of Redelmeier [D.H. Redelmeier, Counting polyominoes: Yet another attack, Discrete Math. 36 (1981) 191-203]. The main deficiency of the algorithm is that it keeps the entire set of cells that appear in any possible polycube in memory at all times. Thus, the amount of required memory grows exponentially with the dimension. In this paper we present an improved version of the same method, whose order of memory consumption is a (very low) polynomial in both n and d. We also describe how we parallelized the algorithm and ran it through the Internet on dozens of computers simultaneously.     

A class of matrix monotone functions

In this paper we show that a class of functions is matrix (operator) monotone and give some consequences of it.     

The curse of dimensionality for numerical integration on general domains

We prove the curse of dimensionality in the worst case setting for multivariate numerical integration for various classes of smooth functions. We prove the results when the domains are isotropic convex bodies with small diameter satisfying a universal ${\psi }_2$-estimate. In particular, we obtain the result for the important class of volume-normalized ${\ell }_p^d$-balls in the complete regime $2\le p\le \infty$. This extends a result in a work of Hinrichs et al. (2014) to the whole range $2\le p\le \infty$, and additionally provides a unified approach. The key ingredient in the proof is a deep result from the theory of Asymptotic Geometric Analysis, the thin-shell volume concentration estimate due to O. Guédon and E. Milman. The connection of Asymptotic Geometric Analysis and Information-based Complexity revealed in this work seems promising and is of independent interest.     

A class of conjugate gradient methods for convex constrained monotone equations

The recent designed non-linear conjugate gradient method of Dai and Kou [SIAM J Optim. 2013;23:296–320] is very efficient currently in solving large-scale unconstrained minimization problems due to its simpler iterative form, lower storage requirement and its closeness to the scaled memoryless BFGS method. Just because of these attractive properties, this method was extended successfully to solve higher dimensional symmetric non-linear equations in recent years. Nevertheless, its numerical performance in solving convex constrained monotone equations has never been explored. In this paper, combining with the projection method of Solodov and Svaiter, we develop a family of non-linear conjugate gradient methods for convex constrained monotone equations. The proposed methods do not require the Jacobian information of equations, and even they do not store any matrix in each iteration. They are potential to solve non-smooth problems with higher dimensions. We prove the global convergence of the class of the proposed methods and establish its R-linear convergence rate under some reasonable conditions. Finally, we also do some numerical experiments to show that the proposed methods are efficient and promising.     

The modular inequalities for a class of convolution operators on monotone functions

This paper is devoted to the study of modular inequality

where and is a class of Volterra convolution operators restricted to the monotone functions. When with and the kernel , our results will extend those for the Hardy operator on monotone functions on Lebesgue spaces.

     

Strong starlikeness for a class of convex functions

By means of the Briot-Bouquet differential subordination, we estimate the order of strong starlikeness of strongly convex functions of a prescribed order. We also make numerical experiments to examine our estimates.     

Sum theorems for monotone operators and convex functions

In this paper, we derive sufficient conditions for the sum of two or more maximal monotone operators on a reflexive Banach space to be maximal monotone, and we achieve this without any renorming theorems or fixed-point-related concepts. In the course of this, we will develop a generalization of the uniform boundedness theorem for (possibly nonreflexive) Banach spaces. We will apply this to obtain the Fenchel Duality Theorem for the sum of two or more proper, convex lower semicontinuous functions under the appropriate constraint qualifications, and also to obtain additional results on the relation between the effective domains of such functions and the domains of their subdifferentials. The other main tool that we use is a standard minimax theorem.

     

On operator monotone and operator convex functions

We establish monotonicity and convexity criteria for a continuous function f: R⁺ → R with respect to any C*-algebra. We obtain an estimate for the measure of noncompactness of the difference of products of the elements of a W*-algebra. We also give a commutativity criterion for a positive τ-measurable operator and a positive operator from a von Neumann algebra.     

On the Lebesgue property of monotone convex functions

The Lebesgue property (order-continuity) of a monotone convex function on a solid vector space of measurable functions is characterized in terms of (1) the weak inf-compactness of the conjugate function on the order-continuous dual space, (2) the attainment of the supremum in the dual representation by order-continuous linear functionals. This generalizes and unifies several recent results obtained in the context of convex risk measures.     

Maximum Lebesgue extension of monotone convex functions

Given a monotone convex function on the space of essentially bounded random variables with the Lebesgue property (order continuity), we consider its extension preserving the Lebesgue property to as big solid vector space of random variables as possible. We show that there exists a maximum such extension, with explicit construction, where the maximum domain of extension is obtained as a (possibly proper) subspace of a natural Orlicz-type space, characterized by a certain uniform integrability property. As an application, we provide a characterization of the Lebesgue property of monotone convex function on arbitrary solid spaces of random variables in terms of uniform integrability and a “nice” dual representation of the function.     

To the theory of operator monotone and operator convex functions

We prove that a real function is operator monotone (operator convex) if the corresponding monotonicity (convexity) inequalities are valid for some normal state on the algebra of all bounded operators in an infinite-dimensional Hilbert space. We describe the class of convex operator functions with respect to a given von Neumann algebra in dependence of types of direct summands in this algebra. We prove that if a function from ℝ⁺ into ℝ⁺ is monotone with respect to a von Neumann algebra, then it is also operator monotone in the sense of the natural order on the set of positive self-adjoint operators affiliated with this algebra.     

The BMO-discrepancy suffers from the curse of dimensionality

We show that the minimal discrepancy of a point set in the d-dimensional unit cube with respect to the BMO seminorm suffers from the curse of dimensionality.     

Double piling structure of matrix monotone functions and of matrix convex functions

There are basic equivalent assertions known for operator monotone functions and operator convex functions in two papers by Hansen and Pedersen. In this note we consider their results as correlation problem between two sequences of matrix n-monotone functions and matrix n-convex functions, and we focus the following three assertions at each label n among them:

(i) f(0)0 and f is n-convex in [0,α),

(ii) For each matrix a with its spectrum in [0,α) and a contraction c in the matrix algebra M_n,

f(cac)cf(a)c,