Near-optimal time-space tradeoff for element distinctness

Andrew Chi Chih Yao

doi:10.1137/S0097539788148959

Near-optimal time-space tradeoff for element distinctness

Andrew Chi Chih Yao

电子与信息学部

科研成果: 期刊稿件 › 文章 › 同行评审

21 引用（Scopus）

摘要

It was conjectured in Borodin et al. that to solve the element distinctness problem requires TS = Ω(n²) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS = O((n log n)²) is achievable. Recently, Borodin et al. showed that TS = Ω(n^3/2(log n)^1/2). This paper presents a near-optimal tradeoff TS = Ω(n^2-ε(n)), where ε(n) = O(1/(log n)^1/2).

源语言	英语
页（从-至）	966-975
页数	10
期刊	SIAM Journal on Computing
卷	23
期	5
DOI	https://doi.org/10.1137/S0097539788148959
出版状态	已出版 - 1994

访问文件

10.1137/S0097539788148959

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{7bc1c02d1a094dbcbf97fea48a4b9d5f,

title = "Near-optimal time-space tradeoff for element distinctness",

abstract = "It was conjectured in Borodin et al. that to solve the element distinctness problem requires TS = Ω(n2) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS = O((n log n)2) is achievable. Recently, Borodin et al. showed that TS = Ω(n3/2(log n)1/2). This paper presents a near-optimal tradeoff TS = Ω(n2-ε(n)), where ε(n) = O(1/(log n)1/2).",

author = "Yao, \{Andrew Chi Chih\}",

year = "1994",

doi = "10.1137/S0097539788148959",

language = "英语",

volume = "23",

pages = "966--975",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "5",

}

TY - JOUR

T1 - Near-optimal time-space tradeoff for element distinctness

AU - Yao, Andrew Chi Chih

PY - 1994

Y1 - 1994

N2 - It was conjectured in Borodin et al. that to solve the element distinctness problem requires TS = Ω(n2) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS = O((n log n)2) is achievable. Recently, Borodin et al. showed that TS = Ω(n3/2(log n)1/2). This paper presents a near-optimal tradeoff TS = Ω(n2-ε(n)), where ε(n) = O(1/(log n)1/2).

AB - It was conjectured in Borodin et al. that to solve the element distinctness problem requires TS = Ω(n2) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS = O((n log n)2) is achievable. Recently, Borodin et al. showed that TS = Ω(n3/2(log n)1/2). This paper presents a near-optimal tradeoff TS = Ω(n2-ε(n)), where ε(n) = O(1/(log n)1/2).

UR - https://www.scopus.com/pages/publications/0028517979

U2 - 10.1137/S0097539788148959

DO - 10.1137/S0097539788148959

M3 - 文章

AN - SCOPUS:0028517979

SN - 0097-5397

VL - 23

SP - 966

EP - 975

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 5

ER -

Near-optimal time-space tradeoff for element distinctness

摘要

访问文件

其它文件与链接

学术指纹

引用此