Article

Randomness vs. Time: De-Randomization under a Uniform Assumption

Authors:

R. Impagliazzo,

A. WigdersonAuthors Info & Claims

FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science

Page 734

Published: 08 November 1998 Publication History

Publisher Site

Abstract

No abstract available.

Cited By

View all

Impagliazzo RKabanets VVolkovich IServedio R(2018)The power of natural properties as oraclesProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235593(1-20)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235593
Tell RDiakonikolas IKempe DHenzinger M(2018)Quantified derandomization of linear threshold circuitsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188822(855-865)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188822
Hoza WUmans CHatami HMcKenzie PKing V(2017)Targeted pseudorandom generators, simulation advice generators, and derandomizing logspaceProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055414(629-640)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055414
Show More Cited By

Recommendations

Randomness vs. Time in Anonymous Networks
DISC 2015: Proceedings of the 29th International Symposium on Distributed Computing - Volume 9363

In an anonymous network, symmetry breaking tasks can only be solved if randomization is available. But how many random bits are required to solve any such task? As it turns out, the answer to this question depends on the desired runtime of the ...
Hardness vs randomness

We present a simple new construction of a pseudorandom bit generator. It stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C (e.g., P, NC, PSPACE, ...) using an arbitrary function ...
Hardness vs. randomness
SFCS '88: Proceedings of the 29th Annual Symposium on Foundations of Computer Science

A simple construction for a pseudorandom bit generator is presented. It stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C (e.g. P, NC, PSPACE, etc.), using an arbitrary function ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science

November 1998

ISBN:0818691727

Publisher

IEEE Computer Society

United States

Publication History

Published: 08 November 1998

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Impagliazzo RKabanets VVolkovich IServedio R(2018)The power of natural properties as oraclesProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235593(1-20)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235593
Tell RDiakonikolas IKempe DHenzinger M(2018)Quantified derandomization of linear threshold circuitsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188822(855-865)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188822
Hoza WUmans CHatami HMcKenzie PKing V(2017)Targeted pseudorandom generators, simulation advice generators, and derandomizing logspaceProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055414(629-640)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055414
Applebaum BArtemenko SShaltiel RYang GZuckerman D(2015)Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract)Proceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833256(582-600)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833256
Goldreich OGoldwasser SRon DKleinberg R(2013)On the possibilities and limitations of pseudodeterministic algorithmsProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422453(127-138)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422453
Jansen MSanthanam RGoldwasser S(2012)Marginal hitting sets imply super-polynomial lower bounds for permanentProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090275(496-506)Online publication date: 8-Jan-2012
https://dl.acm.org/doi/10.1145/2090236.2090275
Artemenko SShaltiel R(2011)Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplificationProceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques10.5555/2033252.2033286(377-388)Online publication date: 17-Aug-2011
https://dl.acm.org/doi/10.5555/2033252.2033286
Glaßer CHitchcock JPavan ATravers S(2011)Unions of disjoint NP-complete setsProceedings of the 17th annual international conference on Computing and combinatorics10.5555/2033094.2033116(240-251)Online publication date: 14-Aug-2011
https://dl.acm.org/doi/10.5555/2033094.2033116
Shaltiel RUmans CJohnson DFeige U(2007)Low-end uniform hardness vs. randomness tradeoffs for AMProceedings of the thirty-ninth annual ACM symposium on Theory of computing10.1145/1250790.1250854(430-439)Online publication date: 11-Jun-2007
https://dl.acm.org/doi/10.1145/1250790.1250854
Gutfreund DShaltiel RTa-Shma A(2007)If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard InstancesComputational Complexity10.1007/s00037-007-0235-816:4(412-441)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1007/s00037-007-0235-8
Show More Cited By

Abstract

Cited By

Recommendations

Randomness vs. Time in Anonymous Networks

Hardness vs randomness

Hardness vs. randomness

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations