Tractability properties of the weighted star discrepancy

Tractability properties of various notions of discrepancy have been intensively studied in the last decade. In this paper we consider the so-called weighted star discrepancy which was introduced by Sloan and Wo?niakowski. We show that under a very mild condition on the weights one can obtain tractability with s$s$-exponent zero (s$s$ is the dimension of the point set). In the case of product weights we give a condition such that the weighted star discrepancy is even strongly tractable. Furthermore, we give a lower bound for the weighted star discrepancy for a large class of weights. This bound shows that for such weights one cannot obtain strong tractability.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

On the distribution of Laplacian eigenvalues of trees

For a tree T$T$ with n$n$ vertices, we apply an algorithm due to Jacobs and Trevisan (2011) to study how the number of small Laplacian eigenvalues behaves when the tree is transformed by a transformation defined by Mohar (2007). This allows us to obtain a new bound for the number of eigenvalues that are smaller than 2. We also report our progress towards a conjecture on the number of eigenvalues that are smaller than the average degree.     

Hardness of comparing two run-length encoded strings

In this paper, we consider a commonly used compression scheme called run-length encoding. We provide both lower and upper bounds for the problems of comparing two run-length encoded strings. Specifically, we prove the 3sum-hardness for both the wildcard matching problem and the k$k$-mismatch problem with run-length compressed inputs. Given two run-length encoded strings of m$m$ and n$n$ runs, such a result implies that it is very unlikely to devise an o(mn)$o\left(mn\right)$-time algorithm for either of them. We then present an inplace algorithm running in O(mnlogm)$O(mnlogm)$ time for their combined problem, i.e. k$k$-mismatch with wildcards. We further demonstrate that if the aim is to report the positions of all the occurrences, there exists a stronger barrier of Ω(mnlogm)$\Omega (mnlogm)$-time, matching the running time of our algorithm. Moreover, our algorithm can be easily generalized to a two-dimensional setting without impairing the time and space complexity.     

Fast orthogonal transforms and generation of Brownian paths

We present a number of fast constructions of discrete Brownian paths that can be used as alternatives to principal component analysis and Brownian bridge for stratified Monte Carlo and quasi-Monte Carlo. By fast we mean that a path of length n$n$ can be generated in O(nlog(n))$O(nlog\left(n\right))$ floating point operations. We highlight some of the connections between the different constructions and we provide some numerical examples.     

Variance bounds and existence results for randomly shifted lattice rules

We study the convergence of the variance for randomly shifted lattice rules for numerical multiple integration over the unit hypercube in an arbitrary number of dimensions. We consider integrands that are square integrable but whose Fourier series are not necessarily absolutely convergent. For such integrands, a bound on the variance is expressed through a certain type of weighted discrepancy. We prove existence and construction results for randomly shifted lattice rules such that the variance bounds are almost O(n^−α)$O\left(n^{-\alpha }\right)$, where n$n$ is the number of function evaluations and α>1$\alpha >1$ depends on our assumptions on the convergence speed of the Fourier coefficients. These results hold for general weights, arbitrary n$n$, and any dimension. With additional conditions on the weights, we obtain a convergence that holds uniformly in the dimension, and this provides sufficient conditions for strong tractability of the integration problem. We also show that lattice rules that satisfy these bounds are not difficult to construct explicitly and we provide numerical illustrations of the behaviour of construction algorithms.     

Polynomial-time perfect matchings in dense hypergraphs

Let H be a k-graph on n   vertices, with minimum codegree at least n/k+cn$n/k+cn$ for some fixed c>0$c>0$. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H   or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n/k−cn$n/k-cn$. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.     

Minimum size transversals in uniform hypergraphs

A set of vertices in a hypergraph which meets all the edges is called a transversal. The transversal number τ(H)$\tau \left(H\right)$ of a hypergraph H$H$ is the minimum cardinality of a transversal in H$H$. A classical greedy algorithm for constructing a transversal of small size selects in each step a vertex which has the largest degree in the hypergraph formed by the edges not met yet. The analysis of this algorithm (by Chvátal and McDiarmid (1992)  [3]) gave some upper bounds for τ(H)$\tau \left(H\right)$ in a uniform hypergraph H$H$ with a given number of vertices and edges. We discuss a variation of this greedy algorithm. Analyzing this new algorithm, we obtain upper bounds for τ(H)$\tau \left(H\right)$ which improve the bounds by Chvátal and McDiarmid.     

A general view on computing communities

We define a community structure of a graph as a partition of the vertices into at least two sets with the property that each vertex has connections to relatively many vertices in its own set compared to any other set in the partition and refer to the sets in such a partition as communities  . We show that it is NP-hard to compute a community containing a given set of vertices. On the other hand, we show how to compute a community structure in polynomial time for any connected graph containing at least four vertices except the star graph _Sn$S_n$. Finally, we generalize our results and formally show that counterintuitive aspects are unavoidable for any definition of a community structure with a polynomial time algorithm for computing communities containing specific vertices.     

On the complexity of solving quadratic Boolean systems

