Search

We introduce the notion of quasimonotone polar of a multivalued operator, in a similar way as the well-known monotone polar due to Martinez-Legaz and Svaiter. We first recover several properties similar to the monotone polar, including a characterization in terms of normal cones. Next, we use it to analyze certain aspects of maximal (in the sense of graph inclusion) quasimonotonicity, and its relation to the notion of maximal quasimonotonicity introduced by Aussel and Eberhard. Furthermore, we study the connections between quasimonotonicity and Minty Variational Inequality Problems., Comment: 11 pages

In a $d$-dimensional convex body $K$ random points $X_0, \dots, X_d$ are chosen. Their convex hull is a random simplex. The expected volume of a random simplex is monotone under set inclusion, if $K \subset L$ implies that the expected volume of a random simplex in $K$ is smaller than the expected volume of a random simplex in $L$. Continuing work of Rademacher, it is shown that moments of the volume of random simplices are in general not monotone under set inclusion.

In this article we consider means of positive bounded linear operators on a Hilbert space. We present a complete theory that provides a framework which extends the theory of the Karcher mean, its approximating matrix power means, and a large part of Kubo-Ando theory to arbitrary many variables, in fact, to the case of probability measures with bounded support on the cone of positive definite operators. This framework characterizes each operator mean extrinsically as unique solutions of generalized Karcher equations which are obtained by exchanging the matrix logarithm function in the Karcher equation to arbitrary operator monotone functions over the positive real half-line. If the underlying Hilbert space is finite dimensional, then these generalized Karcher equations are Riemannian gradients of convex combinations of strictly geodesically convex log-determinant divergence functions, hence these new means are the global minimizers of them, in analogue to the case of the Karcher mean as pointed out. Our framework is based on fundamental contraction results with respect to the Thompson metric, which provides us nonlinear contraction semigroups in the cone of positive definite operators that form a decreasing net approximating these operator means in the strong topology from above., Comment: arXiv admin note: text overlap with arXiv:1208.5603

This paper presents some partial answers to the following question. QUESTION. If a normal space X is the union of an increasing sequence of open sets U(1), U(2), U(3) ... such that each U(n) contracts to a point in X, must X be contractible? The main results of the paper are: THEOREM 1. If a normal space X is the union of a sequence of open subsets { U(n) } such that the closure of U(n) is contained in U(n+1) and U(n) contracts to a point in U(n+1) for each n > 0, then X is contractible. COROLLARY 2. If a locally compact sigma-compact normal space X is the union of an increasing sequence of open sets U(1), U(2), U(3) ... such that each U(n) contracts to a point in X, then X is contractible., In the revised version, a proof of Lemma 5 has been added and a few other minor changes have been made. In the second revision a few minor stylistic changes were made

Resource theory is a widely-applicable framework for analyzing the physical resources required for given tasks, such as computation, communication, and energy extraction. In this paper, we propose a general scheme for analyzing resource theories based on resource destroying maps, which leave resource-free states unchanged but erase the resource stored in all other states. We introduce a group of general conditions that determine whether a quantum operation exhibits typical resource-free properties in relation to a given resource destroying map. Our theory reveals fundamental connections among basic elements of resource theories, in particular, free states, free operations, and resource measures. In particular, we define a class of simple resource measures that can be calculated without optimization, and that are monotone nonincreasing under operations that commute with the resource destroying map. We apply our theory to the resources of coherence and quantum correlations (e.g., discord), two prominent features of nonclassicality., Comment: 12 pages including Supplemental Material, published version

In this work a theory is developed for unifying large classes of nonlinear discrete-time dynamical systems obeying a superposition of a weighted maximum or minimum type. The state vectors and input-output signals evolve on nonlinear spaces which we call complete weighted lattices and include as special cases the nonlinear vector spaces of minimax algebra. Their algebraic structure has a polygonal geometry. Some of the special cases unified include max-plus, max-product, and probabilistic dynamical systems. We study problems of representation in state and input-output spaces using lattice monotone operators, state and output responses using nonlinear convolutions, solving nonlinear matrix equations using lattice adjunctions, stability and controllability. We outline applications in state-space modeling of nonlinear filtering; dynamic programming (Viterbi algorithm) and shortest paths (distance maps); fuzzy Markov chains; and tracking audio-visual salient events in multimodal information streams using generalized hidden Markov models with control inputs., Comment: 38 pages, 4 figures

