کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421999 684999 2008 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lower Bounds on the Continuation of Holomorphic Functions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Lower Bounds on the Continuation of Holomorphic Functions
چکیده انگلیسی

We show that continuation of holomorphic functions needs time at least Ω(n2) in the uniform case, which is optimal up to a polylogarithmic factor. In the non-uniform case, i.e. assuming f to be computable in time O(t) on an open subset of its domain, we show, that continuation of f cannot be robustly done in time o(n⋅t(n)). This again is optimal up to a polylogarithmic factor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 221, 25 December 2008, Pages 207-217