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. (English) Zbl 1220.68005

Lecture Notes in Computer Science 6650. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). xi, 563 p. (2011).

Show indexed articles as search result.

The articles of this volume will be reviewed individually.
Indexed articles:
Goldreich, Oded, Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard, 1-5 [Zbl 1343.68093]
Bellare, Mihir; Goldreich, Oded, Proving computational ability, 6-12 [Zbl 1343.94041]
Goldreich, Oded; Levin, Leonid A.; Nisan, Noam, On constructing 1-1 one-way functions, 13-25 [Zbl 1343.94056]
Goldreich, Oded; Wigderson, Avi, On the circuit complexity of perfect hashing, 26-29 [Zbl 1343.94057]
Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai, Collision-free hashing from lattice problems, 30-39 [Zbl 1343.94055]
Goldreich, Oded; Zuckerman, David, Another proof that \(\mathcal{BPP}\subseteq \mathcal{PH}\) (and more), 40-53 [Zbl 1343.68085]
Goldreich, Oded, Strong proofs of knowledge, 54-58 [Zbl 1343.94051]
Goldreich, Oded; Vadhan, Salil; Wigderson, Avi, Simplified derandomization of BPP using a hitting set generator, 59-67 [Zbl 1343.68303]
Goldreich, Oded; Ron, Dana, On testing expansion in bounded-degree graphs, 68-75 [Zbl 1343.68302]
Goldreich, Oded, Candidate one-way functions based on expander graphs, 76-87 [Zbl 1306.94056]
Goldreich, Oded, Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs, 88-97 [Zbl 1343.68094]
Goldreich, Oded, The GGM construction does NOT yield correlation intractable function ensembles, 98-108 [Zbl 1343.94052]
Goldreich, Oded; Sudan, Madhu; Trevisan, Luca, From logarithmic advice to single-bit advice, 109-113 [Zbl 1343.68080]
Bellare, Mihir; Goldreich, Oded, On probabilistic versus deterministic provers in the definition of proofs of knowledge, 114-123 [Zbl 1343.94042]
Goldreich, Oded, On the average-case complexity of property testing, 124-135 [Zbl 1343.68296]
Goldreich, Oded, A candidate counterexample to the easy cylinders conjecture, 136-140 [Zbl 1343.68083]
Brakerski, Zvika; Goldreich, Oded, From absolute distinguishability to positive distinguishability, 141-155 [Zbl 1343.68290]
Avigad, Lidor; Goldreich, Oded, Testing graph blow-up, 156-172 [Zbl 1343.68286]
Goldreich, Oded; Kaufman, Tali, Proximity oblivious testing and the role of invariances, 173-190 [Zbl 1343.68301]
Goldreich, Oded, In a world of \(\mathrm{P}=\mathrm{BPP}\), 191-232 [Zbl 1343.68084]
Goldreich, Oded, Notes on Levin’s theory of average-case complexity, 233-247 [Zbl 1343.68111]
Goldreich, Oded, Three XOR-lemmas – an exposition, 248-272 [Zbl 1343.68112]
Goldreich, Oded; Nisan, Noam; Wigderson, Avi, On Yao’s XOR-lemma, 273-301 [Zbl 1304.68074]
Goldreich, Oded, A sample of samplers: a computational perspective on sampling, 302-332 [Zbl 1343.68297]
Goldreich, Oded, Short locally testable codes and proofs, 333-372 [Zbl 1309.68220]
Goldreich, Oded, Bravely, moderately: a common theme in four recent works, 373-389 [Zbl 1343.68113]
Goldreich, Oded; Vadhan, Salil, On the complexity of computational problems regarding distributions, 390-405 [Zbl 1343.68115]
Goldreich, Oded, Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: the state of the art, 406-421 [Zbl 1343.94053]
Goldreich, Oded, Average case complexity, revisited, 422-450 [Zbl 1343.68114]
Goldreich, Oded, Basic facts about expander graphs, 451-464 [Zbl 1343.68182]
Goldreich, Oded, A brief introduction to property testing, 465-469 [Zbl 1343.68298]
Goldreich, Oded, Introduction to testing graph properties, 470-506 [Zbl 1343.68299]
Goldreich, Oded, Randomness and computation, 507-539 [Zbl 1343.68181]
Goldreich, Oded, On security preserving reductions – revised terminology, 540-546 [Zbl 1343.94054]
Goldreich, Oded, Contemplations on testing graph properties, 547-554 [Zbl 1291.05195]
Goldreich, Oded, Another motivation for reducing the randomness complexity of algorithms, 555-560 [Zbl 1291.68430]


68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Q25 Analysis of algorithms and problem complexity
00B15 Collections of articles of miscellaneous specific interest
Full Text: DOI