سایپرز، باشگاه دانش - ارائه دهنده مقالات ژورنالهای خارجی

اطلاعات و مشخصات مقاله

explorer iconلينك‌ها

[ بازگشت | جستجو | فهرست کلمات کلیدی | فهرست موضوعات | فهرست نویسندگان | فهرست ناشران | فهرست ژورنالها ]

info iconاطلاعات مقاله

[ 189 بار مشاهده چكيده]

عنوان مقاله:تجزیه و تحلیل ریسک ایمنی مبتنی بر بیزی شبکه در پروژه های ساخت و ساز
ناشر: [ Elsevier BV ]
ژورنال
دوره (شماره): (0)
سال انتشار:August 2015
شماره صفحات: 145165145-165
نشانگر دیجیتالی شیء:[ 10.1016/j.ic.2014.12.011 ]
شما اینجا هستید:
  1. Scipers, the Knowledge ClubScipers »
  2. Elsevier BV »
  3. Information And Computation »
  4. Arthur–Merlin streaming complexity

report iconنمايش خلاصه مقاله

Arthur–Merlin Streaming Complexity


مقاله: تجزیه و تحلیل ریسک ایمنی مبتنی بر بیزی شبکه در پروژه های ساخت و ساز

نويسند‌گان:


خلاصه مقاله:


We study the power of Arthur–Merlin probabilistic proof systems in the data stream model. We show a canonical AM 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 AM 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,w such that s⋅w≥n (where O˜ hides a polylog(m,n) factor). We also prove a lower bound, showing that every MA streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w, satisfies 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 MA communication complexity of the Gap Hamming Distance problem, and prove its tightness.


 


كلمات كليدي:

Communication complexity, Data streams , Communication complexity, Data streams, Probabilistic proof systems
پیچیدگی ارتباطات , جریان داده ها , پیچیدگی ارتباطات, اطلاعات و جریان, سیستم های اثبات احتمالاتی


موضوعات:

Theoretical Computer Science, Computational Theory and Mathematics, Information Systems, Computer Science Applications



[ ]

 

دسترسی بین المللی

اگر شما در داخل کشور (ایران) هستید و این صفحه را مشاهده می کنید، نشان می دهد که IP شما به هر دلیلی در لیست IP های ایران ثبت نشده است. برای رفع این مشکل کافی است IP خود را که در پایین این پیام درج شده از طریق آدرس ایمیل support@scipers.com به ما اطلاع دهید. پس از دریافت درخواست، کارشناسان فنی موضوع را بررسی می نمایند و در صورتی که محل اتصال شما از کشور ایران بوده باشد، به لیست استفاده کنندگان مجاز افزوده می شوید.
IP: 3.80.55.37

اطلاعات استنادی

اطلاعات استنادی این مقاله را به نرم افزارهای مدیریت اطلاعات علمی و استنادی ارسال نمایید و در تحقیقات خود از آن استفاده نمایید.

 

به اشتراک گذاری

این صفحه را با استفاده از انواع شبکه های اجتماعی با دوستان خود به اشتراک بگذارید.

برگشت به بالا
رونمایی از اولین و تنها ربات تلگرامی جستجوی مقالات ژورنالی
×