Image de couverture de livre

Approximate all-pairs Hamming distances and 0-1 matrix multiplication

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kowaluk, Miroslaw, Lingas, Andrzej, Persson, Mia
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Computational Complexity F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Fast approximate $\ell$-center clustering in high dimensional spaces
par: Kowaluk, Mirosław, et autres
Publié: (2025)

Multiplication of 0-1 matrices via clustering
par: Jansson, Jesper, et autres
Publié: (2025)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
par: Lingas, Andrzej
Publié: (2026)

Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
par: Lingas, Andrzej
Publié: (2024)

The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O(\log n)$ Deterministic Rounds on the Congested Clique
par: Jansson, Jesper, et autres
Publié: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
par: Dvořák, Pavel, et autres
Publié: (2017)

Graph Threading with Turn Costs
par: Demaine, Erik D., et autres
Publié: (2024)

Realizing temporal graphs from fastest travel times
par: Klobas, Nina, et autres
Publié: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
par: Clinch, Katie, et autres
Publié: (2024)

Identity Testing for Circuits with Exponentiation Gates
par: Li, Jiatu, et autres
Publié: (2025)

Towards universally optimal sorting algorithms
par: Sen, Sandeep
Publié: (2025)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
par: Krithika, R., et autres
Publié: (2023)

Spanning Trees Minimizing Branching Costs
par: Gargano, Luisa, et autres
Publié: (2024)

An Algorithm for a Variation of the Shortest Common Superstring Problem
par: Gilfanov, Arthur
Publié: (2024)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
par: Sarriguren, Alfredo Goñi
Publié: (2024)

When Votes Change and Committees Should (Not)
par: Bredereck, Robert, et autres
Publié: (2020)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
par: Goldenberg, Elazar, et autres
Publié: (2022)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
par: Fairbairn, David L., et autres
Publié: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
par: Salas, Jesus
Publié: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
par: Saha, Barna, et autres
Publié: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
par: Jansen, Klaus, et autres
Publié: (2024)

Large cliques and large independent sets: can they coexist?
par: Feige, Uriel, et autres
Publié: (2025)

A Decomposition Approach to the Weighted $k$-server Problem
par: Ayyadevara, Nikhil, et autres
Publié: (2024)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
par: Liao, Chao, et autres
Publié: (2022)

Impact of Knowledge on the Cost of Treasure Hunt in Trees
par: Bouchard, Sébastien, et autres
Publié: (2025)

Approximation Algorithms for Action-Reward Query-Commit Matching
par: Derakhshan, Mahsa, et autres
Publié: (2026)

On Hardness and Approximation of Broadcasting in Structured Graphs
par: Bringolf, Jeffrey, et autres
Publié: (2025)

Approximately Partitioning Vertices into Short Paths
par: Gong, Mingyang, et autres
Publié: (2026)

Approximation algorithms for scheduling with rejection in green manufacturing
par: Gong, Mingyang, et autres
Publié: (2025)

Approximation algorithms for Job Scheduling with reconfigurable resources
par: Bergé, Pierre, et autres
Publié: (2023)

On the Approximability of Unsplittable Flow on a Path with Time Windows
par: Armbruster, Alexander, et autres
Publié: (2025)

Kernelization dichotomies for hitting minors under structural parameterizations
par: Bougeret, Marin, et autres
Publié: (2025)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
par: Bougeret, Marin, et autres
Publié: (2024)

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
par: Mosenzon, Ron
Publié: (2025)

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
par: Ahn, Jungho, et autres
Publié: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
par: DeHaan, Ian, et autres
Publié: (2024)

Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio
par: Kanellopoulos, Sotiris, et autres
Publié: (2025)

A Note on Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds of the Congested Clique
par: Lingas, Andrzej
Publié: (2024)

An Efficient Algorithm for Unbalanced 1D Transportation
par: Gouvine, Gabriel
Publié: (2023)

Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size
par: Gudmundsson, Joachim, et autres
Publié: (2021)