Exclusivity probes

Dennis Shasha

doi:10.1145/3538640

Exclusivity probes

Research output: Contribution to journal › Article › peer-review

Abstract

There are some number of particles in a force field. By an exclusion principle they must differ from one another by at least k among d dimensions where each dimension is a binary value. Suppose there is one particle in a three-dimensional space. With exact probes, one might need seven probes to find the location of that particle. The solution to this problem involves the use of a one-away probe at (0,0,0). An ‘exact one-away’ probe gives three answers to probe at location p.

Original language	English (US)
Pages (from-to)	96+95
Journal	Communications of the ACM
Volume	65
Issue number	7
DOIs	https://doi.org/10.1145/3538640
State	Published - Jul 2022

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1145/3538640

Cite this

@article{1ac9ccefc87142c6914e5197754aab4e,

title = "Exclusivity probes",

abstract = "There are some number of particles in a force field. By an exclusion principle they must differ from one another by at least k among d dimensions where each dimension is a binary value. Suppose there is one particle in a three-dimensional space. With exact probes, one might need seven probes to find the location of that particle. The solution to this problem involves the use of a one-away probe at (0,0,0). An {\textquoteleft}exact one-away{\textquoteright} probe gives three answers to probe at location p.",

author = "Dennis Shasha",

year = "2022",

month = jul,

doi = "10.1145/3538640",

language = "English (US)",

volume = "65",

pages = "96+95",

journal = "Communications of the ACM",

issn = "0001-0782",

publisher = "Association for Computing Machinery (ACM)",

number = "7",

}

TY - JOUR

T1 - Exclusivity probes

AU - Shasha, Dennis

PY - 2022/7

Y1 - 2022/7

N2 - There are some number of particles in a force field. By an exclusion principle they must differ from one another by at least k among d dimensions where each dimension is a binary value. Suppose there is one particle in a three-dimensional space. With exact probes, one might need seven probes to find the location of that particle. The solution to this problem involves the use of a one-away probe at (0,0,0). An ‘exact one-away’ probe gives three answers to probe at location p.

AB - There are some number of particles in a force field. By an exclusion principle they must differ from one another by at least k among d dimensions where each dimension is a binary value. Suppose there is one particle in a three-dimensional space. With exact probes, one might need seven probes to find the location of that particle. The solution to this problem involves the use of a one-away probe at (0,0,0). An ‘exact one-away’ probe gives three answers to probe at location p.

UR - http://www.scopus.com/inward/record.url?scp=85132970783&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132970783&partnerID=8YFLogxK

U2 - 10.1145/3538640

DO - 10.1145/3538640

M3 - Article

AN - SCOPUS:85132970783

SN - 0001-0782

VL - 65

SP - 96+95

JO - Communications of the ACM

JF - Communications of the ACM

IS - 7

ER -

Exclusivity probes

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this