More Like this

1. Generically computable Abelian groups

   https://doi.org/10.1007/978-3-031-34034-5_3  

   Calvert, W.; Cenzer, D.; Harizanov, V. (June 2023, Unconventional Computation and Natural Computation)

   Genova, D.; Kari, J. (Ed.)

   Generically computable sets, as introduced by Jockusch and Schupp, have been of great interest in recent years. This idea of approximate computability was motivated by asymptotic density problems studied by Gromov in combinatorial group theory. More recently, we have defined notions of generically computable structures, and studied in particular equivalence structures and injection structures. A structure is said to be generically computable if there is a c.e. substructure defined on an asymptotically dense set, where the functions are computable and the relations are computably enumerable. It turned out that every equivalence structure has a generically computable copy, whereas there is a non-trivial characterization of the injection structures with generically computable copies. In this paper, we return to group theory, as we explore the generic computability of Abelian groups. We show that any Abelian p-group has a generically computable copy and that such a group has a Σ2-generically computably enumerable copy if and only it has a computable copy. We also give a partial characterization of the Σ1-generically computably enumerable Abelian p-groups. We also give a non-trivial characterization of the generically computable Abelian groups that are not p-groups. 

   more » « less
2. Machine Learning and Data Mining with Combinatorial Optimization Algorithms

   https://doi.org/10.1287/educ.2018.0179  

   Dorit S. Hochbaum (October 2018, INFORMS TutORials in Operations Research)

   Binary classification is a fundamental machine learning task defined as correctly assigning new objects to one of two groups based on a set of training objects. Driven by the practical importance of binary classification, numerous machine learning techniques have been developed and refined over the last three decades. Among the most popular techniques are artificial neural networks, decision trees, ensemble methods, logistic regression, and support vector machines. We present here machine learning and pattern recognition algorithms that, unlike the commonly used techniques, are based on combinatorial optimization and make use of information on pairwise relations between the objects of the data set, whether training objects or not. These algorithms solve the respective problems optimally and efficiently, in contrast to the primarily heuristic approaches currently used for intractable problem models in pattern recognition and machine learning. The algorithms described solve efficiently the classification problem as a network flow problem on a graph. The technical tools used in the algorithm are the parametric cut procedure and a process called sparse computation that computes only the pairwise similarities that are “relevant.” Sparse computation enables the scalability of any algorithm that uses pairwise similarities. We present evidence on the effectiveness of the approaches, measured in terms of accuracy and running time, in pattern recognition, image segmentation, and general data mining. 

   more » « less
3. Fractional Hardy-type and trace theorems for nonlocal function spaces with heterogeneous localization

   https://doi.org/10.1142/S0219530521500329  

   Du, Qiang; Mengesha, Tadele; Tian, Xiaochuan (May 2022, Analysis and Applications)

   This work aims to prove a Hardy-type inequality and a trace theorem for a class of function spaces on smooth domains with a nonlocal character. Functions in these spaces are allowed to be as rough as an [Formula: see text]-function inside the domain of definition but as smooth as a [Formula: see text]-function near the boundary. This feature is captured by a norm that is characterized by a nonlocal interaction kernel defined heterogeneously with a special localization feature on the boundary. Thus, the trace theorem we obtain here can be viewed as an improvement and refinement of the classical trace theorem for fractional Sobolev spaces [Formula: see text]. Similarly, the Hardy-type inequalities we establish for functions that vanish on the boundary show that functions in this generalized space have the same decay rate to the boundary as functions in the smaller space [Formula: see text]. The results we prove extend existing results shown in the Hilbert space setting with p = 2. A Poincaré-type inequality we establish for the function space under consideration together with the new trace theorem allows formulating and proving well-posedness of a nonlinear nonlocal variational problem with conventional local boundary condition. 

   more » « less
4. Computing discrete residues of rational functions

   https://doi.org/10.1145/3666000.3669676  

   Arreche, Carlos E; Sitaula, Hari (July 2024, ACM)

   In 2012 Chen and Singer introduced the notion of discrete residues for rational functions as a complete obstruction to rational summability. More explicitly, for a given rational function f(x), there exists a rational function g(x) such that f(x) = g(x+1) - g(x) if and only if every discrete residue of f(x) is zero. Discrete residues have many important further applications beyond summability: to creative telescoping problems, thence to the determination of (differential-)algebraic relations among hypergeometric sequences, and subsequently to the computation of (differential) Galois groups of difference equations. However, the discrete residues of a rational function are defined in terms of its complete partial fraction decomposition, which makes their direct computation impractical due to the high complexity of completely factoring arbitrary denominator polynomials into linear factors. We develop a factorization-free algorithm to compute discrete residues of rational functions, relying only on gcd computations and linear algebra. 

   more » « less
5. A unified approach for a 1D generalized total variation problem

   https://doi.org/10.1007/s10107-021-01633-2  

   Lu, Cheng; Hochbaum, Dorit S. (July 2021, Mathematical Programming)

   null (Ed.)

   Abstract We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush–Kuhn–Tucker optimality conditions. This approach is shown here to lead to a fast algorithm for the problem with general convex fidelity and regularization functions, and a faster algorithm if, in addition, the fidelity functions are differentiable and the regularization functions are strictly convex. Both algorithms achieve the best theoretical worst case complexity over existing algorithms for the classes of objective functions studied here. Also in practice, our C++ implementation of the method is considerably faster than popular C++ nonlinear optimization solvers for the problem. 

   more » « less