Solidot 公告
请在发布文章时用HTML代码加上至少一条新闻来源的链接；原创性消息，可加入相关信息（如涉及公司的网址）的链接。有任何问题，邮件至：he.fang#zhiding.cn
ken：feigaobox@gmail.com
注意：收到邮件乱码的用户请修改客户端的默认字体编码，从"简体中文（GB2312）"修改为"Unicode（UTF8）"。
投 票
信息流

We consider the Graph Isomorphism problem for classes of graphs characterized by two forbidden induced subgraphs $H_1$ and $H_2$. By combining old and new results, Schweitzer settled the computational complexity of this problem restricted to $(H_1,H_2)$free graphs for all but a finite number of pairs $(H_1,H_2)$, but without explicitly giving the number of open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomialtime solvable on graph classes of bounded cliquewidth. By combining previously known results for Graph Isomorphism with known results for boundedness of cliquewidth, we reduce the number of open cases to 14. By proving a number of new results we then further reduce this number to seven. By exploiting the strong relationship between Graph Isomorphism and cliquewidth, we also prove that the class of $(\mbox{gem},P_1+2P_2)$free graphs has unbounded cliquewidth. This reduces the number of open cases for boundedness of cliquewidth for $(H_1,H_2)$free grap
收起

To every topologically transitive Cantor dynamical system $(X, \varphi)$ we associate a group $T(\varphi)$ acting faithfully by homeomorphism on the real line. It is defined as the group of homeomorphisms of the suspension flow of $(X, \varphi)$ which preserve every leaf and acts by dyadic piecewise linear homeomorphisms in the flow direction. We show that if $(X, \varphi)$ is minimal, the group $T(\varphi)$ is simple, and if $(X, \varphi)$ is a subshift the group $T(\varphi)$ is finitely generated. The proofs of these two statements are short and elementary, providing straightforward examples of finitely generated simple leftorderable groups. We show that if the system $(X, \varphi)$ is minimal, every action of the group $T(\varphi)$ on the circle has a fixed point, providing examples of so called "orderable monsters". We additionally have the following: for every subshift $(X, \varphi)$ the group $T(\varphi)$ does not have nontrivial subgroups with Kazhdan's property (T); for every
收起

Let $G$ be a nontrivial connected, edgecolored graph. An edgecut $S$ of $G$ is called a rainbow cut if no two edges in $S$ are colored with a same color. An edgecoloring of $G$ is a rainbow disconnection coloring if for every two distinct vertices $s$ and $t$ of $G$, there exists a rainbow cut $S$ in $G$ such that $s$ and $t$ belong to different components of $G\setminus S$. For a connected graph $G$, the {\it rainbow disconnection number} of $G$, denoted by $rd(G)$, is defined as the smallest number of colors such that $G$ has a rainbow disconnection coloring by using this number of colors. In this paper, we show that for a connected graph $G$, computing $rd(G)$ is NPhard. In particular, it is already NPcomplete to decide if $rd(G)=3$ for a connected cubic graph. Moreover, we prove that for a given edgecolored (with an unbounded number of colors) connected graph $G$ it is NPcomplete to decide whether $G$ is rainbow disconnected.
收起

We give a concrete presentation for the general linear group defined over a ring which is a finitely generated free $\mathbb{Z}$module or the integral Clifford group $\Gamma_n(\mathbb{Z})$ of invertible elements in the Clifford algebra with integral coefficients. We then use this presentation to prove that the elementary linear group over $\Gamma_n(\mathbb{Z})$ has a nontrivial decomposition as a free product with amalgamated subgroup the elementary linear group over $\Gamma_{n1}(\mathbb{Z})$. This allows to obtain applications to the unit group $\mathcal{U}(\mathbb{Z} G)$ of an integral group ring $\mathbb{Z} G$ of a finite group $G$. In particular, we prove that $\mathcal{U} (\mathbb{Z} G)$ is hereditary (FA), i.e. every subgroup of finite index has property (FA), or is commensurable with a nontrivial amalgamated product. In the case $\mathcal{U}(\mathbb{Z} G)$ is not hereditary (FA), we investigate subgroups of finite index in $\mathcal{U}(\mathbb{Z} G)$ that have a nontrivial
收起