A fundamental problem in computer science is that of finding all the common zeros of m$m$ quadratic polynomials in n$n$ unknowns over _F2${\mathbb{F}}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in 4_log2n2ⁿ$4{log}_{2}n{2}^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. We show that, under precise algebraic assumptions on the input system, the deterministic variant of our algorithm has complexity bounded by O(2^0.841n)$O\left(2^{0.841n}\right)$ when m=n$m=n$, while a probabilistic variant of the Las Vegas type has expected complexity O(2^0.792n)$O\left(2^{0.792n}\right)$. Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to 1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as 200, and thus very relevant for cryptographic applications.     

A variant smoothing Newton method for P0-NCP based on a new smoothing function

In this paper, we present a new one-step smoothing Newton method proposed for solving the non-linear complementarity problem with _P0$P_0$-function based on a new smoothing NCP$NCP$-function. We adopt a variant merit function. Our algorithm needs only to solve one linear system of equations and perform one line search per iteration. It shows that any accumulation point of the iteration sequence generated by our algorithm is a solution of _P0-NCP$P_0\text{-}NCP$. Furthermore, under the assumption that the solution set is non-empty and bounded, we can guarantee at least one accumulation point of the generated sequence. Numerical experiments show the feasibility and efficiency of the algorithm.     

Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension

In a celebrated construction, Chen and Skriganov gave explicit examples of point sets achieving the best possible _L2$L_2$-norm of the discrepancy function. We consider the discrepancy function of the Chen–Skriganov point sets in Besov spaces with dominating mixed smoothness and show that they also achieve the best possible rate in this setting. The proof uses a b$b$-adic generalization of the Haar system and corresponding characterizations of the Besov space norm. Results for further function spaces and integration errors are concluded.     

Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs

Homomorphisms to a given graph $H$ ($H$-colourings) are considered in the literature among other graph colouring concepts. We restrict our attention to a special class of $H$-colourings, namely $H$ is assumed to be a star. Our additional requirement is that the set of vertices of a graph $G$ mapped into the central vertex of the star and any other colour class induce in $G$ an acyclic subgraph. We investigate the existence of such a homomorphism to a star of given order. The complexity of this problem is studied. Moreover, the smallest order of a star for which a homomorphism of a given graph $G$ with desired features exists is considered. Some exact values and many bounds of this number for chordal bipartite graphs, cylinders, grids, in particular hypercubes, are given. As an application of these results, we obtain some bounds on the cardinality of the minimum feedback vertex set for specified graph classes.     

Some generalizations of Ekeland-type variational principle with applications to equilibrium problems and fixed point theory

In this paper, we introduce the concept of a Q$Q$-function defined on a quasi-metric space which generalizes the notion of a τ$\tau$-function and a w$w$-distance. We establish Ekeland-type variational principles in the setting of quasi-metric spaces with a Q$Q$-function. We also present an equilibrium version of the Ekeland-type variational principle in the setting of quasi-metric spaces with a Q$Q$-function. We prove some equivalences of our variational principles with Caristi–Kirk type fixed point theorems for multivalued maps, the Takahashi minimization theorem and some other related results. As applications of our results, we derive existence results for solutions of equilibrium problems and fixed point theorems for multivalued maps. We also extend the Nadler’s fixed point theorem for multivalued maps to a Q$Q$-function and in the setting of complete quasi-metric spaces. As a consequence, we prove the Banach contraction theorem for a Q$Q$-function and in the setting of complete quasi-metric spaces. The results of this paper extend and generalize many results appearing recently in the literature.     

A new method for parameter estimation of edge-preserving regularization in image restoration

In image restoration, the so-called edge-preserving regularization method is used to solve an optimization problem whose objective function has a data fidelity term and a regularization term, the two terms are balanced by a parameter λ$\lambda$. In some aspect, the value of λ$\lambda$ determines the quality of images. In this paper, we establish a new model to estimate the parameter and propose an algorithm to solve the problem. In order to improve the quality of images, in our algorithm, an image is divided into some blocks. On each block, a corresponding value of λ$\lambda$ has to be determined. Numerical experiments are reported which show efficiency of our method.     

Multi-dimensional G-Brownian motion and related stochastic calculus under G-expectation

We develop a notion of nonlinear expectation–G$G$-expectation–generated by a nonlinear heat equation with infinitesimal generator G$G$. We first study multi-dimensional G$G$-normal distributions. With this nonlinear distribution we can introduce our G$G$-expectation under which the canonical process is a multi-dimensional G$G$-Brownian motion. We then establish the related stochastic calculus, especially stochastic integrals of Itô’s type with respect to our G$G$-Brownian motion, and derive the related Itô’s formula. We have also obtained the existence and uniqueness of stochastic differential equations under our G$G$-expectation.     

Models for singularity categories

In this article we construct various models for singularity categories of modules over differential graded rings. The main technique is the connection between abelian model structures, cotorsion pairs and deconstructible classes, and our constructions are based on more general results about localization and transfer of abelian model structures. We indicate how recollements of triangulated categories can be obtained model categorically, discussing in detail Krause?s recollement _Kac(Inj(R))→K(Inj(R))→D(R)${\mathrm{K}}_{\mathrm{ac}}(\mathrm{Inj}(R))\to \mathrm{K}(\mathrm{Inj}(R))\to \mathrm{D}(R)$. In the special case of curved mixed Z$\mathbb{Z}$-graded complexes, we show that one of our singular models is Quillen equivalent to Positselski?s contraderived model for the homotopy category of matrix factorizations.