Goldreich, Oded Another motivation for reducing the randomness complexity of algorithms. (English) Zbl 1291.68430 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 555-560 (2011). MSC: 68W20 60-08 94A20 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 555--560 (2011; Zbl 1291.68430) Full Text: DOI
Goldreich, Oded On security preserving reductions – revised terminology. (English) Zbl 1343.94054 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 540-546 (2011). MSC: 94A60 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 540--546 (2011; Zbl 1343.94054) Full Text: DOI
Goldreich, Oded Randomness and computation. (English) Zbl 1343.68181 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 507-539 (2011). MSC: 68Q87 68Q15 68W20 94A60 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 507--539 (2011; Zbl 1343.68181) Full Text: DOI
Goldreich, Oded Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: the state of the art. (English) Zbl 1343.94053 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 406-421 (2011). MSC: 94A60 68Q15 94-02 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 406--421 (2011; Zbl 1343.94053) Full Text: DOI
Goldreich, Oded; Vadhan, Salil On the complexity of computational problems regarding distributions. (English) Zbl 1343.68115 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 390-405 (2011). MSC: 68Q25 62E99 68Q87 94A17 PDFBibTeX XMLCite \textit{O. Goldreich} and \textit{S. Vadhan}, Lect. Notes Comput. Sci. 6650, 390--405 (2011; Zbl 1343.68115) Full Text: DOI
Goldreich, Oded Short locally testable codes and proofs. (English) Zbl 1309.68220 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 333-372 (2011). MSC: 68W20 68P30 68Q25 68Q60 94B60 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 333--372 (2011; Zbl 1309.68220) Full Text: DOI
Goldreich, Oded A sample of samplers: a computational perspective on sampling. (English) Zbl 1343.68297 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 302-332 (2011). MSC: 68W20 05C81 68Q87 94A20 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 302--332 (2011; Zbl 1343.68297) Full Text: DOI
Goldreich, Oded; Nisan, Noam; Wigderson, Avi On Yao’s XOR-lemma. (English) Zbl 1304.68074 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 273-301 (2011). MSC: 68Q25 62E99 68P30 68Q87 94A60 PDFBibTeX XMLCite \textit{O. Goldreich} et al., Lect. Notes Comput. Sci. 6650, 273--301 (2011; Zbl 1304.68074) Full Text: DOI
Goldreich, Oded; Kaufman, Tali Proximity oblivious testing and the role of invariances. (English) Zbl 1343.68301 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 173-190 (2011). MSC: 68W20 05C85 94B60 PDFBibTeX XMLCite \textit{O. Goldreich} and \textit{T. Kaufman}, Lect. Notes Comput. Sci. 6650, 173--190 (2011; Zbl 1343.68301) Full Text: DOI
Goldreich, Oded A candidate counterexample to the easy cylinders conjecture. (English) Zbl 1343.68083 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 136-140 (2011). MSC: 68Q15 94A60 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 136--140 (2011; Zbl 1343.68083) Full Text: DOI
Bellare, Mihir; Goldreich, Oded On probabilistic versus deterministic provers in the definition of proofs of knowledge. (English) Zbl 1343.94042 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 114-123 (2011). MSC: 94A60 PDFBibTeX XMLCite \textit{M. Bellare} and \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 114--123 (2011; Zbl 1343.94042) Full Text: DOI
Goldreich, Oded The GGM construction does NOT yield correlation intractable function ensembles. (English) Zbl 1343.94052 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 98-108 (2011). MSC: 94A60 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 98--108 (2011; Zbl 1343.94052) Full Text: DOI
Goldreich, Oded Candidate one-way functions based on expander graphs. (English) Zbl 1306.94056 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 76-87 (2011). MSC: 94A60 05C75 05C90 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 76--87 (2011; Zbl 1306.94056) Full Text: DOI
Goldreich, Oded Strong proofs of knowledge. (English) Zbl 1343.94051 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 54-58 (2011). MSC: 94A60 68Q25 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 54--58 (2011; Zbl 1343.94051) Full Text: DOI
Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai Collision-free hashing from lattice problems. (English) Zbl 1343.94055 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 30-39 (2011). MSC: 94A60 11H06 PDFBibTeX XMLCite \textit{O. Goldreich} et al., Lect. Notes Comput. Sci. 6650, 30--39 (2011; Zbl 1343.94055) Full Text: DOI Link
Goldreich, Oded; Wigderson, Avi On the circuit complexity of perfect hashing. (English) Zbl 1343.94057 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 26-29 (2011). MSC: 94A60 68R05 PDFBibTeX XMLCite \textit{O. Goldreich} and \textit{A. Wigderson}, Lect. Notes Comput. Sci. 6650, 26--29 (2011; Zbl 1343.94057) Full Text: DOI
Goldreich, Oded; Levin, Leonid A.; Nisan, Noam On constructing 1-1 one-way functions. (English) Zbl 1343.94056 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 13-25 (2011). MSC: 94A60 PDFBibTeX XMLCite \textit{O. Goldreich} et al., Lect. Notes Comput. Sci. 6650, 13--25 (2011; Zbl 1343.94056) Full Text: DOI
Bellare, Mihir; Goldreich, Oded Proving computational ability. (English) Zbl 1343.94041 Goldreich, Oded (ed.), 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. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 6-12 (2011). MSC: 94A60 68Q05 68Q25 PDFBibTeX XMLCite \textit{M. Bellare} and \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 6--12 (2011; Zbl 1343.94041) Full Text: DOI