# Mathematics (math)

• This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest $\mathbf{x}^{\natural}\in\mathbb{R}^{n}$ from $m$ quadratic equations/samples $y_{i}=(\mathbf{a}_{i}^{\top}\mathbf{x}^{\natural})^{2}$, $1\leq i\leq m$. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficiency of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descent --- when randomly initialized --- yields an $\epsilon$-accurate solution in $O\big(\log n+\log(1/\epsilon)\big)$ iterations given nearly minimal samples, thus achieving near-optimal computational and sample complexities at once. This provides the first global convergence guarantee concerning vanilla gradient descent for phase retrieval, without the need of (i) carefully-designed initialization, (ii) sample splitting, or (iii) sophisticated saddle-point escaping schemes. All of these are achieved by exploiting the statistical models in analyzing optimization algorithms, via a leave-one-out approach that enables the decoupling of certain statistical dependency between the gradient descent iterates and the data.
• Mar 22 2018 math.CO arXiv:1803.07694v1
Consider the following two ways to colour the vertices of a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has "defect" $d$ if each monochromatic component has maximum degree at most $d$. A colouring has "clustering" $c$ if each monochromatic component has at most $c$ vertices. This paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, graphs with given circumference, graphs excluding a fixed graph as an immersion, graphs with given thickness, graphs with given stack- or queue-number, graphs excluding $K_t$ as a minor, graphs excluding $K_{s,t}$ as a minor, and graphs excluding an arbitrary graph $H$ as a minor. Several open problems are discussed.
• This paper considers the word problem for free inverse monoids of finite rank from a language theory perspective. It is shown that no free inverse monoid has context-free word problem; that the word problem of the free inverse monoid of rank $1$ is both $2$-context-free (an intersection of two context-free languages) and ET0L; that the co-word problem of the free inverse monoid of rank $1$ is context-free; and that the word problem of a free inverse monoid of rank greater than $1$ is not poly-context-free.
• We study the Wasserstein metric $W_p$, a notion of distance between two probability distributions, from the perspective of Fourier Analysis and discuss applications. In particular, we bound the Earth Mover Distance $W_1$ between the distribution of quadratic residues in a finite field $\mathbb{F}_p$ and uniform distribution by $\lesssim p^{-1/2}$ (the Polya-Vinogradov inequality implies $\lesssim p^{-1/2} \log{p}$). We also show for continuous $f:\mathbb{T} \rightarrow \mathbb{R}_{}$ with mean value 0 $$(\mboxnumber of roots of~f) ⋅\left( \sum_k=1^∞ \frac |\widehatf(k)|^2k^2\right)^\frac12 ≳\frac\|f\|^2_L^1(\mathbbT)\|f\|_L^∞(\mathbbT).$$ Moreover, we show that for a Laplacian eigenfunction $-\Delta_g \phi_{\lambda} = \lambda \phi_{\lambda}$ on a compact Riemannian manifold $W_p\left(\max\left\{\phi_{\lambda}, 0\right\}dx, \max\left\{-\phi_{\lambda}, 0\right\} dx\right) \lesssim_p \sqrt{\log{\lambda}/\lambda} \|\phi_{\lambda}\|_{L^1}^{1/p}$ which is at most a factor $\sqrt{\log{\lambda}}$ away from sharp. Several other problems are discussed.
• We interpret part of the experimental results of Shwartz-Ziv and Tishby [2017]. Inspired by these results, we established a conjecture of the dynamics of the machinary of deep neural network. This conjecture can be used to explain the counterpart result by Saxe et al. [2018].
• In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate of the learning process under diminishing step-sizes. This work focuses on the constant step-size case. In this case, convergence is guaranteed to a small neighborhood of the optimizer albeit at a linear rate. The analysis establishes analytically that random reshuffling outperforms uniform sampling by showing explicitly that iterates approach a smaller neighborhood of size $O(\mu^2)$ around the minimizer rather than $O(\mu)$. Furthermore, we derive an analytical expression for the steady-state mean-square-error performance of the algorithm, which helps clarify in greater detail the differences between sampling with and without replacement. We also explain the periodic behavior that is observed in random reshuffling implementations.
• Applications in machine learning, optimization, and control require the sequential selection of a few system elements, such as sensors, data, or actuators, to optimize the system performance across multiple time steps. However, in failure-prone and adversarial environments, sensors get attacked, data get deleted, and actuators fail. Thence, traditional sequential design paradigms become insufficient and, in contrast, resilient sequential designs that adapt against system-wide attacks, deletions, or failures become important. In general, resilient sequential design problems are computationally hard. Also, even though they often involve objective functions that are monotone and (possibly) submodular, no scalable approximation algorithms are known for their solution. In this paper, we provide the first scalable algorithm, that achieves the following characteristics: system-wide resiliency, i.e., the algorithm is valid for any number of denial-of-service attacks, deletions, or failures; adaptiveness, i.e., at each time step, the algorithm selects system elements based on the history of inflicted attacks, deletions, or failures; and provable approximation performance, i.e., the algorithm guarantees for monotone objective functions a solution close to the optimal. We quantify the algorithm's approximation performance using a notion of curvature for monotone (not necessarily submodular) set functions. Finally, we support our theoretical analyses with simulated experiments, by considering a control-aware sensor scheduling scenario, namely, sensing-constrained robot navigation.
• Mar 22 2018 cs.IT math.IT arXiv:1803.07937v1
The existence of a unique Augustin mean is established for any positive order and probability mass function on the input set. The Augustin mean is shown to be the unique fixed point of an operator defined in terms of the order and the input distribution. The Augustin information is shown to be continuously differentiable in the order. For any channel and any convex constraint set with finite Augustin capacity, the existence of a unique Augustin center and associated van Erven-Harremoes bound are established.The Augustin-Legendre (A-L) information, capacity, center, and radius are introduced and the latter three is proved to be equal to the corresponding Renyi-Gallager quantities. The equality of the A-L capacity to the A-L radius for arbitrary channels and the existence of a unique A-L center for channels with finite A-L capacity are established. For all interior points of the feasible set of cost constraints, the cost constrained Augustin capacity and center are expressed in terms the A-L capacity and center. Certain shift invariant families of probability measures and certain Gaussian channels are analyzed as examples.
• Given a complex manifold endowed with a $\mathbb{C}^\times$-action and a DQ-algebra equipped with a compatible holomorphic Frobenius action (F-action), we prove that if the $\mathbb{C}^\times$-action is free and proper, then the category of F-equivariant DQ-modules is equivalent to the category of modules over the sheaf of invariant sections of the DQ-algebra. As an application, we deduce the codimension three conjecture for formal microdifferential modules from the one for DQ-modules on a symplectic manifold.
• We study the stabilization issue of the Benjamin-Bona-Mahony (BBM) equation on a finite star-shaped network with a damping term acting on the central node. In a first time, we prove the well-posedness of this system. Then thanks to the frequency domain method, we get the asymptotic stabilization result.
• In this paper we prove an $n$th root test for series as well as a Cauchy-Hadamard type formula and Abel's' theorem for power series on universally complete Archimedean complex vector lattices. These results are aimed at developing an alternative approach to the classical theory of complex series and power series using the topology of order convergence.
• Mar 22 2018 math.OC arXiv:1803.07872v1
We study a differential game where two players separately control their own dynamics, pay a running cost, and moreover pay an exit cost (quitting the game) when they leave a fixed domain. In particular, each player has its own domain and the exit cost consists of three different exit costs, depending whether either the first player only leaves its domain, or the second player only leaves its domain, or they both simultaneously leave their own domain. We prove that, under suitable hypotheses, the lower and upper value are continuous and are, respectively, the unique viscosity solution of a suitable Dirichlet problem for a Hamilton-Jacobi-Isaacs equation. The continuity of the values relies on the existence of suitable non-anticipative strategies respecting the domain-constraint. This problem is also treated in this work.
• Mar 22 2018 math.CV arXiv:1803.07862v1
We generalize the notion of tame discrete sets introduced by Rosay and Rudin from complex-Euclidean space to arbitrary complex manifolds and establish their basic properties. We show that complex-linear algebraic groups different from the complex line or the punctured complex line contain tame discrete sets.
• In this paper, we describe a new Niederreiter cryptosystem based on quasi-cyclic $\frac{m-1}{m}$ codes that is quantum-secure. This new cryptosystem has good transmission rate compared to the one using binary Goppa codes and uses smaller keys.
• In this paper, we study the problem of distributed multi-agent optimization over a network, where each agent possesses a local cost function that is smooth and strongly convex. The global objective is to find a common solution that minimizes the average of all cost functions. Assuming agents only have access to unbiased estimates of the gradients of their local cost functions, we consider a distributed stochastic gradient tracking method. We show that, in expectation, the iterates generated by each agent are attracted to a neighborhood of the optimal solution, where they accumulate exponentially fast (under a constant step size choice). More importantly, the limiting (expected) error bounds on the distance of the iterates from the optimal solution decrease with the network size, which is a comparable performance to a centralized stochastic gradient algorithm. Numerical examples further demonstrate the effectiveness of the method.
• We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known "Frank-Wolfe type" theorems imply that exactly one of two cases can occur: either the optimal value is attained on every instance, or it is strongly NP-hard to distinguish attainment from non-attainment. We also show that testing for some well-known sufficient conditions for attainment of the optimal value, such as coercivity of the objective function and closedness and boundedness of the feasible set, is strongly NP-hard. As a byproduct, our proofs imply that testing the Archimedean property of a quadratic module is strongly NP-hard, a property that is of independent interest to the convergence of the Lasserre hierarchy. Finally, we give semidefinite programming (SDP)-based sufficient conditions for attainment of the optimal value, in particular a new characterization of coercive polynomials that lends itself to an SDP hierarchy.
• Mar 22 2018 math.ST stat.TH arXiv:1803.07645v1
Smoothing splines can be thought of as the posterior mean of a Gaussian process regression in a certain limit. By constructing a reproducing kernel Hilbert space with an appropriate inner product, the Bayesian form of the V-spline is derived when the penalty term is a fixed constant instead of a function. An extension to the usual generalized cross-validation formula is utilized to find the optimal V-spline parameters.
• We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.
• We uncover a fairly general principle in online learning: If regret can be (approximately) expressed as a function of certain "sufficient statistics" for the data sequence, then there exists a special Burkholder function that 1) can be used algorithmically to achieve the regret bound and 2) only depends on these sufficient statistics, not the entire data sequence, so that the online strategy is only required to keep the sufficient statistics in memory. This characterization is achieved by bringing the full power of the Burkholder Method --- originally developed for certifying probabilistic martingale inequalities --- to bear on the online learning setting. To demonstrate the scope and effectiveness of the Burkholder method, we develop a novel online strategy for matrix prediction that attains a regret bound corresponding to the variance term in matrix concentration inequalities. We also present a linear-time/space prediction strategy for parameter free supervised learning with linear classes and general smooth norms.
• Mar 22 2018 math.AG arXiv:1803.07596v1
We define the notion of Mumford divisors, argue that they are the natural divisors to study on reduced but non-normal varieties and prove a structure theorem for the Mumford class group.
• In this paper, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider a new distributed gradient-based method where each node maintains two estimates, namely, an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the decision variable is pushed to the neighbors, while the information about the gradients is pulled from the neighbors (hence giving the name "push-pull gradient method"). The method unifies the algorithms with different types of distributed architecture, including decentralized (peer-to-peer), centralized (master-slave), and semi-centralized (leader-follower) architecture. We show that the algorithm converges linearly for strongly convex and smooth objective functions over a directed static network. In our numerical test, the algorithm performs well even for time-varying directed networks.
• The PWP map was introduced by the second author as a tool for ranking nodes in networks. In this work we extend this technique so that it can be used to rank links as well. Applying the Girvan-Newman algorithm a ranking method on links induces a deconstruction method for networks, therefore we obtain new methods for finding clustering and core-periphery structures on networks.
• We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Informally, their delocalization result in the contrapositive states that for any $\varepsilon \in (0,1)$ and positive integer $k,$ if a $(d+1)-$regular graph has an eigenvector which supports $\varepsilon$ fraction of the $\ell_2^2$ mass on a subset of $k$ vertices, then the graph must have a cycle of size $\tilde{O}(\log_{d}(k)/\varepsilon^2)$, suppressing logarithmic terms in $1/\varepsilon$. In this paper, we improve the upper bound to $\tilde{O}(\log_{d}(k)/\varepsilon)$ and present a construction showing a lower bound of $\Omega(\log_d(k)/\varepsilon)$. Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.
• We study locally compact groups having all subgroups minimal. We call such groups hereditarily minimal. In 1972 Prodanov proved that the infinite hereditarily minimal compact abelian groups are precisely the groups $\mathbb Z_p$ of $p$-adic integers. We extend Prodanov's theorem to the non-abelian case at several levels. For infinite hypercentral (in particular, nilpotent) locally compact groups we show that the hereditarily minimal ones remain the same as in the abelian case. On the other hand, we classify completely the locally compact solvable hereditarily minimal groups, showing that in particular they are always compact and metabelian. The proofs involve the (hereditarily) locally minimal groups, introduced similarly. In particular, we prove a conjecture by He, Xiao and the first two authors, showing that the group $\mathbb Q_p\rtimes \mathbb Q_p^*$ is hereditarily locally minimal, where $\mathbb Q_p^*$ is the multiplicative group of non-zero $p$-adic numbers acting on the first component by multiplication. Furthermore, it turns out that the locally compact solvable hereditarily minimal groups are closely related to this group.
• Mar 22 2018 math.DS arXiv:1803.08032v1
Let $\{N_t\}$ be a holomorphic family of degree $d\ge 3$ Newton maps. By studying the related Berkovich dynamics, we obtain an estimate of the weak limit of the maximal measures of $N_t$. Moreover, we give a complete description of the rescaling limits for $\{N_t\}$.
• The goal of this paper is to study a distributed version of the gradient temporal-difference (GTD) learning algorithm for multi-agent Markov decision processes (MDPs). The temporal difference (TD) learning is a reinforcement learning (RL) algorithm which learns an infinite horizon discounted cost function (or value function) for a given fixed policy without the model knowledge. In the distributed RL case each agent receives local reward through a local processing. Information exchange over sparse communication network allows the agents to learn the global value function corresponding to a global reward, which is a sum of local rewards. In this paper, the problem is converted into a constrained convex optimization problem with a consensus constraint. Then, we propose a primal-dual distributed GTD algorithm and prove that it almost surely converges to a set of stationary points of the optimization problem.
• We use recent results of Rolen, Zwegers, and the first author to study characters of irreducible (highest weight) modules for the vertex operator algebra $L_{\frak{sl}_\ell}(-\Lambda_0)$. We establish asymptotic behaviors of characters for the (ordinary) irreducible $L_{\frak{sl}_\ell}(-\Lambda_0)$-modules. As a consequence we prove that their quantum dimensions are one, as predicted by representation theory. We also establish a full asymptotic expansion of irreducible characters for $\frak{sl}_3$. Finally, we determine a decomposition formula for the full characters in terms of unary theta and false theta functions which allows us to study their modular properties.
• We define some signature invariants for a class of knotted trivalent graphs using branched covers. We relate them to classical signatures of knots and links. Finally, we explain how to compute these invariants through the example of Kinoshita's knotted theta graph.
• We give a brief re-exposition of the theory due to Pauli and Sinclair of ramification polygons of Eisenstein polynomials over p-adic fields, their associated residual polynomials and an algorithm to produce all extensions for a given ramification polygon. We supplement this with an algorithm to produce all ramification polygons of a given degree, and hence we can produce all totally ramified extensions of a given degree.
• We study a system of nonlinear partial differential equations describing the unsteady motions of incompressible chemically reacting non-Newtonian fluids. The system under consideration consists of the generalized Navier-Stokes equations with a power-law type stress-strain relation, where the power-law index depends on the concentration of a chemical, coupled to a convection-diffusion equation for the concentration. This system of equations arises in the rheology of the synovial fluid found in the cavities of synovial joints. We prove the existence of global weak solutions of the non-stationary model by using the Galerkin method combined with generalized monotone operator theory and parabolic De Giorgi-Nash-Moser theory. As the governing equations involve a nonlinearity with a variable power-law index, our proofs exploit the framework of generalized Sobolev spaces with variable integrability exponent.
• We give a notion of quantum automorphism group of graph C*-algebras without sink at critical inverse temperature. This is defined to be the universal object of a category of CQG's having a linear action in the sense of [11] and preserving the KMS state at critical inverse temperature. We show that this category for a certain KMS state at critical inverse temperature coincides with the category introduced in [11] for a class of graphs. We also introduce an orthogonal filtration on Cuntz algebra with respect to the unique KMS state and show that the category of CQG's preserving the orthogonal filtration coincides with the category introduced in this paper.
• In 2008, Kauffman and Lomonaco introduce the concepts of a knot mosaic and the mosaic number of a knot or link, the smallest integer $n$ such that a knot or link can be represented on an $n$-mosaic. In arXiv:1702.06462, the authors explore space-efficient knot mosaics and the tile number of a knot or link, the smallest number of non-blank tiles necessary to depict the knot or link on a mosaic. They determine bounds for the tile number in terms of the mosaic number. In this paper, we focus specifically on prime knots with mosaic number 6. We determine a complete list of these knots, provide a minimal, space-efficient knot mosaic for each of them, and determine the tile number (or minimal mosaic tile number) of each of them.
• Let $k({\bf x})=k(x_1,\ldots ,x_n)$ be the rational function field, and $k\subsetneqq L\subsetneqq k({\bf x})$ an intermediate field. Then, Hilbert's fourteenth problem asks whether the $k$-algebra $A:=L\cap k[x_1,\ldots ,x_n]$ is finitely generated. Various counterexamples to this problem were already given, but the case $[k({\bf x}):L]=2$ was open when $n=3$. In this paper, we study the problem in terms of the field-theoretic properties of $L$. We say that $L$ is minimal if the transcendence degree $r$ of $L$ over $k$ is equal to that of $A$. We show that, if $r\ge 2$ and $L$ is minimal, then there exists $\sigma \in {\mathop{\rm Aut}\nolimits}_kk(x_1,\ldots ,x_{n+1})$ for which $\sigma (L(x_{n+1}))$ is minimal and a counterexample to the problem. Our result implies the existence of interesting new counterexamples including one with $n=3$ and $[k({\bf x}):L]=2$.
• We explain a connection between the algebraic and geometric properties of groups of contact transformations, open book decompositions, and flexible Legendrian embeddings. The main result is that, if a closed contact manifold $(V, \xi)$ has a supporting open book whose pages are flexible Weinstein manifolds, then both the connected component of identity in its automorphism group and its universal cover are uniformly simple groups: for every non-trivial element $g$, every other element is a product of at most $128(\dim V + 1)$ conjugates of $g^{\pm 1}$. In particular any conjugation invariant norm on these groups is bounded.
• A source submits status updates to a network for delivery to a destination monitor. Updates follow a route through a series of network nodes. Each node is a last-come-first-served queue supporting preemption in service. We characterize the average age of information at the input and output of each node in the route induced by the updates passing through. For Poisson arrivals to a line network of preemptive memoryless servers, we show that average age accumulates through successive network nodes.
• For every fixed genus $g\geq 1$, we consider all quadruples $Q=(w_0,w_1,w_2,d)\in\mathbb{Z}^4_{>0}$ with the property that any smooth degree-$d$ curve embedded in the weighted projective plane $\mathbb{P}^2(w_0,w_1,w_2)$ has genus $g$. We show there are infinitely many quadruples $Q$ satisfying this condition. For every such $Q$, we consider $Z_Q\subseteq M_g$ the locus in the moduli space of all smooth degree-$d$ curves embedded in $\mathbb{P}^2(w_0,w_1,w_2)$. We show that, as $Q$ varies over all these quadruples, there are only finitely many different loci $Z_Q\subseteq M_g$.
• In this paper we study the Dirichlet eigenvalue problem $$-\Delta_p u-\Delta_J,pu =\lambda|u|^p-2u \quad \text in \Omega,\quad u=0 \quad\text in \Omega^c=\mathbbR^N∖\Omega.$$ Here $\Delta_p u$ is the standard local $p-$Laplacian, $\Delta_{J,p}u$ is a nonlocal, $p-$homogeneous operator of order zero and $\Omega$ is a bounded domain in $\mathbb{R}^N$. We show that the first eigenvalue (that is isolated and simple) satisfies $(\lambda_1)^{1/p}\to \Lambda$ as $p\to\infty$ where $\Lambda$ can be characterized in terms of the geometry of $\Omega$. We also find that the eigenfunctions converge, $u_\infty=\lim_{p\to\infty} u_p$, and find the limit problem that is satisfied in the limit.
• This paper considers a class of real-time decision making problems to minimize the expected value of a function that depends on a random variable $\xi$ under an unknown distribution $\mathbb{P}$. In this process, samples of $\xi$ are collected sequentially in real time, and the decisions are made, using the real-time data, to guarantee out-of-sample performance. We approach this problem in a distributionally robust optimization framework and propose a novel Online Data Assimilation Algorithm for this purpose. This algorithm guarantees the out-of-sample performance in high probability, and gradually improves the quality of the data-driven decisions by incorporating the streaming data. We show that the Online Data Assimilation Algorithm guarantees convergence under the streaming data, and a criteria for termination of the algorithm after certain number of data has been collected.
• Let $\Omega\subset\mathbb R^{n+1}$ be an open set with $n$-AD-regular boundary. In this paper we prove that if the harmonic measure for $\Omega$ satisfies the so-called weak-$A_\infty$ condition, then $\Omega$ satisfies a suitable connectivity condition, namely the weak local John condition. This yields the first geometric characterization of the weak-$A_\infty$ condition of harmonic measure, which is important because its connection with the Dirichlet problem for the Laplace equation.
• We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. Normal form algorithms provide an algebraic approach to solve this problem. We use new characterizations of normal forms and describe accurate and efficient constructions that allow us to compute the algebra structure of R/I, and hence the solutions of I. We show how the resulting algorithms give accurate results in double precision arithmetic and compare with normal form algorithms using Groebner bases and homotopy solvers.
• Recent progress has been made with Adaptive Multiple Importance Sampling (AMIS) methods that show improvement in effective sample size. However, consistency for the AMIS estimator has only been established in very restricted cases. Furthermore, the high computational complexity of the re-weighting in AMIS (called balance heuristic) makes it expensive for applications involving diffusion processes. In this work we consider sequential and adaptive importance sampling that is particularly suitable for diffusion processes. We propose a new discarding-re-weighting scheme that is of lower computational complexity, and we prove that the resulting AMIS is consistent. Using numerical experiments, we demonstrate that discarding-re-weighting performs very similar to the balance heuristic, but at a fraction of the computational cost.
• A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai $k$-coloring is a Gallai coloring that uses $k$ colors. Given an integer $k\ge1$ and graphs $H_1, H_2, \ldots, H_k$, the Gallai-Ramsey number $GR(H_1, H_2, \ldots, H_k)$ is the least integer $n$ such that every Gallai $k$-coloring of the complete graph $K_n$ contains a monochromatic copy of $H_i$ in color $i$ for some $i \in \{1,2, \ldots, k\}$. When $H = H_1 = \cdots = H_k$, we simply write $GR_k(H)$. We study Gallai-Ramsey numbers of even cycles and paths. For all $n\ge3$ and $k\ge1$, let $G_i=P_{2i+3}$ be a path on $2i+3$ vertices for all $i\in\{0,1, \ldots, n-2\}$ and $G_{n-1}\in\{C_{2n}, P_{2n+1}\}$. Let $i_j\in\{0,1,\ldots, n-1 \}$ for all $j\in\{1,2, \ldots, k\}$ with $i_1\ge i_2\ge\cdots\ge i_k$. The first author recently conjectured that $GR(G_{i_1}, G_{i_2}, \ldots, G_{i_k}) = 3+\min\{i_1,n^*-2\}+\sum_{j=1}^k i_j$, where $n^* =n$ when $G_{i_1}\ne P_{2n+1}$ and $n^* =n+1$ when $G_{i_1}= P_{2n+1}$. The truth of this conjecture implies that $GR_k(C_{2n})=GR_k(P_{2n})=(n-1)k+n+1$ for all $n\ge3$ and $k\ge1$, and $GR_k(P_{2n+1})=(n-1)k+n+2$ for all $n\ge1$ and $k\ge1$. In this paper, we prove that the aforementioned conjecture holds for $n\in\{3,4\}$ and all $k\ge1$. Our proof relies only on Gallai's result and the classical Ramsey numbers $R(H_1, H_2)$, where $H_1, H_2\in\{C_8, C_6, P_7, P_5, P_3\}$. We believe the recoloring method we developed here will be very useful for solving subsequent cases, and perhaps the conjecture.
• The Kuramoto--Sakaguchi model is a modification of the well-known Kuramoto model that adds a phase-lag paramater, or "frustration" to a network of phase-coupled oscillators. The Kuramoto model is a flow of gradient type, but adding a phase-lag breaks the gradient structure, significantly complicating the analysis of the model. We present several results determining the stability of phase-locked configurations: the first of these gives a sufficient condition for stability, and the second a sufficient condition for instability. (In fact, the instability criterion gives a count, modulo 2, of the dimension of the unstable manifold to a fixed point and having an odd count is a sufficient condition for instability of the fixed point.) We also present numerical results for both small and large collections of Kuramoto--Sakaguchi oscillators.
• We study transportation networks controlled by dynamical feedback tolls. We consider a multiscale model in which the dynamics of the traffic flows are intertwined with those of the drivers' route choices. The latter are influenced by the congestion status of the whole network as well as decentralized congestion-dependent tolls. Our main result shows that positive increasing decentralized congestion-dependent tolls allow the system planner to globally stabilise the transportation network around the Wardrop equilibrium. Moreover, using the decentralized marginal costs tolls the stability of the transportation network is around the social optimum traffic assignment.This particularly remarkable as such feedback tolls do not require any global information about the network structure or state and can be computed in a fully local way. We also extend this stability analysis to a constant decentralised feedback tolls and compare their performance both asymptotic and during the transient through numerical simulations.
• In The factorization of the Giry monad (arXiv:1707.00488v2) the author considers two $\sigma$-algebras on convex spaces of functions to the unit interval. One of them is generated by the Boolean subobjects and the other is the $\sigma$-algebra induced by the evaluation maps. The author asserts that, under the assumptions given in the paper, the two $\sigma$-algebras coincide. We give examples contradicting this statement.
• In this article, left g, h-derivation and Jordan left g, h-derivation on algebras are introduced. It is shown that there is no Jordan left g, h-derivation over $\mathcal{M}_n(C)$ and $\mathbb{H}_{\mathbb{R}}$, for g not equal to h. Examples are given which show that every Jordan left $\{g, h\}$-derivation over $\mathcal{T}_n(C)$, $\mathcal{M}_n(C)$ and $\mathbb{H}_{\mathbb{R}}$ are not left $\{g, h\}$-derivations. Moreover, we characterize left $\{g, h\}$-derivation and Jordan left $\{g, h\}$-derivation over $\mathcal{T}_n(C)$, $\mathcal{M}_n(C)$ and $\mathbb{H}_{\mathbb{R}}$ respectively. Also, we prove the result of Jordan left $\{g, h\}$-derivation to be a left $\{g, h\}$-derivation over tensor products of algebras as well as for algebra of polynomials.
• We confirm Demailly's conjecture on the convergence of higher Lelong numbers under the canonical approximation of a plurisubharmonic function in the case when the function is toric and in the Cegrell class. As applications to convex geometry, we give a unified analytic proof of the Alexandrov-Fenchel inequalities for mixed Monge-Ampère masses, mixed covolumes and mixed multiplicities.
• In this paper, we deal with the following nonlinear Schrödinger equation $$-\epsilon^2∆u+V(x)u=f(u),\ u∈H^1(\mathbb R^2),$$ where $f(t)$ has critical growth of Trudinger-Moser type. By using the variational techniques, we construct a positive solution $u_\epsilon$ concentrating around the saddle points of the potential $V(x)$ as $\epsilon\rightarrow 0$. Our results complete the analysis made in \citeMR2900480 and \citeMR3426106, where the Schrödinger equation was studied in $\mathbb R^N$, $N\geq 3$ for sub-critical and critical case respectively in the sense of Sobolev embedding. Moreover, we relax the monotonicity condition on the nonlinear term $f(t)/t$ together with a compactness assumption on the potential $V(x)$, imposed in \citeMR3503193.
• In this article, we show that every Jordan g, h-derivation over T_n(C) is a g, h-derivation under an assumption, where C is a commutative ring with unity 1 not equal to 0. We give an example of a Jordan g, h-derivation over T_n(C) which is not a g, h-derivation. Also, we study Jordan g, h-derivation over M_n(C).
• Let C be a commutative ring with unity. In this article, we show that every Jordan derivation over an upper triangular matrix algebra T_n(C) is an inner derivation. Further, we extend the result for Jordan derivation on full matrix algebra M_n(C).

