On derandomization and average-case complexity of monotone functions
Φόρτωση...
Ημερομηνία
Συγγραφείς
Karakostas, G.
Kinne, J.
van Melkebeek, D.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Theoretical Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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. (C) 2012 Elsevier B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
derandomization, monotone circuits, monotone functions, randomized algorithm, pseudorandom generators, average-case complexity, boolean functions, hardness, bounds
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000303903700004
http://ac.els-cdn.com/S0304397512001582/1-s2.0-S0304397512001582-main.pdf?_tid=56fa8ab4-873f-11e3-a7e0-00000aab0f6c&acdnat=1390819366_c3b9245363ffcfd6d4e10adede0eefff
http://ac.els-cdn.com/S0304397512001582/1-s2.0-S0304397512001582-main.pdf?_tid=56fa8ab4-873f-11e3-a7e0-00000aab0f6c&acdnat=1390819366_c3b9245363ffcfd6d4e10adede0eefff
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών