Concept

Levenshtein distance

Related publications (26)

A Gapless Post-quantum Hash Proof System in the Hamming Metric

A hash proof system (HPS) is a form of implicit proof of membership to a language. Out of the very few existing post-quantum HPS, most are based on languages of ciphertexts of code-based or lattice-based cryptosystems and inherently suffer from a gap cause ...

2023

Tangent functional connectomes uncover more unique phenotypic traits

Enrico Amico, Mingkui Wang

Functional connectomes (FCs) containing pairwise estimations of functional couplings between pairs of brain regions are commonly represented by correlation matrices. As symmetric positive definite matrices, FCs can be transformed via tangent space projecti ...

CELL PRESS2023

An Improved Analysis of Local Search for Max-Sum Diversification

Friedrich Eisenbrand, Rico Zenklusen, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

New Results On The Pseudoredundancy

Jens Markus Zumbrägel, Zihui Liu

The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding ...

2019

Spherical Clustering of Users Navigating 360° Content

Pascal Frossard, Francesca De Simone, Laura Toni

In Virtual Reality (VR) applications, understanding how users explore the omnidirectional content is important to optimize content creation, to develop user-centric services, or even to detect disorders in medical applications. Clustering users based on th ...

IEEE2019

Formal Analysis of Distance Bounding with Secure Hardware

Serge Vaudenay, Handan Kilinç Alper

A distance bounding (DB) protocol is a two-party authentication protocol between a prover and a verifier which is based on the distance between the prover and the verifier. It aims to defeat threats by malicious provers who try to convince that they are cl ...

2018

Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels

Rüdiger Urbanke, Seyed Hamed Hassani, Shrinivas Kudekar, Yury Polyanskiy

Consider a binary linear code of length N, minimum distance d(min), transmission over the binary erasure channel with parameter 0 < epsilon < 1 or the binary symmetric channel with parameter 0 < epsilon < 1/2, and block-MAP decoding. It was shown by Tillic ...

IEEE2018

Omnidirectional bats, point-to-plane distances, and the price of uniqueness

Martin Vetterli, Ivan Dokmanic, Miranda Krekovic

We study simultaneous localization and mapping with a device that uses reflections to measure its distance from walls. Such a device can be realized acoustically with a synchronized collocated source and receiver; it behaves like a bat with no capacity for ...

Ieee2017

Dynamic Facility Location via Exponential Clocks

Ola Nils Anders Svensson, Ashkan Norouzi Fard, Hyung Chan An

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance ...

Association for Computing Machinery2017

Distance Bounding based on PUF

Serge Vaudenay, Mathilde Igier

Distance Bounding (DB) is designed to mitigate relay attacks. This paper provides a complete study of the DB protocol of Kleber et al. based on Physical Unclonable Functions (PUFs). We contradict the claim that it resists to Terrorist Fraud (TF). We propos ...

Springer Int Publishing Ag2016

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

Do We Need Binary Features for 3D Reconstruction?

Pascal Fua, Xinchao Wang, Zhiye Wang, Bin Fan

Binary features have been incrementally popular in the past few years due to their low memory footprints and the efficient computation of Hamming distance between binary descriptors. They have been shown with promising results on some real time application ...

2016

Space lower bounds for low-stretch greedy embeddings

Christos Kalaitzis

Greedy (geometric) routing is an important paradigm for routing in communication networks. It uses an embedding of the nodes of a network into points of a space (e.g., R-d) equipped with a distance function (e.g., the Euclidean distance l(2)) and uses as a ...

Elsevier Science Bv2016

Cross-lingual Linking of Multi-word Entities and their corresponding Acronyms

Maud Ehrmann

This paper reports on an approach and experiments to automatically build a cross-lingual multi-word entity resource. Starting from a collection of millions of acronym/expansion pairs for 22 languages where expansion variants were grouped into monolingual c ...

European Language Resources Association (ELRA)2016

A Method for Record Linkage with Sparse Historical Data

Maud Ehrmann, Yannick Rochat, Giovanni Colavizza

Massive digitization of archival material, coupled with automatic document processing techniques and data visualisation tools offers great opportunities for reconstructing and exploring the past. Unprecedented wealth of historical data (e.g. names of perso ...

2016

Challenges in Distance Bounding

Serge Vaudenay

Smartcard-based protocols represent an increasingly large share of the wireless authentication market, from contactless payments to remote car unlocking. Unfortunately, relay attacks pose a significant threat to these wireless solutions. However, this risk ...

Ieee Computer Soc2015

Evaluation of control strategies for fixed-wing drones following slow-moving ground agents

Dario Floreano, Jean-Christophe Zufferey, Grégoire Hilaire Marie Heitz, Maja Varga

There are many situations where fixed-wing drones may be required to track ground moving agents, such as humans or cars, which are typically slower than drones. Some control strategies have been proposed and validated in simulations using the average dista ...

Elsevier2015

Budgeted sensor placement for source localization on trees

Patrick Thiran, Laura Elisa Celis, Brunella Marta Spinelli

We address the problem of choosing a fixed number of sensor vertices in a graph in order to detect the source of a partially-observed diffusion process on the graph itself. Building on the definition of double resolvability we introduce a notion of vertex ...

2015

Models and Algorithms for Comparative Genomics

Mingfu Shao

The deluge of sequenced whole-genome data has motivated the study of comparative genomics, which provides global views on genome evolution, and also offers practical solutions in deciphering the functional roles of components of genomes. A fundamental comp ...

EPFL2015

Indoor localization method and system

Martin Vetterli, Reza Parhizkar, Gilles Baechler

An indoor localization method for estimating the location of nodes (n1, n2), at least one node (n1) being connected to at least another node (n2) by at least two different channels (ch1, ch1′), comprising the following steps: measuring a distance between t ...

2015