In this survey, we address the worst-case, average-case, and generic-case time complexity of the word problem and some other algorithmic problems in several classes of groups and show that it is often the case that the average-case complexity of the word problem is linear with respect to the length of an input word, which is as good as it gets if one considers groups given by generators and defining relations. At the same time, there are other natural algorithmic problems, for instance, the geodesic (decision) problem or Whitehead's automorphism problem, where the average-case time complexity can be sublinear, even constant.
相關內容
In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of $C^2$ manifolds with positive reach embedded in $\mathbb{R}^d$. We extend their results in the following ways: In the first part of our paper we consider both manifolds of positive reach -- a more general setting than $C^2$ manifolds -- and sets of positive reach embedded in $\mathbb{R}^d$. The sample $P$ of such a set $\mathcal{S}$ does not have to lie directly on it. Instead, we assume that the two one-sided Hausdorff distances -- $\varepsilon$ and $\delta$ -- between $P$ and $\mathcal{S}$ are bounded. We provide explicit bounds in terms of $\varepsilon$ and $ \delta$, that guarantee that there exists a parameter $r$ such that the union of balls of radius $r$ centred at the sample $P$ deformation-retracts to $\mathcal{S}$. In the second part of our paper we study homotopy learning in a significantly more general setting -- we investigate sets of positive reach and submanifolds of positive reach embedded in a \emph{Riemannian manifold with bounded sectional curvature}. To this end we introduce a new version of the reach in the Riemannian setting inspired by the cut locus. Yet again, we provide tight bounds on $\varepsilon$ and $\delta$ for both cases (submanifolds as well as sets of positive reach), exhibiting the tightness by an explicit construction.
In an error estimation of finite element solutions to the Poisson equation, we usually impose the shape regularity assumption on the meshes to be used. In this paper, we show that even if the shape regularity condition is violated, the standard error estimation can be obtained if "bad" elements (elements that violate the shape regularity or maximum angle condition) are covered virtually by "good" simplices. A numerical experiment confirms the theoretical result.
In this paper, we study three representations of lattices by means of a set with a binary relation of compatibility in the tradition of Plo\v{s}\v{c}ica. The standard representations of complete ortholattices and complete perfect Heyting algebras drop out as special cases of the first representation, while the second covers arbitrary complete lattices, as well as complete lattices equipped with a negation we call a protocomplementation. The third topological representation is a variant of that of Craig, Haviar, and Priestley. We then extend each of the three representations to lattices with a multiplicative unary modality; the representing structures, like so-called graph-based frames, add a second relation of accessibility interacting with compatibility. The three representations generalize possibility semantics for classical modal logics to non-classical modal logics, motivated by a recent application of modal orthologic to natural language semantics.
In this note we consider the problem of ParaTuck-2 decomposition of a three-way tensor.We provide an algebraic algorithm for finding the ParaTuck-2 decomposition for the case when the ParaTuck-2 ranks are smaller than the frontal dimensions of the tensors.Our approach relies only on linear algebra operations and is based on finding the kernel of a structured matrix constructed from the tensor.
Effective application of mathematical models to interpret biological data and make accurate predictions often requires that model parameters are identifiable. Approaches to assess the so-called structural identifiability of models are well-established for ordinary differential equation models, yet there are no commonly adopted approaches that can be applied to assess the structural identifiability of the partial differential equation (PDE) models that are requisite to capture spatial features inherent to many phenomena. The differential algebra approach to structural identifiability has recently been demonstrated to be applicable to several specific PDE models. In this brief article, we present general methodology for performing structural identifiability analysis on partially observed reaction-advection-diffusion (RAD) PDE models that are linear in the unobserved quantities. We show that the differential algebra approach can always, in theory, be applied to such models. Moreover, despite the perceived complexity introduced by the addition of advection and diffusion terms, identifiability of spatial analogues of non-spatial models cannot decrease in structural identifiability. We conclude by discussing future possibilities and the computational cost of performing structural identifiability analysis on more general PDE models.
Program synthesis with Genetic Programming searches for a correct program that satisfies the input specification, which is usually provided as input-output examples. One particular challenge is how to effectively handle loops and recursion avoiding programs that never terminate. A helpful abstraction that can alleviate this problem is the employment of Recursion Schemes that generalize the combination of data production and consumption. Recursion Schemes are very powerful as they allow the construction of programs that can summarize data, create sequences, and perform advanced calculations. The main advantage of writing a program using Recursion Schemes is that the programs are composed of well defined templates with only a few parts that need to be synthesized. In this paper we make an initial study of the benefits of using program synthesis with fold and unfold templates, and outline some preliminary experimental results. To highlight the advantages and disadvantages of this approach, we manually solved the entire GPSB benchmark using recursion schemes, highlighting the parts that should be evolved compared to alternative implementations. We noticed that, once the choice of which recursion scheme is made, the synthesis process can be simplified as each of the missing parts of the template are reduced to simpler functions, which are further constrained by their own input and output types.
In the present paper, we establish the well-posedness, stability, and (weak) convergence of a fully-discrete approximation of the unsteady $p(\cdot,\cdot)$-Navier-Stokes equations employing an implicit Euler step in time and a discretely inf-sup-stable finite element approximation in space. Moreover, numerical experiments are carried out that supplement the theoretical findings.
In this work, we propose and computationally investigate a monolithic space-time multirate scheme for coupled problems. The novelty lies in the monolithic formulation of the multirate approach as this requires a careful design of the functional framework, corresponding discretization, and implementation. Our method of choice is a tensor-product Galerkin space-time discretization. The developments are carried out for both prototype interface- and volume coupled problems such as coupled wave-heat-problems and a displacement equation coupled to Darcy flow in a poro-elastic medium. The latter is applied to the well-known Mandel's benchmark and a three-dimensional footing problem. Detailed computational investigations and convergence analyses give evidence that our monolithic multirate framework performs well.
This essay provides a comprehensive analysis of the optimization and performance evaluation of various routing algorithms within the context of computer networks. Routing algorithms are critical for determining the most efficient path for data transmission between nodes in a network. The efficiency, reliability, and scalability of a network heavily rely on the choice and optimization of its routing algorithm. This paper begins with an overview of fundamental routing strategies, including shortest path, flooding, distance vector, and link state algorithms, and extends to more sophisticated techniques.
When and why can a neural network be successfully trained? This article provides an overview of optimization algorithms and theory for training neural networks. First, we discuss the issue of gradient explosion/vanishing and the more general issue of undesirable spectrum, and then discuss practical solutions including careful initialization and normalization methods. Second, we review generic optimization methods used in training neural networks, such as SGD, adaptive gradient methods and distributed methods, and theoretical results for these algorithms. Third, we review existing research on the global issues of neural network training, including results on bad local minima, mode connectivity, lottery ticket hypothesis and infinite-width analysis.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191