We study the linear statistics of the circular -ensemble with a Stein’s method argument, where the exchangeable pair is generated through circular Dyson Brownian motion. This generalizes previous results obtained in such a way for the CUE and provides a novel approach for studying linear statistics of -ensembles. This approach allows studying simultaneously a collection of linear statistics whose number grows with the dimension of the ensemble. Also this approach requires estimating only low order moments of the linear statistics.

We prove a slightly sharper version of a result of Rider and Vir\’ag who proved that after centering, the logarithm of the absolute value of the characteristic polynomial of the Ginibre ensemble converges in law to the Gaussian Free Field on the unit disk with free boundary conditions (and continued harmonically outside of it). Using their results on the linear statistics of the Ginibre ensemble, we prove a result that removes the ambiguity concerning the ‘constant part’ or zero mode of the field.

We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit `single-letter’ characterization of the per-vertex mutual information between the vertex labels and the graph. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and –in particular– reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing.

Thermal boundary conditions has played an increasingly important role in recent spin glass research and is likely to be also relevant for other disordered systems. Simulating thermal boundary conditions efficiently using population annealing is straightforward and well studied, but much less is known for parallel tempering. Two methods to simulate thermal boundary conditions using parallel tempering are proposed and their performance are studied, the diffusion method and the weighted average method. Numerical results are compared with those of population annealing using the three-dimensional Edwards-Anderson Ising spin glass model as benchmark tests showing the efficiency of the two methods. The relative strengths and weaknesses of all methods are also discussed.

It is a well-known fact that if the random vector converges in distribution to a multivariate normal random variable , then converges in distribution to if is continuous. In this paper, we develop a general method for deriving bounds on the distributional distance between and . To illustrate this method, we obtain several bounds for the case that the -component of is given by , where the are independent. In particular, provided satisfies certain differentiability and growth rate conditions, we obtain an order bound, for smooth test functions, if the first moments of the agree with those of the normal distribution. If is an even integer and is an even function, this convergence rate can be improved further to order . We apply these general bounds to some examples concerning asymptotically chi-square, variance-gamma and chi distributed statistics.

We consider the detection of multiple outliers in Exponential and Pareto samples — as well as general samples that have approximately Exponential or Pareto tails, thanks to Extreme Value Theory. It is shown that a simple ‘robust’ modification of common test statistics makes inward sequential testing — formerly relegated within the literature since the introduction of outward testing — as powerful as, and potentially less error prone than, outward tests. Moreover, inward testing does not require the complicated type 1 error control of outward tests. A variety of test statistics, employed in both block and sequential tests, are compared for their power and errors, in cases including no outliers, dispersed outliers (the classical slippage alternative), and clustered outliers (a case seldom considered). We advocate a density mixture approach for detecting clustered outliers. Tests are found to be highly sensitive to the correct specification of the main distribution (Exponential/Pareto), exposing high potential for errors in inference. Further, in five case studies — financial crashes, nuclear power generation accidents, stock market returns, epidemic fatalities, and cities within countries — significant outliers are detected and related to the concept of ‘Dragon King’ events, defined as meaningful outliers of unique origin.

We investigate how well the graph of a bilinear function   can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor cannot be bounded by a constant independent of . More precisely, we show that for a random bilinear function we have asymptotically almost surely . In addition we characterize the functions such that the McCormick relaxation is equal to the convex hull.

We present a new algorithm for estimating the Personalized PageRank (PPR) between a source and target node on undirected graphs, with sublinear running-time guarantees over the worst-case choice of source and target nodes. Our work builds on a recent line of work on bidirectional estimators for PPR, which obtained sublinear running-time guarantees but in an average case sense, for a uniformly random choice of target node. Crucially, we show how the reversibility of random walks on undirected networks can be exploited to convert average-case to worst-case guarantees. While past bidirectional methods combine forward random walks with reverse local pushes, our algorithm combines forward local pushes with reverse random walks. We also modify our methods to estimate random-walk probabilities for any length distribution, thereby obtaining fast algorithms for estimating general graph diffusions, including the heat kernel, on undirected networks. Whether such worst-case running-time results extend to general graphs, or if PageRank computation is fundamentally easier on undirected graphs as opposed to directed graphs, remains an open question.

We verify a conjecture of Nowakowski and Ottaway that closed Dots-and-Triangles is a first-player win when . We also prove that in both the open and closed Dots-and-Boxes games where is even, the first player can guarantee a tie.

We assume that an individual invests in a financial market with one riskless and one risky asset, with the latter’s price following geometric Brownian motion as in the Black-Scholes model. Under a constant rate of consumption, we find the optimal investment strategy for the individual who wishes to minimize the probability that her wealth drops below some fixed proportion of her maximum wealth to date, the so-called probability of {\it lifetime drawdown}. If maximum wealth is less than a particular value, , then the individual optimally invests in such a way that maximum wealth never increases above its current value. By contrast, if maximum wealth is greater than but less than the safe level, then the individual optimally allows the maximum to increase to the safe level.

We present an automated verification of the well-known modal logic cube in Isabelle/HOL, in which we prove the inclusion relations between the cube’s logics using automated reasoning tools. Prior work addresses this problem but without restriction to the modal logic cube, and using encodings in first-order logic in combination with first-order automated theorem provers. In contrast, our solution is more elegant, transparent and effective. It employs an embedding of quantified modal logic in classical higher-order logic. Automated reasoning tools, such as Sledgehammer with LEO-II, Satallax and CVC4, Metis and Nitpick, are employed to achieve full automation. Though successful, the experiments also motivate some technical improvements in the Isabelle/HOL tool.

Understanding efficiency in high dimensional linear models is a longstanding problem of interest. Classical work with smaller dimensional problems dating back to Huber and Bickel has illustrated the benefits of efficient loss functions. When the number of parameters is of the same order as the sample size , , an efficiency pattern different from the one of Huber was recently established. In this work, we consider the effects of model selection on the estimation efficiency of penalized methods. In particular, we explore whether sparsity, results in new efficiency patterns when . In the interest of deriving the asymptotic mean squared error for regularized M-estimators, we use the powerful framework of approximate message passing. We propose a novel, robust and sparse approximate message passing algorithm (RAMP), that is adaptive to the error distribution. Our algorithm includes many non-quadratic and non-differentiable loss functions. We derive its asymptotic mean squared error and show its convergence, while allowing , with and . We identify new patterns of relative efficiency regarding a number of penalized estimators, when is much larger than . We show that the classical information bound is no longer reachable, even for light–tailed error distributions. We show that the penalized least absolute deviation estimator dominates the penalized least square estimator, in cases of heavy–tailed distributions. We observe this pattern for all choices of the number of non-zero parameters , both and . In non-penalized problems where , the opposite regime holds. Therefore, we discover that the presence of model selection significantly changes the efficiency patterns.

There is an overwhelmingly large literature and algorithms already available on `large scale inference problems’ based on different modeling techniques and cultures. Our primary goal in this paper is \emph{not to add one more new methodology} to the existing toolbox but instead (a) to clarify the mystery how these different simultaneous inference methods are \emph{connected}, (b) to provide an alternative more intuitive derivation of the formulas that leads to \emph{simpler} expressions, and (c) to develop a \emph{unified} algorithm for practitioners. A detailed discussion on representation, estimation, inference, and model selection is given. Applications to a variety of real and simulated datasets show promise. We end with several future research directions.

