Viewing Dehn's algorithm as a rewriting system, we generalise to allow an alphabet containing letters which do not necessarily represent group elements. This extends the class of groups for which the algorithm solves the word problem to include nilpotent groups, many relatively hyperbolic groups including geometrically…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “grouping algorithm”
New concept of within-group fairness improves AI fairness without sacrificing accuracy.
problem Fairness issues in AI models treating individuals in the same sensitive group unfairly.
method Introducing within-group fairness, proposing mathematical definitions, and developing learning algorithms.
result Improves within-group fairness without sacrificing accuracy and between-group fairness.
Proposes a group-splicing algorithm for efficient BSGS in high-dimensional settings.
problem Efficiently selecting a small part of non-overlapping groups for best interpretability in high-dimensional settings.
method Iteratively detects relevant groups and excludes irrelevant ones using a novel group information criterion.
result Certifiable polynomial-time algorithm for identifying the optimal subset of groups with high probability.
The group lasso is a penalized regression method, used in regression problems where the covariates are partitioned into groups to promote sparsity at the group level. Existing methods for finding the group lasso estimator either use gradient projection methods to update the entire coefficient vector simultaneously at e…
In this paper, we propose a unified framework and an algorithm for the problem of group recommendation where a fixed number of items or alternatives can be recommended to a group of users. The problem of group recommendation arises naturally in many real world contexts, and is closely related to the budgeted social cho…
The notions of stable and Morse subgroups of finitely generated groups generalize the concept of a quasiconvex subgroup of a word-hyperbolic group. For a word-hyperbolic group , Kapovich provided a partial algorithm which, on input a finite set of , halts if generates a quasiconvex subgroup of and run…
We present a new algorithm to solve the conjugacy problem in Artin braid groups, which is faster than the one presented by Birman, Ko and Lee. This algorithm can be applied not only to braid groups, but to all Garside groups (which include finite type Artin groups and torus knot groups among others).
New algorithms solve word and conjugacy problems in braid group B3.
problem Word and conjugacy problems in braid group B3.
method Classical interpretation of braid group B3 as central extension of modular group, theory of continued fractions.
result Simple and efficient algorithms to solve word and conjugacy problems in braid group B3.
The paper offers simple, near-optimal algorithms for multi-group learning.
problem Learning predictors within subgroups of a population, addressing fairness and hidden stratification.
method Studies the structure of solutions and provides simple, near-optimal algorithms.
result Simple and near-optimal algorithms for multi-group learning.
Division algorithm for surface group rings yields standard complexes and cohomological dimensions.
problem Understanding cohomological dimensions of surface group actions.
method Division algorithm for group rings of surface groups.
result Some 2-complexes with surface fundamental groups are standard.
Stable Torsion Lengthmath.GR
Study on stable torsion length in groups, showing it vanishes in crystallographic groups and providing algorithms for computation.
problem Understanding the stable torsion length in groups, especially in crystallographic and free products of groups.
method Developed linear programming and exact algorithms to compute stable torsion length in free products of groups and finite groups.
result Showed that stable torsion length vanishes in crystallographic groups and provided exact computations for nontrivial examples.
New algorithm balances exploration cost between groups in multi-armed bandits.
problem Balancing exploration cost between groups in multi-armed bandits.
method Introducing Col-UCB algorithm that dynamically coordinates exploration across groups.
result Achieves optimal minimax and instance-dependent collaborative regret up to logarithmic factors.
An algorithm for efficient computation of equivariant neural network layers.
problem Efficiently computing with Brauer's group equivariant neural network layers.
method Category theoretic constructions and Kronecker product matrices.
result Significant reduction in computational cost compared to naive implementation.
Algorithm constructs surfaces with specific Veech groups in lattice strata.
problem Finding all translation surfaces with a given lattice Veech group.
method Developed an algorithm and provided a new proof of finiteness.
result Algorithm constructs all translation surfaces with a given lattice Veech group.
This is a survey of the recent work in algorithmic and asymptotic properties of groups. I discuss Dehn functions of groups, complexity of the word problem, Higman embeddings, and constructions of finitely presented groups with extreme properties (monsters).
The -means algorithm is extended to allow for partitioning of skewed groups. Our algorithm is called TiK-Means and contributes a -means type algorithm that assigns observations to groups while estimating their skewness-transformation parameters. The resulting groups and transformation reveal general-structured cl…
We present an algorithm that computes Bowditch's canonical JSJ decomposition of a given one-ended hyperbolic group over its virtually cyclic subgroups. The algorithm works by identifying topological features in the boundary of the group. As a corollary we also show how to compute the JSJ decomposition of such a group o…
New algorithms achieve small prediction regret for learning from overlapping groups.
problem Online multi-group learning with fairness applications.
method Oracle-efficient algorithms for groups not explicitly enumerated.
result Sublinear regret in various settings.
New method selects variables in groups with few nonzeros, improving support recovery.
problem Structured variable selection with sparse patterns across groups.
method Composite norm and proximal algorithm for exclusive group sparsity.
result Asymptotic consistency in signed support recovery under conventional assumptions.
Paper tackles underranking in group-fair ranking systems, proving a trade-off and presenting an algorithm.
problem Underranking in group-fair ranking systems can worsen social and economic inequalities.
method Formulated underranking as a new problem, proved a lower bound, and presented a fair ranking algorithm.
result Algorithm achieves best of underranking and group fairness, confirming theoretical trade-off.
Algorithm calculates knot Floer homology for a specific knot type.
problem Computing knot Floer homology for knots.
method Algorithm based on fundamental group of knots.
result Algorithm successfully computes knot Floer homology.
One of the most interesting questions about a group is if its word problem can be solved and how. The word problem in the braid group is of particular interest to topologists, algebraists and geometers, and is the target of intensive current research. We look at the braid group from a topological point of view (rather …
Introduces a reduction system for Artin-Tits groups, improving algorithms and proving periodicity results.
problem Computing reduction systems in Artin-Tits groups of spherical type.
method Introduces a canonical reduction system, proves periodicity of centralizers, and provides algorithms.
result Improved algorithms for computing reduction systems in braid groups and Artin-Tits groups.
We present an algorithm to construct the JSJ decomposition of one-ended hyperbolic groups which are fundamental groups of graphs of free groups with cyclic edge groups. Our algorithm runs in double exponential time, and is the first algorithm on JSJ decompositions to have an explicit time bound. Our methods are combina…
Discrimination via algorithmic decision making has received considerable attention. Prior work largely focuses on defining conditions for fairness, but does not define satisfactory measures of algorithmic unfairness. In this paper, we focus on the following question: Given two unfair algorithms, how should we determine…
Algorithm solves word problem in mapping class group quickly.
problem Word problem in mapping class group of a surface.
method Quasi-linear time algorithm (O(n log^3(n))).
result Solves word problem efficiently.
We solve Dehn's isomorphism problem for virtually torsion-free relatively hyperbolic groups with nilpotent parabolic subgroups. We do so by reducing the isomorphism problem to three algorithmic problems in the parabolic subgroups, namely the isomorphism problem, separation of torsion (in their outer automorphism groups…
CrossWalk enhances fairness in graph algorithms by biasing random walks.
problem Fairness in machine learning systems applied to graphs.
method Bias random walks to cross group boundaries by upweighting edges.
result Enhances fairness in various graph algorithms with minimal performance loss.
AgABC improves ABC algorithm by balancing exploration and exploitation.
problem Balancing global and local search abilities in ABC algorithm.
method Divide population into groups and assign different search strategies to members.
result Proposed AgABC algorithm outperforms other algorithms in accuracy and stability.
FGSV defends against shell company attacks in group data valuation.
problem Shell company attacks on group-level data valuation.
method Developed a provably fast and accurate approximation algorithm for FGSV.
result Empirical results show significant improvement in computational efficiency and accuracy.
In this article, we give a numerical algorithm to compute braid groups of curves, hyperplane arrangements, and parameterized system of polynomial equations. Our main result is an algorithm that determines the cross-locus and the generators of the braid group.
Using a similar algorithm to Hatcher-Thurston's algorithm for finding a presentation of the mapping class group of a surface, Wajnryb succeeded to find a presentation for the handlebody group. This is long and complicated. In this note I simplify Wajnryb's presentation for the handlebody group of genus g = 2.
Recursive Group lassostat.ME
We introduce a recursive adaptive group lasso algorithm for real-time penalized least squares prediction that produces a time sequence of optimal sparse predictor coefficient vectors. At each time index the proposed algorithm computes an exact update of the optimal -penalized recursive least squares (R…
In this paper we purpose a blockwise descent algorithm for group-penalized multiresponse regression. Using a quasi-newton framework we extend this to group-penalized multinomial regression. We give a publicly available implementation for these in R, and compare the speed of this algorithm to a competing algorithm --- w…
We present a detailed description of a fundamental group algorithm based on Forman's combinatorial version of Morse theory. We use this algorithm in a classification problem of prime knots up to 14 crossings.
Study thin hyperbolic reflection groups and their properties.
problem Characterize and enumerate thin hyperbolic reflection groups.
method Analyze Zariski dense subgroups of hyperbolic isometries, apply Vinberg algorithm.
result All thin hyperbolic reflection groups are enumerable.
The sparse group lasso optimization problem is solved using a coordinate gradient descent algorithm. The algorithm is applicable to a broad class of convex loss functions. Convergence of the algorithm is established, and the algorithm is used to investigate the performance of the multinomial sparse group lasso classifi…
A Diagrammatic Approach to Improve Computational Efficiency in Group Equivariant Neural Networkscs.LG
New algorithm speeds up group equivariant neural networks computations.
problem Challenging computations in group equivariant neural networks.
method Diagrammatic framework based on category theory for matrix multiplication.
result Exponential improvement in time complexity for matrix multiplication.
Algorithm finds connected components on Lie groups for multi-orientation image analysis.
problem Finding connected components in complex, multi-orientation images.
method Iterative algorithm using morphological dilations and Hamilton-Jacobi-Bellman kernels on Lie groups.
result Algorithm converges in finitely many steps and can differentiate between crossing and aligned structures.
The study analyzes group testing algorithms for identifying defective items with high confidence.
problem Identifying defective items from a population using group testing with high confidence.
method Formulated as a function learning problem using the PAC framework, analyzed three algorithms: column matching, combinatorial basis pursuit, and definite defectives.
result Derived bounds on the number of tests needed for approximate set identification, comparing with existing bounds and simulating performance.
Adyan and Rabin showed that most properties of groups cannot be algorithmically recognized from a finite presentation alone. We prove that, if one is also given a solution to the word problem, then the class of fundamental groups of closed, geometric 3-manifolds is algorithmically recognizable. In our terminology, the …
New algorithms allocate sampling budget to estimate group means without exploration.
problem Allocate sampling budget to estimate means of multiple groups.
method Design exploration-free non-adaptive and adaptive algorithms.
result Prove tighter regret bounds for multi-group mean estimation.
In query learning, the goal is to identify an unknown object while minimizing the number of "yes or no" questions (queries) posed about that object. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world, time-critical identification tasks such as emergency…
Algorithm distinguishes Fuchsian groups with finite quotients.
problem Distinguishing between non-isomorphic Fuchsian groups.
method Develops an algorithm to create group extensions using finite quotients.
result Establishes an upperbound for the order of a distinguishing finite quotient.
MultiDendrograms is a Java-written application that computes agglomerative hierarchical clusterings of data. Starting from a distances (or weights) matrix, MultiDendrograms is able to calculate its dendrograms using the most common agglomerative hierarchical clustering methods. The application implements a variable-gro…
Paper proposes a new algorithm to minimize AUC disparities in machine learning models.
problem Minimizing unfairness in AUC scores for machine learning models.
method Proposes a minimax learning and bias mitigation framework for AUC optimization.
result Proves the convergence of the proposed algorithm to minimize group-level AUC.
We show that the isomorphism problem is solvable in the class of central extensions of word-hyperbolic groups, and that the isomorphism problem for biautomatic groups reduces to that for biautomatic groups with finite centre. We describe an algorithm that, given an arbitrary finite presentation of an automatic group $Γ…
Algorithm decides homeomorphism of 4-manifolds.
problem Deciding homeomorphism of closed, simply connected 4-manifolds.
method Represent 4-manifolds by Kirby diagrams, compute Kirby-Siebenmann invariant, and use algorithms for Kirby diagrams and intersection forms.
result Algorithmic decision for homeomorphism of 4-manifolds.