Danial Dervovic Mar 01 2018 12:08 UTC

Hello again Māris, many thanks for your patience. Your comments and questions have given me much food for thought, and scope for an amended version of the paper -- please see my responses below.

Please if any of the authors of [AST17 [arXiv:1712.01609](https://arxiv.org/abs/1712.01609)] have any fu

...(continued)
Danial Dervovic Feb 05 2018 15:03 UTC

Thank you Māris for the extremely well thought-out and articulated points here.

I think this very clearly highlights the need to think explicitly about the precompute time if using the lifting to directly simulate the quantum walk, amongst other things.

I wish to give a well-considered respons

...(continued)
Māris Ozols Feb 01 2018 17:53 UTC

This paper considers the problem of using "lifted" Markov chains to simulate the mixing of coined quantum walks. The Markov chain has to approximately (in the total variational distance) sample from the distribution obtained by running the quantum walk for a randomly chosen time $t \in [0,T]$ follow

...(continued)
Marco Piani Jan 28 2018 11:21 UTC

Hi Mizanur,

thanks to you for taking into account my comment. I am not sure of the jargon and nomenclature in mathematics; are/were the maps that are completely positive and also completely co-positive known as PPT maps? What I was pointing out is that in the quantum information community the nam

...(continued)
Mizanur Rahaman Jan 27 2018 19:06 UTC

Hi Marco, thanks for pointing out the possible confusion. I will make it clear in the revised version. I think in this context what I should clearly state is that I am considering linear maps
which are completely positive and co-completely positive, that is, the map \Phi and \Phi\circleT
are compl

...(continued)
Marco Piani Jan 24 2018 03:34 UTC

Great work! One thing that might potentially confuse readers is the use of "PPT channel" to indicate that the partial action of the channel produces a PPT state. There might be some ambiguity in literature, but many call "PPT channels" those channels that act jointly on two parties, and that preserv

...(continued)
Mizanur Rahaman Jan 23 2018 23:20 UTC

Thanks for the comment. I was not aware of the "entanglement breaking index" paper.
I will include it in a revised version. I will make a remark about the other deduction as well.
Thanks.

Ludovico Lami Jan 19 2018 00:08 UTC

Very nice work, congratulations! I just want to point out that the "index of separability" had already been defined in arXiv:1411.2517, where it was called "entanglement-breaking index" and studied in some detail. The channels that have a finite index of separability had been dubbed "entanglement-sa

...(continued)
Steve Flammia Dec 18 2017 20:59 UTC

It splits into even and odd cases, actually. I was originally sloppy about the distinction between integer and polynomial division, but it's fixed now. There is a little room left in the case $d=3$ now though, but it's still proven in every other dimension.

Aram Harrow Dec 18 2017 19:30 UTC

whoa, awesome! But why do you get that $d^3-d$ must be a divisor instead of $(d^3-d)/2$?