A distance-based method to reconstruct a phylogenetic tree with leaves takes a distance matrix, symmetric matrix with s in the diagonal, as its input and reconstructs a tree with leaves using tools in combinatorics. A safety radius is a radius from a tree metric (a distance matrix realizing a true tree) within which the input distance matrices must all lie in order to satisfy a precise combinatorial condition under which the distance-based method is guaranteed to return a correct tree. A stochastic safety radius is a safety radius under which the distance-based method is guaranteed to return a correct tree within a certain probability. In this paper we investigated stochastic safety radii for the neighbor-joining (NJ) method and balanced minimal evolution (BME) method for .

For an integer , a (distance) -dominating set of a connected graph is a set of vertices of such that every vertex of is at distance at most~ from some vertex of . The -domination number, , of is the minimum cardinality of a -dominating set of . In this paper, we establish lower bounds on the -domination number of a graph in terms of its diameter, radius and girth. We prove that for connected graphs and , , where denotes the direct product of and .

Motivated by vision-based reinforcement learning (RL) problems, in particular Atari games from the recent benchmark Aracade Learning Environment (ALE), we consider spatio-temporal prediction problems where future (image-)frames are dependent on control variables or actions as well as previous frames. While not composed of natural scenes, frames in Atari games are high-dimensional in size, can involve tens of objects with one or more objects being controlled by the actions directly and many other objects being influenced indirectly, can involve entry and departure of objects, and can involve deep partial observability. We propose and evaluate two deep neural network architectures that consist of encoding, action-conditional transformation, and decoding layers based on convolutional neural networks and recurrent neural networks. Experimental results show that the proposed architectures are able to generate visually-realistic frames that are also useful for control over approximately 100-step action-conditional futures in some games. To the best of our knowledge, this paper is the first to make and evaluate long-term predictions on high-dimensional video conditioned by control inputs.

Low rank methods allow us to capture globally correlated components within matrices. The recent low rank + sparse decomposition further enables us to extract sparse entries along with the globally correlated components. In this paper, we present a natural generalization and consider the decomposition of matrices into components of multiple scales. Such decomposition is well motivated in practice as data matrices often exhibit local correlations in multiple scales. Concretely, we propose a multi-scale low rank modeling that represents a data matrix as a sum of block-wise low rank matrices with increasing scales of block sizes. We then consider the inverse problem of decomposing the data matrix into its multi-scale low rank components and approach the problem via a convex formulation. Theoretically, we show that under an incoherence condition, the convex program recovers the multi-scale low rank components exactly. Practically, we provide guidance on selecting the regularization parameters and incorporate cycle spinning to reduce blocking artifacts. Experimentally, we show that the multi-scale low rank decomposition provides a more intuitive decomposition than conventional low rank methods and demonstrate its effectiveness in four applications, including illumination normalization for face images, motion separation for surveillance videos, multi-scale modeling of the dynamic contrast enhanced magnetic resonance imaging and collaborative filtering exploiting age information.

We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and analysis which is optimal for convex Lipschitz functions. This improves on \cite{dujww13}, which only provides an optimal result for smooth functions; Moreover, the algorithm and analysis are simpler, and readily extend to non-Euclidean problems. The algorithm is based on a small but surprisingly powerful modification of the gradient estimator.

We construct and study branching Markov processes on the space of finite configurations of the state space of a given standard process, controlled by a branching kernel and a killing one. In particular, we may start with a superprocess, obtaining a branching process with state space the finite configurations of positive finite measures on a topological space. A main tool in proving the path regularity of the branching process is the existence of convenient superharmonic functions having compact level sets, allowing the use of appropriate potential theoretical methods.

We show that, under certain natural assumptions, large random plane bipartite maps with a boundary converge after rescaling to a one-parameter family (BD\_L, 0 \textless{} L \textless{} 8) of random metric spaces homeomorphic to the closed unit disk of R^2, the space BD\_L being called the Brownian disk of perimeter L. These results can be seen as an extension of the convergence of uniform plane quadrangulations to the Brownian map, which intuitively corresponds to the limit case where L = 0.

We study the convergence properties of the VR-PCA algorithm introduced by \cite{shamir2015stochastic} for fast computation of leading singular vectors. We prove several new results, including a formal analysis of a block version of the algorithm, and convergence from random initialization. We also make a few observations of independent interest, such as how pre-initializing with just a single exact power iteration can significantly improve the runtime of stochastic methods, and what are the convexity and non-convexity properties of the underlying optimization problem.

A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks to find whether there exist at most edges in the input graph whose deletion results in a diamond-free graph. The problem is known to be fixed-parameter tractable and a polynomial kernel of vertices is found by Y. Cai [MPhil Thesis, 2012]. In this paper, we give an improved kernel of vertices for Diamond-free Edge Deletion. We complement the result by proving that the problem is NP-complete and cannot be solved in time , unless Exponential Time Hypothesis fails.

We propose a constructive algorithm, called the Tensor-based Kronecker Product (KP) Singular Value Decomposition (TKPSVD), that decomposes an arbitrary real matrix into a finite sum of KP terms with an arbitrary number of factors, namely . The algorithm relies on reshaping and permuting the original matrix into a -way tensor, after which its tensor-train rank-1 (TTr1) decomposition is computed. The TTr1 decomposition exhibits a singular value profile as the SVD, allowing for a low-rank truncated series whenever the singular value decay is prominent. It also permits a straightforward way to compute the relative approximation error without the need to explicitly compute the approximant. We move on to show that for many different structured matrices, the KP factor matrices are guaranteed to inherit this structure. In providing these proofs we generalize the notion of symmetric matrices into general symmetric matrices.

