Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/13153Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Karakostas, G. | en |
| dc.contributor.author | Kinne, J. | en |
| dc.contributor.author | van Melkebeek, D. | en |
| dc.date.accessioned | 2015-11-24T17:26:08Z | - |
| dc.date.available | 2015-11-24T17:26:08Z | - |
| dc.identifier.issn | 0304-3975 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/13153 | - |
| dc.rights | Default Licence | - |
| dc.subject | derandomization | en |
| dc.subject | monotone circuits | en |
| dc.subject | monotone functions | en |
| dc.subject | randomized algorithm | en |
| dc.subject | pseudorandom generators | en |
| dc.subject | average-case complexity | en |
| dc.subject | boolean functions | en |
| dc.subject | hardness | en |
| dc.subject | bounds | en |
| dc.title | On derandomization and average-case complexity of monotone functions | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | DOI 10.1016/j.tcs.2012.02.017 | - |
| heal.identifier.secondary | <Go to ISI>://000303903700004 | - |
| heal.identifier.secondary | http://ac.els-cdn.com/S0304397512001582/1-s2.0-S0304397512001582-main.pdf?_tid=56fa8ab4-873f-11e3-a7e0-00000aab0f6c&acdnat=1390819366_c3b9245363ffcfd6d4e10adede0eefff | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2012 | - |
| heal.abstract | 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. | en |
| heal.journalName | Theoretical Computer Science | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Karakostas-2012-On derandomization a.pdf | 246.4 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
