478 Result(s)
within
Chapter
**e **an
Mathematics
Algorithm Analysis and Problem Complexity
Artificial Intelligence
-
Chapter
Synchronous SGD and Straggler-Resilient Variants
For large training datasets, it can be prohibitively slow to conduct sequential SGD training at a single node, as we described in Chap. 1.
-
Chapter and Conference Paper
Dynamic Compact Planar Embeddings
This paper presents a way to compactly represent dynamic connected planar embeddings, which may contain self loops and multi-edges, in \(4m + o(m)\) ...
-
Chapter and Conference Paper
Efficient Parameterized Pattern Matching in Sublinear Space
The parameterized matching problem is a variant of string matching, which is to search for all parameterized occurrences of a pattern P in a text T. In considering matching algorithms, the combinatorial natures o...
-
Chapter and Conference Paper
Linear Interpolation of Program Control with Respect to a Multidimensional Parameter in the Convergence Problem
We consider a control system containing a constant three-dimensional vector parameter, the approximate value of which is reported to the control person only at the moment of the movement start. The set of poss...
-
Chapter
Local-Update and Overlap SGD
In the last two chapters, we studied synchronous and asynchronous SGD, where the workers compute mini-batch gradients and the parameter server aggregates them and updates the model. Both these algorithms and t...
-
Chapter and Conference Paper
String Covers of a Tree Revisited
We consider covering labeled trees with a collection of paths with the same string label, called a (string) cover of a tree. This problem was originated by Radoszewski et al. (SPIRE 2021), who show how to comp...
-
Chapter and Conference Paper
Uncertainty of Graph Clustering in Correlation Block Model
Cluster analysis is a powerful tool in network science and it is well developed in many directions. However, the uncertainty analysis of clustering algorithms is still not sufficiently investigated in the lite...
-
Chapter
Decentralized SGD and Its Variants
In all the distributed SGD implementations that we studied so far, namely, synchronous SGD.
-
Chapter and Conference Paper
Constant Time and Space Updates for the Sigma-Tau Problem
Sawada and Williams in [SODA 2018] and [ACM Trans. Alg. 2020] gave algorithms for constructing Hamiltonian paths and cycles in the Sigma-Tau graph, thereby solving a problem of Nijenhuis and Wilf that had been...
-
Chapter and Conference Paper
Algorithms and Hardness for the Longest Common Subsequence of Three Strings and Related Problems
A string is called a square (resp. cube) if it is in the form of \(XX=X^2\) (resp. ...
-
Chapter and Conference Paper
Using General Least Deviations Method for Forecasting of Crops Yields
Nowadays much attention has been paid to the development of the software, which makes it possible to process and visualize images, and in particular, develop the mathematical models for monitoring and predicti...
-
Chapter and Conference Paper
Frequency-Constrained Substring Complexity
We introduce the notion of frequency-constrained substring complexity. For any finite string, it counts the distinct substrings of the string per length and frequency class. For a string x of length n and a parti...
-
Chapter and Conference Paper
Towards Subderivative-Based Zeroing Neural Networks
Zeroing Neural Networks (ZNN) are dynamic systems suitable for studying and solving time-varying problems. The advantage of this particular type of recurrent neural networks (RNNs) is their global and exponent...
-
Chapter and Conference Paper
Longest Common Prefix Arrays for Succinct k-Spectra
The k-spectrum of a string is the set of all distinct substrings of length k occurring in the string. K-spectra have many applications in bioinformatics including pseudoalignment and genome assembly. The Spectral...
-
Chapter and Conference Paper
Online Optimization Problems with Functional Constraints Under Relative Lipschitz Continuity and Relative Strong Convexity Conditions
In this work, we consider the problem of strongly convex online optimization with convex inequality constraints. A scheme with switching over productive and non-productive steps is proposed for these problems....
-
Chapter and Conference Paper
Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph
In this paper, we present the first study of the computational complexity of converting an automata-based text index structure, called the Compact Directed Acyclic Word Graph (CDAWG), of size e for a text T of le...
-
Chapter and Conference Paper
Implementing One Variant of the Successive Concessions Method for the Multi-objective Optimization Problem
We propose one variant of the successive concessions method for solving a multi-objective optimization problem, which differs from the mentioned famous method by the approach of determining concessions. The co...
-
Chapter and Conference Paper
Approximate Cartesian Tree Matching: An Approach Using Swaps
Cartesian tree pattern matching consists of finding all the factors of a text that have the same Cartesian tree than a given pattern. There already exist theoretical and practical solutions for the exact case....
-
Chapter and Conference Paper
Estimation of Both Unknown Parameters in Gaussian Multi-armed Bandit for Batch Processing Scenario
We consider a Gaussian multi-armed bandit problem with both reward means and variances unknown. A Gaussian multi-armed bandit is considered because in case of batch processing the cumulative rewards for the ba...
-
Chapter and Conference Paper
Approximation Algorithms for Graph Cluster Editing Problems with Cluster Size at Most 3 and 4
In clustering problems, one has to partition a given set of objects into pairwise disjoint subsets (clusters) taking into account only similarity of objects. In the graph cluster editing problem similarity rel...
