کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426451 686077 2015 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Arthur–Merlin streaming complexity
ترجمه فارسی عنوان
پیچیدگی جریان Arthur–Merlin
کلمات کلیدی
سیستم های اثبات احتمالی؛ جریان داده ها؛ پیچیدگی ارتباطی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We study the power of Arthur–Merlin probabilistic proof systems in the data stream model. We show a canonical AMAM streaming algorithm for a class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.As an application, we give an AMAM streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n  , the algorithm uses O˜(s) space and a proof of size O˜(w), for every s,ws,w such that s⋅w≥ns⋅w≥n (where O˜ hides a polylog(m,n)polylog(m,n) factor). We also prove a lower bound, showing that every MAMA streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w  , satisfies s⋅w=Ω(n)s⋅w=Ω(n). Furthermore, the lower bound also holds for approximating the number of distinct elements within a multiplicative factor of 1±1/n.As a part of the proof of the lower bound for the Distinct Elements   problem, we show a new lower bound of Ω(n) on the MAMA communication complexity of the Gap Hamming Distance problem, and prove its tightness.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 243, August 2015, Pages 145–165
نویسندگان
, ,