We compute the Dolbeault cohomology of certain domains contained in Cousin groups defined by lattices which satisfy a strong dispersiveness condition. As a consequence we obtain a description of the Dolbeault cohomology of OeljeklausToma manifolds and in particular the fact that the Hodge decomposition holds for their cohomology.
收起

In this paper we construct families of homology spheres which bound 4manifolds with intersection forms isomorphic to $E_8$. We show that these families have arbitrary large correction terms. This result says that among homology spheres, the difference of the maximal rank of minimal sublattice of definite filling and the maximal rank of even definite filling is arbitrarily large.
收起

A new mathematical method for the dynamic analysis of nonlinear ecological systems has recently been developed by the author and was presented in a separate article. Based on this methodology, multiple new dynamic ecological system measures and indices of matrix, vector, and scalar types are systematically introduced in the present paper. These mathematical system analysis tools are quantitative ecological indicators that monitor the flow distribution and storage organization, quantify the effect and utility of one compartment directly or indirectly on another, identify the system efficiency and stress, measure the compartmental exposure to system flows, determine the residence time and compartmental activity levels, and ascertain the restoration time and resilience in the case of disturbances. Major flow and stockrelated concepts and quantities of the current static network analyses are also extended to nonlinear dynamic settings and integrated with the proposed dynamic measures and
收起

In this article, we study EinsteinWeyl structures on almost cosymplectic manifolds. First we prove that an almost cosymplectic $(\kappa,\mu)$manifold is Einstein or cosymplectic if it admits a closed EinsteinWeyl structure or two EinsteinWeyl structures. Next for a three dimensional compact almost $\alpha$cosymplectic manifold admitting closed EinsteinWeyl structures, we prove that it is Riccflat. Further, we show that an almost $\alpha$cosymplectic admitting two EinsteinWeyl structures is either Einstein or $\alpha$cosymplectic, provided that its Ricci tensor is commuting. Finally, we prove that a compact $K$cosymplectic manifold with a closed EinsteinWeyl structure or two special EinsteinWeyl structures is cosymplectic.
收起

We construct stable envelopes in equivariant elliptic cohomology of Nakajima quiver varieties. In particular, this gives an elliptic generalization of the results of arXiv:1211.1287. We apply them to the computation of the monodromy of $q$difference equations arising the enumerative Ktheory of rational curves in Nakajima varieties, including the quantum KnizhnikZamolodchikov equations.
收起

Let $H := \begin{pmatrix} 1 & {\mathbf R} & {\mathbf R} \\ 0 & 1 &{\mathbf R} \\ 0 & 0 & 1 \end{pmatrix}$ denote the Heisenberg group with the usual CarnotCarath\'eodory metric $d$. It is known (since the work of Pansu and Semmes) that the metric space $(H,d)$ cannot be embedded in a bilipchitz fashion into a Hilbert space; however, from a general theorem of Assouad, for any $0 < \varepsilon < 1$, the snowflaked metric space $(H,d^{1\varepsilon})$ embeds into an infinitedimensional Hilbert space with distortion $O( \varepsilon^{1/2} )$. This distortion bound was shown by Austin, Naor, and Tessera to be sharp for the Heisenberg group $H$. Assouad's argument allows $\ell^2$ to be replaced by ${\mathbf R}^{D(\varepsilon)}$ for some dimension $D(\varepsilon)$ dependent on $\varepsilon$. Naor and Neiman showed that $D$ could be taken independent of $\varepsilon$, at the cost of worsening the bound on the distortion to $O( \varepsilon^{1+c_D} )$, where $c_D
收起

In early study of Engel manifolds from R. Montgomery, the Cartan prolongation and the development map are central figures. However, the development map can be globally defined only if the characteristic foliation is "nice". In this paper, we introduce the Cartan prolongation of a contact 3orbifold and the development map associated to a more general Engel manifold, and we give necessary and sufficient condition for the Cartan prolongation to be a manifold. Moreover, we explain the Cartan prolongation of a 3dimensional contact \'etale Lie groupoid and the development map associated to any Engel manifold, and we proof that all Engel manifolds obtained as the Cartan prolongation of a "space" with contact structure are obtained from a contact 3orbifold.
收起