We introduce a simple yet effective sampling-based planner that is tailored for bottleneck pathfinding: Given an implicitly-defined cost map M : Rd A R, which assigns to every point in space a real value, we wish to find a path connecting two given points, which minimizes the maximal value with respect to M. We demonstrate the capabilities of our algorithm, which we call bottleneck tree (BTT), on several challenging instances of the problem involving multiple agents, where it outperforms the state-of-the-art cost-map planning technique T-RRT∗. In addition to its efficiency, BTT requires the tuning of only a single parameter: the number of samples. On the theoretical side, we study the asymptotic properties of our method and consider the special setting where the computed trajectories must be monotone in all coordinates. This constraint arises in cases where the problem involves the coordination of multiple agents that are restricted to forward motions along predefined paths.

We consider two isotonic smooth estimators for a monotone baseline hazard in the Cox model, a maximum smooth likelihood estimator and a Grenander-type estimator based on the smoothed Breslow estimator for the cumulative baseline hazard. We show that they are both asymptotically normal at rate $n^{m/(2m+1)}$, where $m\geq 2$ denotes the level of smoothness considered, and we relate their limit behavior to kernel smoothed isotonic estimators studied in Lopuha\"a and Musta (2016). It turns out that the Grenander-type estimator is asymptotically equivalent to the kernel smoothed isotonic estimators, while the maximum smoothed likelihood estimator exhibits the same asymptotic variance but a different bias. Finally, we present numerical results on pointwise confidence intervals that illustrate the comparable behavior of the two methods., Comment: arXiv admin note: text overlap with arXiv:1609.06617

The aim of this article is to provide a simple sampling procedure to reconstruct any monotone path from its signature. For every $N$, we sample a lattice path of $N$ steps with weights given by the coefficient of the corresponding word in the signature. We show that these weights on lattice paths satisfy the large deviations principle. In particular, this implies that the probability of picking up a “wrong” path is exponentially small in $N$. The argument relies on a probabilistic interpretation of the signature for monotone paths.

As a continuation of previous work of the first author with Ranjbar [‘A variational inequality in complete CAT(0) spaces’, J. Fixed Point Theory Appl. 17 (2015), 557–574] on a special form of variational inequalities in Hadamard spaces, in this paper we study equilibrium problems in Hadamard spaces, which extend variational inequalities and many other problems in nonlinear analysis. In this paper, first we study the existence of solutions of equilibrium problems associated with pseudo-monotone bifunctions with suitable conditions on the bifunctions in Hadamard spaces. Then, to approximate an equilibrium point, we consider the proximal point algorithm for pseudo-monotone bifunctions. We prove existence of the sequence generated by the algorithm in several cases in Hadamard spaces. Next, we introduce the resolvent of a bifunction in Hadamard spaces. We prove convergence of the resolvent to an equilibrium point. We also prove $\triangle$-convergence of the sequence generated by the proximal point algorithm to an equilibrium point of the pseudo-monotone bifunction and also the strong convergence under additional assumptions on the bifunction. Finally, we study a regularization of Halpern type and prove the strong convergence of the generated sequence to an equilibrium point without any additional assumption on the pseudo-monotone bifunction. Some examples in fixed point theory and convex minimization are also presented.

We present a method for solving linearly constrained convex optimization problems, which is based on the application of known algorithms for finding zeros of the sum of two monotone operators (presented by Eckstein and Svaiter) to the dual problem. We establish convergence rates for the new method, and we present applications to TV denoising and compressed sensing problems.

This work deals with a numerical method for solving a mean-field type control problem with congestion. It is the continuation of an article by the same authors, in which suitably defined weak solutions of the system of partial differential equations arising from the model were discussed and existence and uniqueness were proved. Here, the focus is put on numerical methods: a monotone finite difference scheme is proposed and shown to have a variational interpretation. Then an Alternating Direction Method of Multipliers for solving the variational problem is addressed. It is based on an augmented Lagrangian. Two kinds of boundary conditions are considered: periodic conditions and more realistic boundary conditions associated to state constrained problems. Various test cases and numerical results are presented.

This Note aims at presenting a simple and efficient procedure to derive the structure of high-order corrector estimates for the homogenization limit applied to a semi-linear elliptic equation posed in perforated domains. Our working technique relies on monotone iterations combined with formal two-scale homogenization asymptotics. It can be adapted to handle more complex scenarios including for instance nonlinearities posed at the boundary of perforations and the vectorial case, when the model equations are coupled only through the nonlinear production terms., Comment: 1 figure

Given a sequence of $n$ independent random variables with common continuous distribution, we propose a simple adaptive online policy that selects a monotone increasing subsequence. We show that the expected number of monotone increasing selections made by such a policy is within $O(\log n)$ of optimal. Our construction provides a direct and natural way for proving the $O(\log n)$-optimality gap. An earlier proof of the same result made crucial use of a key inequality of Bruss and Delbaen (2001) and of de-Poissonization., Comment: 12 pages

We consider the simplest one-constant model, put forward by J. Ericksen, for nematic liquid crystals with variable degree of orientation. The equilibrium state is described by a director field $\mathbf{n}$ and its degree of orientation $s$, where the pair $(s, \mathbf{n})$ minimizes a sum of Frank-like energies and a double well potential. In particular, the Euler-Lagrange equations for the minimizer contain a degenerate elliptic equation for $\mathbf{n}$, which allows for line and plane defects to have finite energy. We present a structure preserving discretization of the liquid crystal energy with piecewise linear finite elements that can handle the degenerate elliptic part without regularization, and show that it is consistent and stable. We prove $\Gamma$-convergence of discrete global minimizers to continuous ones as the mesh size goes to zero. We develop a quasi-gradient flow scheme for computing discrete equilibrium solutions and prove it has a strictly monotone energy decreasing property. We present simulations in two and three dimensions to illustrate the method's ability to handle non-trivial defects. A music video summary of the paper is available on YouTube: "Mathematical Modeling and Simulation of Nematic Liquid Crystals (A Montage)," http://www.youtube.com/watch?v=pWWw7\_6cQ-U, Comment: keywords: liquid crystals, finite element method, gamma-convergence, gradient flow, line defect, plane defect

We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant {depth}. The goal is to select a subset of $k$ species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is $(1-\frac{1}{\sqrt{e}})$. This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no $(1-1/e+\epsilon)$-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting., Comment: in Algorithmica (2015)

We show that for a monic polynomial $f(x)$ over a number field $K$ containing a global permutation polynomial of degree $>1$ as its composition factor, the Newton Polygon of $f\mod\mathfrak p$ does not converge for $\mathfrak p$ passing through all finite places of $K$. In the rational number field case, our result is the "only if" part of a conjecture of Wan about limiting Newton polygons.

As is well known, many classes of markets have efficient equilibria, but this depends on agents being non-strategic, i.e. that they declare their true demands when offered goods at particular prices, or in other words, that they are price-takers. An important question is how much the equilibria degrade in the face of strategic behavior, i.e. what is the Price of Anarchy (PoA) of the market viewed as a mechanism? Often, PoA bounds are modest constants such as 4/3 or 2. Nonetheless, in practice a guarantee that no more than 25% or 50% of the economic value is lost may be unappealing. This paper asks whether significantly better bounds are possible under plausible assumptions. In particular, we look at how these worst case guarantees improve in the following large settings. -Large Walrasian auctions: These are auctions with many copies of each item and many agents. We show that the PoA tends to 1 as the market size increases, under suitable conditions, mainly that there is some uncertainty about the numbers of copies of each good and demands obey the gross substitutes condition. We also note that some such assumption is unavoidable. -Large Fisher markets: Fisher markets are a class of economies that has received considerable attention in the computer science literature. A large market is one in which at equilibrium, each buyer makes only a small fraction of the total purchases; the smaller the fraction, the larger the market. Here the main condition is that demands are based on homogeneous monotone utility functions that satisfy the gross substitutes condition. Again, the PoA tends to 1 as the market size increases. Furthermore, in each setting, we quantify the tradeoff between market size and the PoA.

In this article, we consider the following question: Can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples ( OPS ). In OPS , we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions that are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.

We consider a robust formulation, introduced by Krause et al. (2008), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to $\tau$ elements from the chosen set. For the fundamental case of $\tau=1$, we give a deterministic $(1-1/e)-1/\Theta(m)$ approximation algorithm, where $m$ is an input parameter and number of queries scale as $O(n^{m+1})$. In the process, we develop a deterministic $(1-1/e)-1/\Theta(m)$ approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (2010), we show a randomized $(1-1/e)-\epsilon$ approximation for constant $\tau$ and $\epsilon\leq \frac{1}{\tilde{\Omega}(\tau)}$, making $O(n^{1/\epsilon^3})$ queries. Further, for $\tau\ll \sqrt{k}$, we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robust maximization subject to an Independence System., Comment: Preliminary version in IPCO 2016

We address the problem of quantifying the cryptographic content of probability distributions, in relation to an application to secure multi-party sampling against a passive t-adversary. We generalize a recently introduced notion of assisted common information of a pair of correlated sources to that of K sources and define a family of monotone rate regions indexed by K. This allows for a simple characterization of all t-private distributions that can be statistically securely sampled without any auxiliary setup of pre-shared noisy correlations. We also give a new monotone called the residual total correlation that admits a simple operational interpretation. Interestingly, for sampling with non-trivial setups (K > 2) in the public discussion model, our definition of a monotone region differs from the one by Prabhakaran and Prabhakaran (ITW 2012)., 6 pages, 2 figures, v2: Improved readability

Unaggregated data, in streamed or distributed form, is prevalent and come from diverse application domains which include interactions of users with web services and IP traffic. Data elements have {\em keys} (cookies, users, queries) and elements with different keys interleave. Analytics on such data typically utilizes statistics stated in terms of the frequencies of keys. The two most common statistics are {\em distinct}, which is the number of active keys in a specified segment, and {\em sum}, which is the sum of the frequencies of keys in the segment. Both are special cases of {\em cap} statistics, defined as the sum of frequencies {\em capped} by a parameter $T$, which are popular in online advertising platforms. Aggregation by key, however, is costly, requiring state proportional to the number of distinct keys, and therefore we are interested in estimating these statistics or more generally, sampling the data, without aggregation. We present a sampling framework for unaggregated data that uses a single pass (for streams) or two passes (for distributed data) and state proportional to the desired sample size. Our design provides the first effective solution for general frequency cap statistics. Our $\ell$-capped samples provide estimates with tight statistical guarantees for cap statistics with $T=\Theta(\ell)$ and nonnegative unbiased estimates of {\em any} monotone non-decreasing frequency statistics. An added benefit of our unified design is facilitating {\em multi-objective samples}, which provide estimates with statistical guarantees for a specified set of different statistics, using a single, smaller sample., Comment: 21 pages, 4 figures, preliminary version will appear in KDD 2015

This paper studies the last-column-block-augmented northwest-corner truncation (LC-block-augmented truncation, for short) of discrete-time block-monotone Markov chains under subgeometric drift conditions. The main result of this paper is to present an upper bound for the total variation distance between the stationary probability vectors of a block-monotone Markov chain and its LC-block-augmented truncation. The main result is extended to Markov chains that themselves may not be block monotone but are block-wise dominated by block-monotone Markov chains satisfying modified drift conditions. Finally, as an application of the obtained results, the GI/G/1-type Markov chain is considered.

We construct a general measure for detecting the quantum speedup in both closed and open systems. The speed measure is based on the changing rate of the position of quantum states on a manifold with appropriate monotone Riemannian metrics. Any increase in speed is a clear signature of dynamical speedup. To clarify the mechanisms for quantum speedup, we first introduce the concept of longitudinal and transverse types of speedup: the former stems from the time evolution process itself with fixed initial conditions, while the latter is a result of adjusting initial conditions. We then apply the proposed measure to several typical closed and open quantum systems, illustrating that quantum coherence (or entanglement) and the memory effect of the environment together can become resources for longitudinally or transversely accelerating dynamical evolution under specific conditions and assumptions., Comment: 7 pages, 4 figures; Accepted for publication in New Journal of Physics

We prove that a monotone Lagrangian torus in $S^2\times S^2$ which suitably sits in a symplectic fibration with two sections in its complement is Hamiltonian isotopic to the Clifford torus., Comment: 40 pages, 10 figures

We consider the problem of tracking with small relative error an integer function $f(n)$ defined by a distributed update stream $f'(n)$. Existing streaming algorithms with worst-case guarantees for this problem assume $f(n)$ to be monotone; there are very large lower bounds on the space requirements for summarizing a distributed non-monotonic stream, often linear in the size $n$ of the stream. Input streams that give rise to large space requirements are highly variable, making relatively large jumps from one timestep to the next. However, streams often vary slowly in practice. What has heretofore been lacking is a framework for non-monotonic streams that admits algorithms whose worst-case performance is as good as existing algorithms for monotone streams and degrades gracefully for non-monotonic streams as those streams vary more quickly. In this paper we propose such a framework. We introduce a new stream parameter, the "variability" $v$, deriving its definition in a way that shows it to be a natural parameter to consider for non-monotonic streams. It is also a useful parameter. From a theoretical perspective, we can adapt existing algorithms for monotone streams to work for non-monotonic streams, with only minor modifications, in such a way that they reduce to the monotone case when the stream happens to be monotone, and in such a way that we can refine the worst-case communication bounds from $\Theta(n)$ to $\tilde{O}(v)$. From a practical perspective, we demonstrate that $v$ can be small in practice by proving that $v$ is $O(\log f(n))$ for monotone streams and $o(n)$ for streams that are "nearly" monotone or that are generated by random walks. We expect $v$ to be $o(n)$ for many other interesting input classes as well., Comment: submitted to ICALP 2015 (here, fullpage formatting)

For both unitary and open qubit dynamics, we compare asymmetry monotone-based bounds on the minimal time required for an initial qubit state to evolve to a final qubit state from which it is probabilistically distinguishable with fixed minimal error probability (i.e., the minimal error distinguishability time). For the case of unitary dynamics generated by a time-independent Hamiltonian, we derive a necessary and sufficient condition on two asymmetry monotones that guarantees that an arbitrary state of a two-level quantum system or a separable state of $N$ two-level quantum systems will unitarily evolve to another state from which it can be distinguished with a fixed minimal error probability $\delta \in [0,1/2]$. This condition is used to order the set of qubit states based on their distinguishability time, and to derive an optimal release time for driven two-level systems such as those that occur, e.g., in the Landau-Zener problem. For the case of non-unitary dynamics, we compare three lower bounds to the distinguishability time, including a new type of lower bound which is formulated in terms of the asymmetry of the uniformly time-twirled initial system-plus-environment state with respect to the generator $H_{SE}$ of the Stinespring isometry corresponding to the dynamics, specifically, in terms of $\Vert [H_{SE},\rho_{\text{av}}(\tau)]\Vert_{1}$, where $\rho_{\text{av}}(\tau):={1\over \tau}\int_{0}^{\tau}dt\, e^{-iH_{SE}t}\rho \otimes \vert 0\rangle_{E}\langle 0\vert_{E} e^{iH_{SE}t}$., Comment: 13 pages, 4 figures

