کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437241 690093 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On derandomization and average-case complexity of monotone functions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On derandomization and average-case complexity of monotone functions
چکیده انگلیسی

We investigate whether circuit lower bounds for monotone circuits can be used to derandomize randomized monotone circuits. We show that, in fact, any derandomization of randomized monotone computations would derandomize all randomized computations, whether monotone or not. We prove similar results in the settings of pseudorandom generators and average-case hard functions — that a pseudorandom generator secure against monotone circuits is also secure with somewhat weaker parameters against general circuits, and that an average-case hard function for monotone circuits is also hard with somewhat weaker parameters for general circuits.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 434, 25 May 2012, Pages 35-44