We prove that, under a well known conjecture in the finitely generated case, Galois cohomology satisfies several surprisingly strong versions of Koszul properties. We point out several unconditional results which follow from our work. We show how these enhanced versions are preserved under certain natural operations on algebras, generalising several results that were previously established only in the commutative case.
收起

Shearer's inequality bounds the sum of joint entropies of random variables in terms of the total joint entropy. We give another lower bound for the same sum in terms of the individual entropies when the variables are functions of independent random seeds. The inequality involves a constant characterizing the expansion properties of the system. Our results generalize to entropy inequalities used in recent work in invariant settings, including the edgevertex inequality for factorofIID processes, Bowen's entropy inequalities, and Bollob\'as's entropy bounds in random regular graphs. The proof method yields inequalities for other measures of randomness, including covariance. As an application, we give upper bounds for independent sets in both finite and infinite graphs.
收起

Delays are an important phenomenon arising in a wide variety of real world systems. They occur in biological models because of diffusion effects or as simplifying modeling elements. We propose here to consider delayed stochastic reaction networks. The difficulty here lies in the fact that the statespace of a delayed reaction network is infinitedimensional, which makes their analysis more involved. We demonstrate here that a particular class of stochastic timevarying delays, namely those that follow a phasetype distribution, can be exactly implemented in terms of a chemical reaction network. Hence, any delayfree network can be augmented to incorporate those delays through the addition of delayspecies and delayreactions. Hence, for this class of stochastic delays, which can be used to approximate any delay distribution arbitrarily accurately, the statespace remains finitedimensional and, therefore, standard tools developed for standard reaction network still apply. In particular
收起

We study the ergodicity of nonautonomous discrete dynamical systems with nonuniform expansion. As an application we get that any uniformly expanding finitely generated semigroup action of $C^{1+\alpha}$ local diffeomorphisms of a compact manifold is ergodic with respect to the Lebesgue measure. Moreover, we will also prove that every exact nonuniform expandable finitely generated semigroup action of conformal $C^{1+\alpha}$ local diffeomorphisms of a compact manifold is Lebesgue ergodic.
收起

This paper presents a new algorithm based on interval methods for rigorously constructing inner estimates of feasible parameter regions together with enclosures of the solution set for parameterdependent systems of nonlinear equations in low (parameter) dimensions. The proposed method allows to explicitly construct feasible parameter sets around a regular parameter value, and to rigorously enclose a particular solution curve (resp. manifold) by a union of inclusion regions, simultaneously. The method is based on the calculation of inclusion and exclusion regions for zeros of square nonlinear systems of equations. Starting from an approximate solution at a fixed set $p$ of parameters, the new method provides an algorithmic concept on how to construct a box $\mathbf{s}$ around $p$ such that for each element $s\in \mathbf{s}$ in the box the existence of a solution can be proved within certain error bounds.
收起

Here we extend the notion of targetlocal Gromov convergence of pseudoholomorphic curves to the case in which the target manifold is not compact, but rather is exhausted by compact neighborhoods. Under the assumption that the curves in question have uniformly bounded area and genus on each of the compact regions (but not necessarily global bounds), we prove a subsequence converges in an exhaustive Gromov sense.
收起

An efficient algorithm for computing eigenvectors of a matrix of integers by exact computation is proposed. The components of calculated eigenvectors are expressed as polynomials in the eigenvalue to which the eigenvector is associated, as a variable. The algorithm, in principle, utilizes the minimal annihilating polynomials for eliminating redundant calculations. Furthermore, in the actual computation, the algorithm computes candidates of eigenvectors by utilizing pseudo annihilating polynomials and verifies their correctness. The experimental results show that our algorithms have better performance compared to conventional methods.
收起

We give an efficient algorithm that, given a graph $G$ and a partition $V_1,\ldots,V_m$ of its vertex set, finds either an independent transversal (an independent set $\{v_1,\ldots,v_m\}$ in $G$ such that $v_i\in V_i$ for each $i$), or a subset $\mathcal B$ of vertex classes such that the subgraph of $G$ induced by $\bigcup\mathcal B$ has a small dominating set. A nonalgorithmic proof of this result has been known for a number of years and has been applied to solve many other problems. Thus we are able to give algorithmic versions of many of these applications, a few of which we describe explicitly here.
收起

In this paper, we present finite element approximations of a class of Generalized random fields defined over a bounded domain of R d or a smooth ddimensional Riemannian manifold (d $\ge$ 1). An explicit expression for the covariance matrix of the weights of the finite element representation of these fields is provided and an analysis of the approximation error is carried out. Finally, a method to generate simulations of these weights while limiting computational and storage costs is presented.
收起

The relationship between the sparsest cut and the maximum concurrent multiflow in graphs has been studied extensively. For general graphs with $k$ terminal pairs, the flowcut gap is $O(\log k)$, and this is tight. But when topological restrictions are placed on the flow network, the situation is far less clear. In particular, it has been conjectured that the flowcut gap in planar networks is $O(1)$, while the known bounds place the gap somewhere between $2$ (Lee and Raghavendra, 2003) and $O(\sqrt{\log k})$ (Rao, 1999). A seminal result of Okamura and Seymour (1981) shows that when all the terminals of a planar network lie on a single face, the flowcut gap is exactly $1$. This setting can be generalized by considering planar networks where the terminals lie on $\gamma>1$ faces in some fixed planar drawing. Lee and Sidiropoulos (2009) proved that the flowcut gap is bounded by a function of $\gamma$, and Chekuri, Shepherd, and Weibel (2013) showed that the gap is at most $3\gamma
收起

What Google did not make public was that an employee had accused Mr. Rubin of sexual misconduct. The woman, with whom Mr. Rubin had been having an extramarital relationship, said he coerced her into performing oral sex in a hotel room in 2013, according to two company executives with knowledge of the episode. Google investigated and concluded her claim was credible, said the people, who spoke on the condition that they not be named, citing confidentiality agreements. Mr. Rubin was notified, they said, and Mr. Page asked for his resignation. Google could have fired Mr. Rubin and paid him little to nothing on the way out. Instead, the company handed him a $90 million exit package, paid in installments of about $2 million a month for four years, said two people with knowledge of the terms. The last payment is scheduled for next month. Mr. Rubin was one of three executives that Google protected over the past decade after they were accused of sexual misconduct. In two instances, it
收起

harrymcc writes: The better AI gets at teaching itself to perform tasks in ways beyond the skills of mere humans, the more likely it is that it may unwittingly behave in ways a human would consider unethical. To explore ways to prevent this from happening, IBM researchers taught AI to play PacMan without ever gobbling up the ghosts. And it did so without ever explicitly telling the software that this was the goal. Over at Fast Company, I wrote about this project and what IBM learned from conducting it. The researchers built a piece of software that could balance the AI's ratio of selfdevised, aggressive game play to humaninfluenced ghost avoidance, and tried different settings to see how they affected its overall approach to the game. By doing so, they found a tipping point  the setting at which PacMan went from seriously chowing down on ghosts to largely avoiding them.
收起

We introduce a connection between a nearterm quantum computing device, specifically a Gaussian boson sampler, and the graph isomorphism problem. We propose a scheme where graphs are encoded into quantum states of light, whose properties are then probed with photonnumberresolving detectors. We prove that the probabilities of different photondetection events in this setup can be combined to give a complete set of graph invariants. Two graphs are isomorphic if and only if their detection probabilities are equivalent. We present additional ways that the measurement probabilities can be combined or coarsegrained to make experimental tests more amenable. We benchmark these methods with numerical simulations on the Titan supercomputer for several graph families: pairs of isospectral nonisomorphic graphs, isospectral regular graphs, and strongly regular graphs.
收起

In this paper, we define a class of slice mappings of several Clifford variables, and the corresponding slice regular mappings. Furthermore, we establish the growth theorem for slice regular starlike or convex mappings on the unit ball of several slice Clifford variables, as well as on the bounded slice domain which is slice starlike and slice circular.
收起