Vector-space word representations based on neural network models can include linguistic regularities, enabling semantic operations based on vector arithmetic. In this paper, we explore an analogous approach applied to images. We define a methodology to obtain large and sparse vectors from individual images and image classes, by using a pre-trained model of the GoogLeNet architecture. We evaluate the vector-space after processing 20,000 ImageNet images, and find it to be highly correlated with WordNet lexical distances. Further exploration of image representations shows how semantically similar elements are clustered in that space, regardless of large visual variances (e.g., 118 kinds of dogs), and how the space distinguishes abstract classes of objects without supervision (e.g., living things from non-living things). Finally, we consider vector arithmetic, and find them to be related with image concatenation (e.g., ‘horse cart – horse = rickshaw’), image overlap (‘Panda – Brown bear = Skunk’) and regularities (‘Panda is to Brown bear as Skunk is to Badger’). All these results indicate that visual semantics contain a large amount of general information, and that those semantics can be extracted as vector representations from neural network models, making them available for further learning and reasoning.

Pairwise comparisons between alternatives are a well-established tool to decompose decision problems into smaller and more easily tractable sub-problems. However, due to our limited rationality, the subjective preferences expressed by decision makers over pairs of alternatives can hardly ever be consistent. Therefore, several inconsistency indices have been proposed in the literature to quantify the extent of the deviation from complete consistency. Only recently, a set of axioms has been proposed to define a family of functions representing inconsistency indices. The scope of this paper is to expand the axiomatic framework by adding and justifying a new axiom.

A current trend in networking and cloud computing is to provide compute resources at widely dispersed places; this is exemplified by developments such as Network Function Virtualisation. This paves the way for wide-area service deployments with improved service quality: e.g, a nearby server can reduce the user-perceived response times. But always using the nearest server can be a bad decision if that server is already highly utilised. This paper formalises the two related problems of allocating resources at different locations and assigning users to them with the goal of minimising the response times for a given number of resources to use — a non-linear capacitated facility location problem with integrated queuing systems. To efficiently handle the non-linearity, we introduce five linear problem approximations and adapt the currently best heuristic for a similar problem to our scenario. All six approaches are compared in experiments for solution quality and solving time. Surprisingly, our best optimisation formulation outperforms the heuristic in both time and quality. Additionally, we evaluate the influence ot resource distributions in the network on the response time: Cut by half for some configurations. The presented formulations are applicable to a broader optimisation domain.

The behaviour of the maximal displacement of a supercritical branching random walk has been a subject of intense studies for a long time. But only recently the case of time-inhomogeneous branching has gained focus. The contribution of this paper is to analyse a time-inhomogeneous model with two level of randomness. In the first step a sequence of branching law is sampled independently according to a distribution on point measures. Conditionally on the realisation of this sequence (called environment) we define a branching random walk and find the asymptotic behaviour of its maximal particle. It is of the form , where is a function of the environment that behaves as a random walk and is a constant. It turns out that the logarithmic correction is bigger than the usual one of the homogenous branching case.

Auditability is crucial for data outsourcing, facilitating accountability and identifying data loss or corruption incidents in a timely manner, reducing in turn the risks from such losses. In recent years, in synch with the growing trend of outsourcing, a lot of progress has been made in designing probabilistic (for efficiency) provable data possession (PDP) schemes. However, even the recent and advanced PDP solutions that do deal with dynamic data, do so in a limited manner, and for only the latest version of the data. A naive solution treating different versions in isolation would work, but leads to tremendous overheads, and is undesirable. In this paper, we present algorithms to achieve full persistence (all intermediate configurations are preserved and are modifiable) for an optimized skip list (known as FlexList) so that versioned data can be audited. The proposed scheme provides deduplication at the level of logical, variable sized blocks, such that only the altered parts of the different versions are kept, while the persistent data-structure facilitates access (read) of any arbitrary version with the same storage and process efficiency that state-of-the-art dynamic PDP solutions provide for only the current version, while commit (write) operations incur around 5% additional time. Furthermore, the time overhead for auditing arbitrary versions in addition to the latest version is imperceptible even on a low-end server…

In this paper, we investigate the problem of optimization multivariate performance measures, and propose a novel algorithm for it. Different from traditional machine learning methods which optimize simple loss functions to learn prediction function, the problem studied in this paper is how to learn effective hyper-predictor for a tuple of data points, so that a complex loss function corresponding to a multivariate performance measure can be minimized. We propose to present the tuple of data points to a tuple of sparse codes via a dictionary, and then apply a linear function to compare a sparse code against a give candidate class label. To learn the dictionary, sparse codes, and parameter of the linear function, we propose a joint optimization problem. In this problem, the both the reconstruction error and sparsity of sparse code, and the upper bound of the complex loss function are minimized. Moreover, the upper bound of the loss function is approximated by the sparse codes and the linear function parameter. To optimize this problem, we develop an iterative algorithm based on descent gradient methods to learn the sparse codes and hyper-predictor parameter alternately. Experiment results on some benchmark data sets show the advantage of the proposed methods over other state-of-the-art algorithms.

We study conformal iterated function systems (IFS) with arbitrary overlaps, and measures on limit sets , which are projections of equilibrium measures with respect to a certain lift map on . No type of Open Set Condition is assumed. We introduce a notion of overlap function and overlap number for such a measure with respect to ; and, in particular a notion of (topological) overlap number . These notions take in consideration the -chains between points in the limit set. We prove that is related to a conditional entropy of with respect to the lift . Various types of projections to of invariant measures are studied. We obtain upper estimates for the Hausdorff dimension of on , by using pressure functions and . In particular, this applies to projections of Bernoulli measures on . Next, we apply the results to Bernoulli convolutions for , which correspond to self-similar measures determined by composing, with equal probabilities, the contractions of an IFS with overlaps . We prove that for all , there exists a relation between and the overlap number . The number is approximated with integrals on with respect to the uniform Bernoulli measure . We also estimate for certain values of .

We consider spaces with free involutions that satisfy the Borsuk–Ulam theorems (BUT-spaces). There are several equivalent definitions for BUT-spaces that can be considered as its properties. Our main technical tool is Yang’s cohomological index.

We analyst in detail a new approach to the monitoring and forecasting of the onset of transitions in high dimensional complex systems (see Phys. Rev. Lett . vol. 113, 264102 (2014)) by application to the Tangled Nature Model of evolutionary ecology and high dimensional replicator systems with a stochastic element. A high dimensional stability matrix is derived for the mean field approximation to the stochastic dynamics. This allows us to determine the stability spectrum about the observed quasi-stable configurations. From overlap of the instantaneous configuration vector of the full stochastic system with the eigenvectors of the unstable directions of the deterministic mean field approximation we are able to construct a good early-warning indicator of the transitions occurring intermittently. Inspired by these findings we are able to suggest an alternative simplified applicable forecasting procedure which only makes use of observable data streams.

Consider mobile sensors placed independently at random with the uniform distribution on a barrier represented as the unit line segment . The sensors have identical sensing radius, say . When a sensor is displaced on the line a distance equal to it consumes energy (in movement) which is proportional to some (fixed) power of the distance traveled. The energy consumption of a system of sensors thus displaced is defined as the sum of the energy consumptions for the displacement of the individual sensors. We focus on the problem of energy efficient displacement of the sensors so that in their final placement the sensor system ensures coverage of the barrier and the energy consumed for the displacement of the sensors to these final positions is minimized in expectation. In particular, we analyze the problem of displacing the sensors from their initial positions so as to attain coverage of the unit interval and derive trade-offs for this displacement as a function of the sensor range. We obtain several tight bounds in this setting thus generalizing several of the results of [8] to any power .

We present families of undirected and directed Cayley graphs whose construction is motivated by that of the De Bruijn graphs. One approach yields, for every large and for values of taken from a large interval, the largest known Cayley graphs and digraphs of diameter and degree . Another method yields, for every and infinitely many values of , Cayley graphs and digraphs of diameter and degree whose order is exponentially larger in than any previously constructed. In the directed case, these are within a polynomial factor of the Moore bound.

In this paper an improved Cuckoo Search Algorithm is developed to allow for an efficient and robust calibration of the Heston option pricing model for American options. Calibration of stochastic volatility models like the Heston is significantly harder than classical option pricing models as more parameters have to be estimated. The difficult task of calibrating one of these models to American Put options data is the main objective of this paper. Numerical results are shown to substantiate the suitability of the chosen method to tackle this problem.