We propose new concepts in order to analyze and model the dependence structure between two time series. Our methods rely exclusively on the order structure of the data points. Hence, the methods are stable under monotone transformations of the time series and robust against small perturbations or measurement errors. Ordinal pattern dependence can be characterized by four parameters. We propose estimators for these parameters, and we calculate their asymptotic distributions. Furthermore, we derive a test for structural breaks within the dependence structure. All results are supplemented by simulation studies and empirical examples. For three consecutive data points attaining different values, there are six possibilities how their values can be ordered. These possibilities are called ordinal patterns. Our first idea is simply to count the number of coincidences of patterns in both time series, and to compare this with the expected number in the case of independence. If we detect a lot of coincident patterns, this means that the up-and-down behavior is similar. Hence, our concept can be seen as a way to measure non-linear `correlation'. We show in the last section, how to generalize the concept in order to capture various other kinds of dependence., Comment: 32 pages, 11 figures

We investigate the convergence rates of the trajectories generated by implicit first and second order dynamical systems associated to the determination of the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space. We show that these trajectories strongly converge with exponential rate to a zero of the sum, provided the latter is strongly monotone. We derive from here convergence rates for the trajectories generated by dynamical systems associated to the minimization of the sum of a proper, convex and lower semicontinuous function with a smooth convex one provided the objective function fulfills a strong convexity assumption. In the particular case of minimizing a smooth and strongly convex function, we prove that its values converge along the trajectory to its minimum value with exponential rate, too., Comment: arXiv admin note: text overlap with arXiv:1503.04652

This paper describes our hunt for the solver of Problem 157 in the Scottish Book, a problem originally posed by A.~J. (Gus) Ward in 1937. We first make the observation that a theorem of Richard O'Malley from 1975 yields an immediate positive solution. A further look at O'Malley's references revealed a 1970 paper by Donald Ornstein that we now believe contains the first solution of {\em SB 157}. We isolate the common elements in the machinery used by both Ornstein and O'Malley and discuss several consequences. We also examine an example function given by Ornstein. There are some difficulties with this function but we provide a fix, and show moreover that functions of that kind are typical in the sense of the Baire category theorem., Comment: 12 pages

We present a collection of new results on problems related to 3SUM, including: 1. The first truly subquadratic algorithm for $\ \ \ \ \ $ 1a. computing the (min,+) convolution for monotone increasing sequences with integer values bounded by $O(n)$, $\ \ \ \ \ $1b. solving 3SUM for monotone sets in 2D with integer coordinates bounded by $O(n)$, and $\ \ \ \ \ $1c. preprocessing a binary string for histogram indexing (also called jumbled indexing). The running time is: $O(n^{(9+\sqrt{177})/12}\,\textrm{polylog}\,n)=O(n^{1.859})$ with randomization, or $O(n^{1.864})$ deterministically. This greatly improves the previous $n^2/2^{\Omega(\sqrt{\log n})}$ time bound obtained from Williams' recent result on all-pairs shortest paths [STOC'14], and answers an open question raised by several researchers studying the histogram indexing problem. 2. The first algorithm for histogram indexing for any constant alphabet size that achieves truly subquadratic preprocessing time and truly sublinear query time. 3. A truly subquadratic algorithm for integer 3SUM in the case when the given set can be partitioned into $n^{1-\delta}$ clusters each covered by an interval of length $n$, for any constant $\delta>0$. 4. An algorithm to preprocess any set of $n$ integers so that subsequently 3SUM on any given subset can be solved in $O(n^{13/7}\,\textrm{polylog}\,n)$ time. All these results are obtained by a surprising new technique, based on the Balog--Szemer\'edi--Gowers Theorem from additive combinatorics.

We study the incentives that agents have to invest in costly protection against cascading failures in networked systems. Applications include vaccination, computer security and airport security. Agents are connected through a network and can fail either intrinsically or as a result of the failure of a subset of their neighbors. We characterize the equilibrium based on an agent's failure probability and derive conditions under which equilibrium strategies are monotone in degree (i.e. in how connected an agent is on the network). We show that different kinds of applications (e.g. vaccination, malware, airport/EU security) lead to very different equilibrium patterns of investments in protection, with important welfare and risk implications. Our equilibrium concept is flexible enough to allow for comparative statics in terms of network properties and we show that it is also robust to the introduction of global externalities (e.g. price feedback, congestion)., Comment: 32 pages, 3 figures

In this note we present a framework which allows to prove an abstract existence result for evolution equations with pseudo-monotone operators. The assumptions on the spaces and the operators can be easily verified in concrete examples.

We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$-modems and study the minimum number of $k$-modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. We show that every monotone polygon with $n$ vertices can be illuminated with $\big\lceil \frac{n-2}{2k+3} \big\rceil$ $k$-modems. In addition, we exhibit examples of monotone polygons requiring at least $\lceil \frac {n-2} {2k+3}\rceil$ $k$-modems to be illuminated. For monotone orthogonal polygons with $n$ vertices we show that for $k=1$ and for even $k$, every such polygon can be illuminated with $\big\lceil \frac{n-2}{2k+4} \big\rceil$ $k$-modems, while for odd $k\geq3$, $\big\lceil \frac{n-2}{2k+6} \big\rceil$ $k$-modems are always sufficient. Further, by presenting according examples of monotone orthogonal polygons, we show that both bounds are tight., Comment: full version, 21 pages, 14 figures

The purpose of this paper is to study some properties of solutions to one dimensional as well as multidimensional stochastic differential equations (SDEs in short) with super-linear growth conditions on the coefficients. Taking inspiration from \cite{BEHP, KBahlali, Bahlali}, we introduce a new {\it{local condition}} which ensures the pathwise uniqueness, as well as the non-contact property. We moreover show that the solution produces a stochastic flow of continuous maps and satisfies a large deviations principle of Freidlin-Wentzell type. Our conditions on the coefficients go beyond the existing ones in the literature. For instance, the coefficients are not assumed uniformly continuous and therefore can not satisfy the classical Osgood condition. The drift coefficient could not be locally monotone and the diffusion is neither locally Lipschitz nor uniformly elliptic. Our conditions on the coefficients are, in some sense, near the best possible. Our results are sharp and mainly based on Gronwall lemma and the localization of the time parameter in concatenated intervals, Comment: in Stochastics An International Journal of Probability and Stochastic Processes, 2015

The altitude of a graph $G$, denoted $f(G)$, is the largest integer $k$ such that under each ordering of $E(G)$, there exists a path of length $k$ which traverses edges in increasing order. In 1971, Chv\'atal and Koml\'os asked for $f(K_n)$, where $K_n$ is the complete graph on $n$ vertices. In 1973, Graham and Kleitman proved that $f(K_n) \ge \sqrt{n - 3/4} - 1/2$ and in 1984, Calderbank, Chung, and Sturtevant proved that $f(K_n) \le (\frac{1}{2} + o(1))n$. We show that $f(K_n) \ge (\frac{1}{20} - o(1))(n/\lg n)^{2/3}$., Comment: 11 pages

A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a circuit counts the number of monomials of f evaluated to 1 by a given 0-1 input vector (with multiplicities given by their coefficients). A circuit decides $f$ if it has the same 0-1 roots as f. We first show that some multilinear polynomials can be exponentially easier to count than to compute them, and can be exponentially easier to decide than to count them. Then we give general lower bounds on the size of counting circuits., Comment: 20 pages

Operator splitting schemes have been successfully used in computational sciences to reduce complex problems into a series of simpler subproblems. Since 1950s, these schemes have been widely used to solve problems in PDE and control. Recently, large-scale optimization problems in machine learning, signal processing, and imaging have created a resurgence of interest in operator-splitting based algorithms because they often have simple descriptions, are easy to code, and have (nearly) state-of-the-art performance for large-scale optimization problems. Although operator splitting techniques were introduced over 60 years ago, their importance has significantly increased in the past decade. This paper introduces a new operator-splitting scheme for solving a variety of problems that are reduced to a monotone inclusion of three operators, one of which is cocoercive. Our scheme is very simple, and it does not reduce to any existing splitting schemes. Our scheme recovers the existing forward-backward, Douglas-Rachford, and forward-Douglas-Rachford splitting schemes as special cases. Our new splitting scheme leads to a set of new and simple algorithms for a variety of other problems, including the 3-set split feasibility problems, 3-objective minimization problems, and doubly and multiple regularization problems, as well as the simplest extension of the classic ADMM from 2 to 3 blocks of variables. In addition to the basic scheme, we introduce several modifications and enhancements that can improve the convergence rate in practice, including an acceleration that achieves the optimal rate of convergence for strongly monotone inclusions. Finally, we evaluate the algorithm on several applications., Comment: 52 pages, 5 figures

In this article I study the dynamics of open quantum system in Markovian environment. I give necessary and sufficient conditions for such dynamics to be majorization monotone, which are those dynamics always mixing the states., Comment: 5 pages

We propose a criterion for the existence of monotone wavefronts in non-monotone and non-local monostable diffusive equations of the Mackey-Glass type. This extends recent results by Gomez et al proved for the particular case of equations with local delayed reaction. In addition, we demonstrate the uniqueness (up to a translation) of obtained monotone wavefront within the class of all monotone wavefronts (such a kind of conditional uniqueness was recently established for the non-local KPP-Fisher equation by Fang and Zhao). Moreover, we show that if delayed reaction is local then this uniqueness actually holds within the class of all wavefronts and therefore the minimal fronts under consideration (either pulled or pushed) should be monotone. Similarly to the case of the KPP-Fisher equations, our approach is based on the construction of an appropriate fundamental solution for associated boundary value problem for linear integral-differential equation., Comment: 23 pages, submitted

A path v 1 , v 2 , … , v m in a graph G is degree-monotone if d e g ( v 1 ) ≤ d e g ( v 2 ) ≤ ⋯ ≤ d e g ( v m ) where d e g ( v i ) is the degree of v i in G . Longest degree-monotone paths have been studied in several recent papers. Here we consider the Ramsey type problem for degree monotone paths. Denote by M k ( m ) the minimum number M such that for all n ≥ M , in any k -edge coloring of K n there is some 1 ≤ j ≤ k such that the graph formed by the edges colored j has a degree-monotone path of order m . We prove several nontrivial upper and lower bounds for M k ( m ) .

Measuring association, or the lack of it, between variables plays an important role in a variety of research areas, including education,which is of our primary interest in this paper. Given, for example, student marks on several study subjects, we may for a number of reasons be interested in measuring the lack of comonotonicity (LOC) between the marks, which rarely follow monotone, let alone linear, patterns. For this purpose, in this paperwe explore a novel approach based on a LOCindex,which is related to, yet substantially different from, Eckhard Liebscher’s recently suggested coefficient of monotonically increasing dependence. To illustrate the new technique,we analyze a data-set of student marks on mathematics, reading and spelling.

We develop a "metrically selfdual" variational calculus for $c$-monotone vector fields between general manifolds $X$ and $Y$, where $c$ is a coupling on $X\times Y$. Remarkably, many of the key properties of classical monotone operators known to hold in a linear context, extend to this non-linear setting. This includes an integral representation of $c$-monotone vector fields in terms of $c$-convex selfdual Lagrangians, their characterization as a partial $c$-gradients of antisymmetric Hamiltonians, as well as the property that these vector fields are generically single-valued. We also use a symmetric Monge-Kantorovich transport to associate to any measurable map its closest possible $c$-monotone "rearrangement". We also explore how this metrically selfdual representation can lead to a global variational approach to the problem of inverting $c$-monotone maps, an approach that has proved efficient for resolving non-linear equations and evolutions driven by monotone vector fields in a Hilbertian setting., Comment: 27 pages, Updated version - if any - can be downloaded at http://www.birs.ca/~nassif/

The classical correlation inequality of Harris asserts that any two monotone increasing families on the discrete cube are nonnegatively correlated. In 1996, Talagrand established a lower bound on the correlation in terms of how much the two families depend simultaneously on the same coordinates. Talagrand's method and results inspired a number of important works in combinatorics and probability theory. In this paper we present stronger correlation lower bounds that hold when the increasing families satisfy natural regularity or symmetry conditions. In addition, we present several new classes of examples for which Talagrand's bound is tight. A central tool in the paper is a simple lemma asserting that for monotone events noise decreases correlation. This lemma gives also a very simple derivation of the classical FKG inequality for product measures, and leads to a simplification of part of Talagrand's proof., Comment: 22 pages

We study the expressive power of positive neural networks. The model uses positive connection weights and multiple input neurons. Different behaviors can be expressed by varying the connection weights. We show that in discrete time and in the absence of noise, the class of positive neural networks captures the so-called monotone-regular behaviors, which are based on regular languages. A finer picture emerges if one takes into account the delay by which a monotone-regular behavior is implemented. Each monotone-regular behavior can be implemented by a positive neural network with a delay of one time unit. Some monotone-regular behaviors can be implemented with zero delay. And, interestingly, some simple monotone-regular behaviors cannot be implemented with zero delay.

We consider the problem of testing multivariate normality when the data consists of a random sample of two-step monotone incomplete observations. We define for such data a generalization of Mardia's statistic for measuring kurtosis, derive the asymptotic non-null distribution of the statistic under certain regularity conditions and against a broad class of alternatives, and give an application to a well-known data set on cholesterol measurements., Comment: 20 pages

This paper is concerned with the traveling wave solutions of a reaction-diffusion equation with state-dependent delay. When the birth function is monotone, the existence and nonexistence of monotone traveling wave solutions are established. When the birth function is not monotone, the minimal wave speed of nontrivial traveling wave solutions is obtained. The results are proved by the construction of upper and lower solutions and application of the fixed point theorem.

We generalise Milnor-Thurston's kneading theory to the setting of piecewise continuous and monotone interval maps with weights. We define a weighted kneading determinant ${\cal D}(t)$ and establish combinatorially two kneading identities, one with the cutting invariant and one with the dynamical zeta function. For the pressure $\log \rho_1$ of the weighted system, playing the role of entropy, we prove that ${\cal D}(t)$ is non-zero when $|t, Comment: 25 pages, 3 figures

We prove that the Lipschitz-free space over a separable ultrametric space has a monotone Schauder basis and is isomorphic to $\ell_1$. This extends results of A. Dalet using an alternative approach., Comment: The only change in the latest version is the second author's grant information. Question 1 from the previous version has been answered - see Remark 15 for the solution. Preprint was accepted in Mediterr. J. Math

We study multivalued stochastic differential equations (MSDEs) with maximal monotone operators driven by semimartingales with jumps. We discuss in detail some methods of approximation of solutions of MSDEs based on discretization of processes and Yosida approximation of the monotone operator. We also study the general problem of stability of solutions of MSDEs with respect to the convergence of driving semimartingales.