No label defined (Q3304157)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	No label defined	scientific article

Statements

scholarly article

0 references

0 references

publication date

5 August 2020

0 references

zbMATH Keywords

approximate counting

0 references

lower bounds

0 references

derandomization

0 references

parallel algorithms

0 references

query complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman

0 references

On derandomizing algorithms that err extremely rarely

0 references

In search of an easy witness: Exponential time vs. probabilistic polynomial time.

0 references

Derandomizing polynomial identity tests means proving circuit lower bounds

0 references

The complexity of parallel search

0 references

The probabilistic method yields deterministic parallel algorithms

0 references

0 references

Pseudorandomness and average-case complexity via uniform reductions

0 references

The complexity of constructing pseudorandom generators from hard functions

0 references

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

0 references

Identifiers

zbMATH Open document ID

0 references

10.4230/LIPIcs.STACS.2018.58

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3304157

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q3304157&oldid=36605239"