We address the issue of the reducibility of the dynamics on a multilayer network to an equivalent process on an aggregated single-layer network. As a typical example of models for opinion formation in social networks, we implement the voter model on a two-layer multiplex network, and we study its dynamics as a function of two control parameters, namely the fraction of edges simultaneously existing in both layers of the network (edge overlap), and the fraction of nodes participating in both layers (interlayer connectivity or degree of multiplexity). We compute the asymptotic value of the number of active links (interface density) in the thermodynamic limit, and the time to reach an absorbing state for finite systems, and we compare the numerical results with the analytical predictions on equivalent single-layer networks obtained through various possible aggregation procedures. We find a large region of parameters where the interface density of large multiplexes gives systematic deviations from that of the aggregates. We show that neither of the standard aggregation procedures is able to capture the highly nonlinear increase in the lifetime of a finite size multiplex at small interlayer connectivity. These results indicate that multiplexity should be appropriately taken into account when studying voter model dynamics, and that, in general, single-layer approximations might be not accurate enough to properly understand processes occurring on multiplex networks, since they might flatten out relevant dynamical details.

We explore the statistical properties of the Casimir-Polder potential between a dielectric sphere and a three-dimensional heterogeneous medium, by means of extensive numerical simulations based on the scattering theory of Casimir forces. The simulations allow us to confirm recent predictions for the mean and standard deviation of the Casimir potential, and give us access to its full distribution function in the limit of a dilute distribution of heterogeneities. These predictions are compared with a simple statistical model based on a pairwise summation of the individual contributions of the constituting elements of the medium.

The interplay between local, repulsive interactions and disorder acting only on one spin orientation of lattice fermions (‘spin-dependent disorder’) is investigated. The nonmagnetic disorder vs. interaction phase diagram is computed using Dynamical Mean-Field Theory in combination with the geometric average over disorder. The latter determines the typical local density of states and is therefore sensitive to Anderson localization. The effect of spin-dependent disorder is found to be very different from that of conventional disorder. In particular, it destabilizes the metallic solution and leads to a novel spin-selective, localized phase at weak interactions and strong disorder.

We present an effective hydrodynamic theory of electronic transport in graphene in the interaction-dominated regime. We derive the emergent hydrodynamic description from the microscopic Boltzmann kinetic equation taking into account dissipation due to Coulomb interaction and find the viscosity of Dirac fermions in graphene for arbitrary densities. The viscous terms have a dramatic effect on transport coefficients in clean samples at high temperatures. Within linear response, we show that viscosity manifests itself in the nonlocal conductivity as well as dispersion of hydrodynamic plasmons. Beyond linear response, we apply the derived nonlinear hydrodynamics to the problem of hot spot relaxation in graphene.

The strong chromatic index of a multigraph is the minimum such that the edge set can be -colored requiring that each color class induces a matching. We verify a conjecture of Faudree, Gy\'{a}rf\'{a}s, Schelp and Tuza, showing that every planar multigraph with maximum degree at most 3 has strong chromatic index at most 9, which is sharp.

A distributed algorithm performs local computations on pieces of input and communicates the results through given communication links. When processing a massive graph in a distributed algorithm, local outputs must be configured as a solution to a graph problem without shared memory and with few rounds of communication. In this paper we consider the problem of computing a local cluster in a massive graph in the distributed setting. Computing local clusters are of certain application-specific interests, such as detecting communities in social networks or groups of interacting proteins in biological networks. When the graph models the computer network itself, detecting local clusters can help to prevent communication bottlenecks. We give a distributed algorithm that computes a local cluster in time that depends only logarithmically on the size of the graph in the CONGEST model. In particular, when the value of the optimal local cluster is known, the algorithm runs in time entirely independent of the size of the graph and depends only on error bounds for approximation. We also show that the local cluster problem can be computed in the k-machine distributed model in sublinear time. The speedup of our local cluster algorithms is mainly due to the use of our distributed algorithm for heat kernel pagerank.

The article is devoted to the estimation of the rate of convergence of integral functionals of a Markov process. Under the assumption that the given Markov process admits a transition probability density which is differentiable in and the derivative has an integrable upper bound of a certain type, we derive the accuracy rates for strong and weak approximations of the functionals by Riemannian sums. Some examples are provided.