We consider hamiltonian models representing an arbitrary number of spin $1/2$ fermion quantum fields interacting through arbitrary processes of creation or annihilation of particles. The fields may be massive or massless. The interaction form factors are supposed to satisfy some regularity conditions in both position and momentum space. Without any restriction on the strength of the interaction, we prove that the Hamiltonian identifies to a selfadjoint operator on a tensor product of antisymmetric Fock spaces and we establish the existence of a ground state. Our results rely on new interpolated $N_\tau$ estimates. They apply to models arising from the Fermi theory of weak interactions, with ultraviolet and spatial cutoffs.
收起

In the last two decades, significant effort has been put in understanding and designing socalled structurepreserving numerical methods for the simulation of mechanical systems. Geometric integrators attempt to preserve the geometry associated to the original system as much as possible, such as the structure of the configuration space, the energy behaviour, preservation of constants of the motion and of constraints or other structures associated to the continuous system (symplecticity, Poisson structure...). In this article, we develop highorder geometric (or pseudovariational) integrators for nonholonomic systems, i.e., mechanical systems subjected to constraint functions which are, roughly speaking, functions on velocities that are not derivable from position constraints. These systems realize rolling or certain kinds of sliding contact and are important for describing different classes of vehicles.
收起

Let $(X,H)$ be a polarized K3 surface with $\mathrm{Pic}(X) = \mathbb Z H$, and let $C\in H$ be a smooth curve of genus $g$. We give an upper bound on the dimension of global sections of a semistable vector bundle on $C$. This allows us to compute the higher rank Clifford indices of $C$ with high genus. In particular, when $g\geq r^2\geq 4$, the rank $r$ Clifford index of $C$ can be computed by the restriction of LazarsfeldMukai bundles on $X$ corresponding to line bundles on the curve $C$. This is a generalization of the result by Green and Lazarsfeld for curves on K3 surfaces to higher rank vector bundles. We also apply the same method to the projective plane and show that the rank $r$ Clifford index of a degree $d(\geq 5)$ smooth plane curve is $d4$, which is the same as the Clifford index of the curve.
收起

We extend to arbitrary commutative base rings a recent result of Demeneghi that every ideal of an ample groupoid algebra over a field is an intersection of kernels of induced representations from isotropy groups, with a much shorter proof, by using the author's Disintegration Theorem for groupoid representations. We also prove that every primitive ideal is the kernel of an induced representation from an isotropy group; however, we are unable to show, in general, that it is the kernel of an irreducible induced representation. If each isotropy group is finite (e.g., if the groupoid is principal) and if the base ring is Artinian (e.g., a field), then we can show that every primitive ideal is the kernel of an irreducible representation induced from isotropy.
收起

High dimensional error covariance matrices are used to weight the contribution of observation and background terms in data assimilation procedures. As error covariance matrices are often obtained by sampling methods, the resulting matrices are often degenerate or illconditioned, making them too expensive to use in practice. In order to combat these problems, reconditioning methods are used. In this paper we present new theory for two existing methods that can be used to reduce the condition number of (or 'recondition') any covariance matrix: ridge regression, and the minimum eigenvalue method. These methods are used in practice at numerical weather prediction centres, but their theoretical impact on the covariance matrix itself is not well understood. Here we address this by investigating the impact of reconditioning on variances and covariances of a general covariance matrix in both a theoretical and practical setting. Improved theoretical understanding provides guidance to users wit
收起

The Defense Advanced Research Projects Agency (DARPA), a division of the U.S. Department of Defense responsible for the development of emerging technologies, is one of the birthplaces of machine learning, a kind of artificial intelligence (AI) that mimics the behavior of neurons in the brain. Dr. Brian Pierce, director of DARPA's Innovation Office, spoke about the agency's recent efforts at a VentureBeat summit. From the report: One area of study is socalled "common sense" AI  AI that can draw on environmental cues and an understanding of the world to reason like a human. Concretely, DARPA's Machine Common Sense Program seeks to design computational models that mimic core domains of cognition: objects (intuitive physics), places (spatial navigation), and agents (intentional actors). "You could develop a classifier that could identify a number of objects in an image, but if you ask a question, you're not going to get an answer," Pierce said. "We'd like to get away from having an enor
收起

Like many people, Alex Stamos, former Facebook chief security officer, thinks tech platforms like Facebook and Google have too much power. But he doesn't agree with the calls to break them up. And he argues that the very people who say Facebook and Google are too powerful are giving them more power by insisting they do more to control hate speech and propaganda. From a report: "That's a dangerous path," he warns. If democratic countries make tech firms impose limits on free speech, so will autocratic ones. Before long, the technology will enable "machinespeed, realtime moderation of everything we say online." In attempting to rein in Big Tech, we risk creating Big Brother. So what's the solution? I spoke to Stamos at his Stanford office to find out. Technology Review: So is the disinformation/propaganda problem mostly solved? Stamos: In a free society, you will never eliminate that problem. I think the most important thing [in the US] is the advertising transparency. With or without
收起

Ars technica takes a look at the Enhanced Tracking Protection (ETP) feature in Firefox 63. "Firefox has long had the ability to block all thirdparty cookies, but this is a crude solution, and many sites will break if all thirdparty cookies are prohibited. The new EPT option works as a more selective block on tracking cookies; thirdparty cookies still work in general, but those that are known to belong to tracking companies are blocked. For the most part, sites will retain their full functionality, just without undermining privacy at the same time. At least for now, however, Mozilla is defaulting this feature to off, so the company can get a better idea of the impact it has on the Web. In testing, the company has found the occasional site that breaks when tracking cookies are blocked. Over the next few months, Firefox developers will get a better picture of just how much breaks, and, if it's not too severe, the plan is to block trackers by default starting in early 2019.
收起

Ever since Microsoft settled on a cadence of two feature updates a year  one in April, one in October  the quality of its operating system (taking into consideration the volume of bugs that emerge every few days) has deteriorated, writes Peter Bright of ArsTechnica. From the story: The problem with Windows as a Service is quality. Previous issues with the feature and security updates have already shaken confidence in Microsoft's updating policy for Windows 10. While data is notably lacking, there is at the very least a popular perception that the quality of the monthly security updates has taken a dive with Windows 10 and that installation of the twiceannual feature updates as soon as they're available is madness. These complaints are longstanding, too. The unreliable updates have been a cause for concern since shortly after Windows 10's release. The latest problem has brought this to a head, with commentators saying that two feature updates a year is too many and Redmond should
收起

According to a press release posted today, Netflix is planning to raise $2 billion to help fund new content, including "content acquisitions, production and development, capital expenditures, investments, working capital and potential acquisitions and strategic transactions." TechCrunch reports: The funds will be raised in the form of senior unsecured notes, denominated in U.S. dollars and euros, it said. This debt offering is the sixth time in under four years that Netflix is raising $1 billion or more through bonds, noted Variety, which was among the first to report the news. As of September 30, Netflix's longterm debt had reached $8.34 billion, up 71% from $4.89 billion in the year ago quarter, it said during its last earnings, Variety's report also noted. Netflix recently explained during its Q3 2018 earnings that it needs to continue to invest in original programming in order to remain competitive. "Content companies such as WarnerMedia and Disney/Fox are moving to selfdistribut
收起

If it seems as though the app you deleted last week is suddenly popping up everywhere, it may not be mere coincidence. From a report: Companies that cater to app makers have found ways to game both iOS and Android, enabling them to figure out which users have uninstalled a given piece of software lately  and making it easy to pelt the departed with ads aimed at winning them back. Adjust, AppsFlyer, MoEngage, Localytics, and CleverTap are among the companies that offer uninstall trackers, usually as part of a broader set of developer tools. Their customers include TMobile US, Spotify Technology, and Yelp. Critics say they're a fresh reason to reassess online privacy rights and limit what companies can do with user data. "Most tech companies are not giving people nuanced privacy choices, if they give them choices at all," says Jeremy Gillula, tech policy director at the Electronic Frontier Foundation, a privacy advocate. Some providers say these tracking tools are meant to measure use
收起

Brendan Iribe, the cofounder and former CEO of Oculus, announced today that he is leaving Facebook. From a report: Iribe is leaving Facebook following some internal shakeups in the company's virtual reality arm last week that saw the cancellation of the company's next generation "Rift 2" PCpowered virtual reality headset, which he had been leading development of, a source close to the matter told TechCrunch. Iribe and the Facebook executive team had "fundamentally different views on the future of Oculus that grew deeper over time," and Iribe wasn't interested in a "race to the bottom" in terms of performance, we are told.
收起

This paper is devoted to survey composition algebras and some of their applications. After overviewing the classical algebras of quaternions and octonions, both unital composition algebras (or Hurwitz algebras) and symmetric composition algebras will be dealt with. Their main properties, as well as their classifications, will be reviewed. Algebraic triality, through the use of symmetric composition algebras, will be considered too.
收起

We study the scheduling of computation tasks across $n$ workers in a large scale distributed learning problem. Computation speeds of the workers are assumed to be heterogeneous and unknown to the master, and redundant computations are assigned to workers in order to tolerate straggling workers. We consider sequential computation and instantaneous communication from each worker to the master, and each computation round, which can model a single iteration of the stochastic gradient descent algorithm, is completed once the master receives $k$ distinct computations from the workers. Our goal is to characterize the average completion time as a function of the computation load, which denotes the portion of the dataset available at each worker. We propose two computation scheduling schemes that specify the computation tasks assigned to each worker, as well as their computation schedule, i.e., the order of execution, and derive the corresponding average completion time in closedform. We also
收起

We investigate the connectivity of wireless sensor networks secured by the heterogeneous random pairwise key predistribution scheme. In contrast to the homogeneous scheme proposed by Chan et al., where each node is paired (offline) with $K$ other nodes chosen uniformly at random; herein, each node is classified as class$1$ with probability $\mu$ or class$2$ with probability $1\mu$, for $0<\mu<1$, independently. Then, each class$1$ (respectively, class$2$) node is paired (offline) with $K_1$ (respectively, $K_2$) other nodes selected uniformly at random. We consider the particular case when $K_1=1$ and $K_2=K$. The heterogeneous random pairwise scheme induces an inhomogeneous random Kout graph $\mathbb{H} (n;\mu,K_n)$, where $n$ denotes the number of nodes and $K_n$ denotes a scaling of $K$ with respect to the network size $n$. Hence, establishing the connectivity of wireless sensor networks secured by the heterogeneous random pairwise scheme maps to deriving conditions on h
收起

This paper deals with a homoskedastic errorsinvariables linear regression model and properties of the total least squares (TLS) estimator. We partly revise the consistency results for the TLS estimator previously obtained by the author [18]. We present complete and comprehensive proofs of consistency theorems. A theoretical foundation for construction of the TLS estimator and its relation to the generalized eigenvalue problem is explained. Particularly, the uniqueness of the estimate is proved. The Frobenius norm in the definition of the estimator can be substituted by the spectral norm, or by any other unitarily invariant norm; then the consistency results are still valid.
收起

In this paper we prove that when the geodesic flow of a compact or noncompact complete manifold without conjugate points is of the Anosov type, then the average along of the sectional curvature in planes tangent to the geodesic is negative away from zero for some uniform time. Moreover, in dimension two, if the manifold has no focal points, then the latter condition is sufficient to obtain that the geodesic flow is of Anosov type.
收起

We study weak solutions of the twodimensional (2D) filtered Euler equations whose vorticity is a finite Radon measure and velocity has locally finite kinetic energy, which is called the vortex sheet solution. The 2D filtered Euler equations are considered as a regularized 2D Euler equations with a spatial filtering and these equations have a unique global weak solution for vortex sheet initial data. On the other hand, the 2D Euler equations require a distinguished sign of initial vorticity for the existence of a global solution with vortex sheet initial data and its uniqueness remains an open question. In this paper, we prove that vortex sheet solutions of the 2D filtered Euler equations converge to those of the 2D Euler equations in the limit of the filtering parameter provided that initial vortex sheet has a distinguished sign. We also show that a simple application of our proof yields the convergence of the vortex method that is a point vortex approximation of vortex sheets. We mak
收起

It is known that every torsionfree abelian group of finite rank has a maximal completely decomposable summand that is unique up to isomorphism. We show that groups of infinite rank need not have maximal completely decomposable summands, but when they do, this summand is unique up to isomorphism.
收起