Edit Profile (opens in new tab) Goldreich, Oded Co-Author Distance Author ID: goldreich.oded Published as: Goldreich, Oded; Goldreich, O. Homepage: http://www.wisdom.weizmann.ac.il/~/oded/ External Links: MGP · ORCID · Wikidata · Google Scholar · ResearchGate · dblp · GND · IdRef Documents Indexed: 264 Publications since 1981, including 9 Books 14 Contributions as Editor · 2 Further Contributions Biographic References: 1 Publication Co-Authors: 119 Co-Authors with 196 Joint Publications 3,734 Co-Co-Authors all top 5 Co-Authors 83 single-authored 30 Ron, Dana 21 Goldwasser, Shafi 21 Sudan, Madhu 18 Wigderson, Avi 15 Vadhan, Salil P. 11 Bellare, Mihir 10 Chor, Benny 8 Canetti, Ran 8 Micali, Silvio 7 Even, Shimon 7 Gur, Tom 7 Halevi, Shai 7 Krawczyk, Hugo 5 Håstad, Johan Torkel 5 Petrank, Erez 4 Bürgisser, Peter 4 Kushilevitz, Eyal 4 Nisan, Noam 4 Sahai, Amit 4 Trevisan, Luca 3 Alon, Noga 3 Avigad, Lidor 3 Barak, Boaz 3 Ben-Sasson, Eli 3 Kaufman, Tali 3 Krivelevich, Michael 3 Luby, Michael G. 3 Meir, Or 3 Newman, Ilan I. 3 Ostrovsky, Rafail 3 Rosen, Alon 3 Rothblum, Guy N. 3 Rothblum, Ron D. 3 Rozenberg, Eyal 3 Tal, Avishay 3 Vainish, Ronen 3 von zur Gathen, Joachim 2 Akavia, Adi 2 Awerbuch, Baruch 2 Bar-Yehuda, Reuven 2 Ben-Or, Michael 2 Brakerski, Zvika 2 Decatur, Scott E. 2 Dinur, Irit 2 Even, Guy 2 Freeman, David Mandell 2 Harsha, Prahladh 2 Impagliazzo, Russell 2 Itai, Alon 2 Kiltz, Eike 2 Komargodski, Ilan 2 Lehman, Eric 2 Levin, Leonid A. 2 Lindell, Yehuda 2 Moshkovitz, Dana 2 Peleg, David 2 Peralta, René C. 2 Rubinfeld, Ronitt 2 Rudich, Steven 2 Safra, Muli 2 Samorodnitsky, Alex 2 Schnorr, Claus Peter 2 Segev, Gil 2 Sheffet, Or 2 Shinkar, Igor 2 Shrira, Liuba 2 Yang, Ke 2 Zuckerman, David 1 Alexi, Werner 1 Ball, Marshall 1 Barhum, Kfir 1 Ben-David, Shai 1 Benjamini, Itai 1 Blum, Manuel 1 Chang, Richard 1 Czumaj, Artur 1 Damgård, Ivan Bjerre 1 De Santis, Alfredo 1 Di Crescenzo, Giovanni 1 Dodis, Yevgeniy 1 Feige, Uriel 1 Hartmanis, Juris 1 Izsak, Rani 1 Juba, Brendan 1 Kahan, Ariel 1 Karloff, Howard J. 1 Kilian, Joe 1 Lempel, Abraham 1 Leshkowitz, Maya 1 Linial, Nathan 1 Luby, Michel 1 Malkin, Tal G. 1 Mansour, Yishay 1 Meyer, Bernd E. 1 Micciancio, Daniele 1 Moran, Shlomo 1 Naor, Moni 1 Nussboim, Asaf 1 Okamoto, Tatsuaki 1 Oren, Yair ...and 19 more Co-Authors all top 5 Serials 14 SIAM Journal on Computing 14 Computational Complexity 12 Journal of Cryptology 9 Information Processing Letters 9 Random Structures & Algorithms 8 Journal of the ACM 6 Oberwolfach Reports 5 Journal of Computer and System Sciences 4 ACM Transactions on Computation Theory 3 Distributed Computing 3 Lecture Notes in Computer Science 3 Foundations and Trends in Theoretical Computer Science 2 IEEE Transactions on Information Theory 2 Journal of the Association for Computing Machinery 2 Theoretical Computer Science 2 Combinatorica 2 Algorithmica 2 Information and Computation 1 Acta Informatica 1 Discrete Mathematics 1 Israel Journal of Mathematics 1 Networks 1 Journal of Algorithms 1 Journal of Complexity 1 SIAM Journal on Discrete Mathematics 1 Notices of the American Mathematical Society 1 Chicago Journal of Theoretical Computer Science 1 Algorithms and Combinatorics 1 University Lecture Series 1 Theory of Computing 1 ACM Books 1 Information Security and Cryptography all top 5 Fields 244 Computer science (68-XX) 112 Information and communication theory, circuits (94-XX) 31 Combinatorics (05-XX) 14 General and overarching topics; collections (00-XX) 14 Mathematical logic and foundations (03-XX) 12 Numerical analysis (65-XX) 9 Number theory (11-XX) 7 Probability theory and stochastic processes (60-XX) 4 Statistics (62-XX) 3 Group theory and generalizations (20-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 1 History and biography (01-XX) 1 Quantum theory (81-XX) 1 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 236 Publications have been cited 5,742 times in 3,437 Documents Cited by ▼ Year ▼ Foundations of cryptography. Vol. 1. Basic tools. Zbl 1007.94016 Goldreich, Oded 303 2001 Foundations of cryptography. Vol. 2. Basic applications. Zbl 1068.94011 Goldreich, Oded 277 2004 Property testing and its connection to learning and approximation. Zbl 1065.68575 Goldreich, Oded; Goldwasser, Shafi; Ron, Dana 255 1998 How to construct random functions. Zbl 0596.65002 Goldreich, O.; Goldwasser, S.; Micali, S. 252 1986 On the (im)possibility of obfuscating programs (extended abstract). Zbl 1001.68511 Barak, Boaz; Goldreich, Oded; Impagliazzo, Rusell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke 193 2001 Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Zbl 0799.68101 Goldreich, Oded; Micali, Silvio; Wigderson, Avi 187 1991 The random oracle methodology, revisited. Zbl 1204.94063 Canetti, Ran; Goldreich, Oded; Halevi, Shai 143 2004 Computational complexity. A conceptual perspective. Zbl 1154.68056 Goldreich, Oded 119 2008 Simple constructions of almost \(k\)-wise independent random variables. Zbl 0755.60002 Alon, Noga; Goldreich, Oded; Håstad, Johan; Peralta, René 118 1992 Software protection and simulation on oblivious RAMs. Zbl 0885.68041 Goldreich, Oded; Ostrovsky, Rafail 113 1996 The random oracle methodology, revisited. Zbl 1027.68603 Canetti, Ran; Goldreich, Oded; Halevi, Shai 112 1998 Unbiased bits from sources of weak randomness and probabilistic communication complexity. Zbl 0644.94008 Chor, Benny; Goldreich, Oded 111 1988 On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Zbl 0752.68009 Bar-Yehuda, Reuven; Goldreich, Oded; Itai, Alon 110 1992 On the (im)possibility of obfuscating programs. Zbl 1281.68118 Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke 105 2012 A randomized protocol for signing contracts. Zbl 0538.94011 Even, S.; Goldreich, O.; Lempel, A. 98 1983 Definitions and properties of zero-knowledge proof systems. Zbl 0791.94010 Goldreich, Oded; Oren, Yair 94 1994 Free bits, PCPs, and nonapproximability – towards tight results. Zbl 0912.68041 Bellare, Mihir; Goldreich, Oded; Sudan, Madhu 91 1998 On defining proofs of knowledge. Zbl 0823.94016 Bellare, Mihir; Goldreich, Oded 85 1993 Private information retrieval. Zbl 1065.68524 Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu 85 1998 Property testing in bounded degree graphs. Zbl 0990.68103 Goldreich, O.; Ron, D. 84 2002 Robust PCPs of proximity, shorter PCPs, and applications to coding. Zbl 1118.68071 Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil 80 2006 How to construct constant-round zero-knowledge proof systems for NP. Zbl 0855.68085 Goldreich, Oded; Kahan, Ariel 77 1996 Private information retrieval. Zbl 0938.68625 Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu 75 1995 Introduction to property testing. Zbl 06797790 Goldreich, Oded 75 2017 Adaptively secure multi-party computation. Zbl 0922.68048 Canetti, Ran; Feige, Uri; Goldreich, Oded; Naor, Moni 72 1996 On the composition of zero-knowledge proof systems. Zbl 0841.68112 Goldreich, Oded; Krawczyk, Hugo 66 1996 Public-key cryptosystems from lattice reduction problems. Zbl 0889.94011 Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai 60 1997 How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design. Zbl 0636.94010 Goldreich, Oded; Micali, Silvio; Wigderson, Avi 55 1987 Testing monotonicity. Zbl 0964.68148 Goldreich, Oded; Goldwasser, Shafi; Lehman, Eric; Ron, Dana; Samorodnitsky, Alex 53 2000 Foundations of cryptography. II: Basic applications. Reprint of the 2004 hardback ed. Zbl 1179.94063 Goldreich, Oded 52 2009 On-line/off-line digital signatures. Zbl 0844.94011 Even, Shimon; Goldreich, Oded; Micali, Silvio 48 1996 A theory of goal-oriented communication. Zbl 1281.94004 Goldreich, Oded; Juba, Brendan; Sudan, Madhu 48 2012 On testing expansion in bounded-degree graphs. Zbl 1343.68302 Goldreich, Oded; Ron, Dana 47 2011 Candidate one-way functions based on expander graphs. Zbl 1306.94056 Goldreich, Oded 47 2011 Resettable zero-knowledge (extended abstract). Zbl 1296.94093 Canetti, Ran; Goldreich, Oded; Goldwasser, Shafi; Micali, Silvio 47 2000 Locally testable codes and PCPs of almost-linear length. Zbl 1315.94144 Goldreich, Oded; Sudan, Madhu 46 2006 Three theorems regarding testing graph properties. Zbl 1048.68062 Goldreich, Oded; Trevisan, Luca 46 2003 Universal arguments and their applications. Zbl 1180.94047 Barak, Boaz; Goldreich, Oded 44 2008 A sublinear bipartiteness tester for bounded degree graphs. Zbl 0932.68053 Goldreich, Oded; Ron, Dana 41 1999 On the power of two-point based sampling. Zbl 0672.60105 Chor, Benny; Goldreich, Oded 37 1989 Improved testing algorithms for monotonicity. Zbl 0949.68178 Dodis, Yevgeniy; Goldreich, Oded; Lehman, Eric; Raskhodnikova, Sofya; Ron, Dana; Samorodnitsky, Alex 37 1999 Everything provable is provable in zero-knowledge. Zbl 0718.68033 Ben-Or, Michael; Goldreich, Oded; Goldwasser, Shafi; Håstad, Johan; Kilian, Joe; Micali, Silvio; Rogaway, Phillip 37 1990 On the cryptographic applications of random functions (extended abstract). Zbl 1359.94599 Goldreich, Oded; Goldwasser, Shafi; Micali, Silvio 36 1985 On Yao’s XOR-lemma. Zbl 1304.68074 Goldreich, Oded; Nisan, Noam; Wigderson, Avi 34 2011 RSA and Rabin functions: Certain parts are as hard as the whole. Zbl 0644.94011 Alexi, Werner; Chor, Benny; Goldreich, Oded; Schnorr, Claus P. 33 1988 Approximating average parameters of graphs. Zbl 1155.05057 Goldreich, Oded; Ron, Dana 32 2008 On the theory of average case complexity. Zbl 0762.68027 Ben-David, Shai; Chor, Benny; Goldreich, Oded; Luby, Michel 30 1992 A trade-off between information and communication in broadcast protocols. Zbl 0696.68020 Awerbuch, Baruch; Goldreich, Oded; Peleg, David; Vainish, Ronen 28 1990 Asynchronous secure computation. Zbl 1310.68044 Ben-Or, Michael; Canetti, Ran; Goldreich, Oded 28 1993 The minimum-length generator sequence problem is NP-hard. Zbl 0467.68046 Even, S.; Goldreich, O. 26 1981 Collision-free hashing from lattice problems. Zbl 1343.94055 Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai 25 2011 Modern cryptography, probabilistic proofs and pseudo-randomness. Zbl 0907.94002 Goldreich, Oded 25 1999 Property testing. Current research and surveys. Zbl 1197.68012 25 2010 On interactive proofs with a laconic prover. Zbl 1053.68045 Goldreich, Oded; Vadhan, Salil; Wigderson, Avi 24 2002 On the existence of pseudorandom generators. Zbl 0795.94011 Goldreich, Oded; Krawczyk, Hugo; Luby, Michael 24 1993 More constructions of lossy and correlation-secure trapdoor functions. Zbl 1281.94024 Freeman, David Mandell; Goldreich, Oded; Kiltz, Eike; Rosen, Alon; Segev, Gil 23 2010 Incremental cryptography: The case of hashing and signing. Zbl 0939.94530 Bellare, Mihir; Goldreich, Oded; Goldwasser, Shafi 23 1994 Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. Zbl 1027.68695 Goldreich, Oded; Sahai, Amit; Vadhan, Salil 23 1998 A sample of samplers: a computational perspective on sampling. Zbl 1343.68297 Goldreich, Oded 22 2011 Free bits, PCPs and non-approximability – towards tight results. Zbl 0938.68820 Bellare, Mihir; Goldreich, Oded; Sudan, Madhu 22 1995 Can statistical zero knowledge be made non-interactive? or On the relationship of \({\mathcal {SZK}}\) and \({\mathcal {NISZK}}\). (Extended abstract). Zbl 0942.68046 Goldreich, Oded; Sahai, Amit; Vadhan, Salil 21 1999 On the limits of nonapproximability of lattice problems. Zbl 0961.68122 Goldreich, Oded; Goldwasser, Shafi 21 2000 Foundations of cryptography – a primer. Print version of Foundations and Trends in Theoretical Computer Science Vol. 1, No. 1 (2005). Zbl 1141.94009 Goldreich, Oded 21 2005 Two remarks concerning the Goldwasser-Micali-Rivest signature scheme. Zbl 0635.94010 Goldreich, Oded 20 1987 How to solve any protocol problem - An efficiency improvement. Zbl 0644.68077 Goldreich, Oded; Vainish, Ronen 20 1988 On proximity-oblivious testing. Zbl 1223.68045 Goldreich, Oded; Ron, Dana 20 2011 On the complexity of interactive proofs with bounded communication. Zbl 1338.68104 Goldreich, Oded; Håstad, Johan 20 1998 Efficient approximation of product distributions. Zbl 0959.68553 Even, Guy; Goldreich, Oded; Luby, Michael; Nisan, Noam; Veličković, Boban 19 1998 A uniform-complexity treatment of encryption and zero-knowledge. Zbl 0795.68069 Goldreich, Oded 19 1993 On basing one-way functions on NP-hardness. Zbl 1302.68132 Akavia, Adi; Goldreich, Oded; Goldwasser, Shafi; Moshkovitz, Dana 19 2006 Enhancements of trapdoor permutations. Zbl 1372.94427 Goldreich, Oded; Rothblum, Ron D. 19 2013 Lower bounds for linear locally decodable codes and private information retrieval. Zbl 1113.68049 Goldreich, Oded; Karloff, Howard; Schulman, Leonard J.; Trevisan, Luca 18 2006 Incremental cryptography and application to virus protection. Zbl 0916.94005 Bellare, Mihir; Goldreich, Oded; Goldwasser, Shafi 18 1995 Lower bounds for sampling algorithms for estimating the average. Zbl 0875.68529 Canetti, Ran; Even, Guy; Goldreich, Oded 18 1995 Chinese remaindering with errors. Zbl 1007.94026 Goldreich, Oded; Ron, Dana; Sudan, Madhu 17 2000 Combinatorial property testing (a survey). Zbl 0912.68071 Goldreich, Oded 17 1999 Learning polynomials with queries: The highly noisy case. Zbl 0968.68063 Goldreich, Oded; Rubinfeld, Ronitt; Sudan, Madhu 16 2000 On the limits of non-approximability of lattice problems. Zbl 1011.68512 Goldreich, Oded; Goldwasser, Shafi 16 1998 DES-like functions can generate the alternating group. Zbl 0537.94011 Even, Shimon; Goldreich, Oded 15 1983 Tiny families of functions with random properties: A quality-size trade-off for hashing. Zbl 0891.60010 Goldreich, Oded; Wigderson, Avi 15 1997 Property testing in bounded degree graphs. Zbl 0963.68154 Goldreich, Oded; Ron, Dana 15 1999 Randomness in interactive proofs. Zbl 0802.68053 Bellare, Mihir; Goldreich, Oded; Goldwasser, Shafi 15 1993 Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Zbl 0999.68085 Goldreich, O.; Micciancio, D.; Safra, S.; Seifert, J.-P. 15 1999 Uniform generation of NP-witnesses using an NP-oracle. Zbl 1006.68050 Bellare, Mihir; Goldreich, Oded; Petrank, Erez 15 2000 More constructions of lossy and correlation-secure trapdoor functions. Zbl 1291.94083 Freeman, David Mandell; Goldreich, Oded; Kiltz, Eike; Rosen, Alon; Segev, Gil 14 2013 Three XOR-lemmas – an exposition. Zbl 1343.68112 Goldreich, Oded 13 2011 Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection. Zbl 0726.94018 Bar-Yehuda, Reuven; Goldreich, Oded; Itai, Alon 13 1991 Eliminating decryption errors in the Ajtai-Dwork cryptosystem. Zbl 0889.94010 Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai 13 1997 The random oracle hypothesis is false. Zbl 0813.68100 Chang, Richard; Chor, Benny; Goldreich, Oded; Hartmanis, Juris; Håstad, Johan; Ranjan, Desh; Rohatgi, Pankaj 13 1994 Strong locally testable codes with relaxed local decoders. Zbl 1378.94083 Goldreich, Oded; Gur, Tom; Komargodski, Ilan 13 2015 Session-key generation using human passwords only. Zbl 1003.94527 Goldreich, Oded; Lindell, Yehuda 13 2001 Almost \(k\)-wise independence versus \(k\)-wise independence. Zbl 1178.68251 Alon, Noga; Goldreich, Oded; Mansour, Yishay 12 2003 On testing computability by small width OBDDs. Zbl 1305.68330 Goldreich, Oded 12 2010 Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard. Zbl 1343.68093 Goldreich, Oded 11 2011 On the NP-completeness of certain network testing problems. Zbl 0532.94017 Even, S.; Goldreich, O.; Moran, S.; Tong, P. 11 1984 On the implementation of huge random objects. Zbl 1225.68132 Goldreich, Oded; Goldwasser, Shafi; Nussboim, Asaf 11 2010 On the composition of zero-knowledge proof systems. Zbl 0766.68033 Goldreich, Oded; Krawczyk, Hugo 10 1990 Short locally testable codes and proofs. Zbl 1309.68220 Goldreich, Oded 10 2011 Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: the state of the art. Zbl 1343.94053 Goldreich, Oded 10 2011 Computational sample complexity. Zbl 0941.68108 Decatur, Scott E.; Goldreich, Oded; Ron, Dana 10 2000 Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Zbl 1512.94128 Goldreich, Oded; Gur, Tom 2 2021 Robustly self-ordered graphs: constructions and applications to property testing. Zbl 07711594 Goldreich, Oded; Wigderson, Avi 1 2021 The uniform distribution is complete with respect to testing identity to a fixed distribution. Zbl 07578387 Goldreich, Oded 4 2020 On (Valiant’s) polynomial-size monotone formula for majority. Zbl 07578380 Goldreich, Oded 3 2020 Super-perfect zero-knowledge proofs. Zbl 07578385 Goldreich, Oded; Teichner, Liav 2 2020 Worst-case to average-case reductions for subclasses of P. Zbl 07578392 Goldreich, Oded; Rothblum, Guy N. 2 2020 Two comments on targeted canonical derandomizers. Zbl 07578381 Goldreich, Oded 1 2020 On the communication complexity methodology for proving lower bounds on the query complexity of property testing. Zbl 07578384 Goldreich, Oded 1 2020 On the relation between the relative earth mover distance and the variation distance (an exposition). Zbl 07578386 Goldreich, Oded; Ron, Dana 1 2020 Reducing testing affine spaces to testing linearity of functions. Zbl 07578390 Goldreich, Oded 1 2020 Deconstructing 1-local expanders. Zbl 07578391 Goldreich, Oded 1 2020 On the optimal analysis of the collision probability tester (an exposition). Zbl 07578393 Goldreich, Oded 1 2020 Constant-round interactive proof systems for AC0[2] and NC1. Zbl 07578395 Goldreich, Oded; Rothblum, Guy N. 1 2020 Providing sound foundations for cryptography. On the work of Shafi Goldwasser and Silvio Micali. Zbl 1460.94002 7 2019 Testing graphs in vertex-distribution-free models. Zbl 1433.68295 Goldreich, Oded 2 2019 Strong locally testable codes with relaxed local decoders. Zbl 1495.94159 Goldreich, Oded; Gur, Tom; Komargodski, Ilan 1 2019 Hierarchy theorems for testing properties in size-oblivious query complexity. Zbl 1494.68091 Goldreich, Oded 1 2019 Every set in \(\mathcal{P}\) is strongly testable under a suitable encoding. Zbl 07559073 Dinur, Irit; Goldreich, Oded; Gur, Tom 1 2019 Universal locally testable codes. Zbl 1426.94159 Goldreich, Oded; Gur, Tom 7 2018 Simple doubly-efficient interactive proof systems for locally-characterizable sets. Zbl 1462.68048 Goldreich, Oded; Rothblum, Guy N. 5 2018 Matrix rigidity of random Toeplitz matrices. Zbl 1398.68237 Goldreich, Oded; Tal, Avishay 2 2018 On doubly-efficient interactive proof systems. Zbl 1394.68179 Goldreich, Oded 1 2018 Introduction to property testing. Zbl 06797790 Goldreich, Oded 75 2017 On learning and testing dynamic environments. Zbl 1426.68297 Goldreich, Oded; Ron, Dana 1 2017 On sample-based testers. Zbl 1427.68360 Goldreich, Oded; Ron, Dana 7 2016 Matrix rigidity of random Toeplitz matrices. Zbl 1373.68271 Goldreich, Oded; Tal, Avishay 3 2016 Two-sided error proximity oblivious testing. Zbl 1352.68285 Goldreich, Oded; Shinkar, Igor 3 2016 Strong locally testable codes with relaxed local decoders. Zbl 1378.94083 Goldreich, Oded; Gur, Tom; Komargodski, Ilan 13 2015 Proofs of proximity for context-free languages and read-once branching programs. Zbl 1395.68168 Goldreich, Oded; Gur, Tom; Rothblum, Ron D. 9 2015 On sample-based testers (extended abstract). Zbl 1364.68361 Goldreich, Oded; Ron, Dana 5 2015 On randomness extraction in \({\mathcal{AC}}^0\). Zbl 1388.68074 Goldreich, Oded; Viola, Emanuele; Wigderson, Avi 2 2015 Complexity theory. Abstracts from the workshop held November 15–21, 2015. Zbl 1380.00044 1 2015 Finding cycles and trees in sublinear time. Zbl 1307.05210 Czumaj, Artur; Goldreich, Oded; Ron, Dana; Seshadhri, C.; Shapira, Asaf; Sohler, Christian 10 2014 On derandomizing algorithms that err extremely rarely. Zbl 1315.68152 Goldreich, Oded; Widgerson, Avi 8 2014 On multiple input problems in property testing. Zbl 1359.68085 Goldreich, Oded 2 2014 Enhancements of trapdoor permutations. Zbl 1372.94427 Goldreich, Oded; Rothblum, Ron D. 19 2013 More constructions of lossy and correlation-secure trapdoor functions. Zbl 1291.94083 Freeman, David Mandell; Goldreich, Oded; Kiltz, Eike; Rosen, Alon; Segev, Gil 14 2013 On the possibilities and limitations of pseudodeterministic algorithms (extended abstract). Zbl 1361.68089 Goldreich, Oded; Goldwasser, Shafi; Ron, Dana 4 2013 On the (im)possibility of obfuscating programs. Zbl 1281.68118 Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke 105 2012 A theory of goal-oriented communication. Zbl 1281.94004 Goldreich, Oded; Juba, Brendan; Sudan, Madhu 48 2012 The tensor product of two good codes is not necessarily robustly testable. Zbl 1243.94046 Goldreich, Oded; Meir, Or 8 2012 Monotone circuits: one-way functions versus pseudorandom generators. Zbl 1247.68099 Goldreich, Oded; Izsak, Rani 3 2012 Hierarchy theorems for property testing. Zbl 1282.68114 Goldreich, Oded; Krivelevich, Michael; Newman, Ilan; Rozenberg, Eyal 2 2012 Two-sided error proximity oblivious testing (extended abstract). Zbl 1352.68284 Goldreich, Oded; Shinkar, Igor 2 2012 On testing expansion in bounded-degree graphs. Zbl 1343.68302 Goldreich, Oded; Ron, Dana 47 2011 Candidate one-way functions based on expander graphs. Zbl 1306.94056 Goldreich, Oded 47 2011 On Yao’s XOR-lemma. Zbl 1304.68074 Goldreich, Oded; Nisan, Noam; Wigderson, Avi 34 2011 Collision-free hashing from lattice problems. Zbl 1343.94055 Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai 25 2011 A sample of samplers: a computational perspective on sampling. Zbl 1343.68297 Goldreich, Oded 22 2011 On proximity-oblivious testing. Zbl 1223.68045 Goldreich, Oded; Ron, Dana 20 2011 Three XOR-lemmas – an exposition. Zbl 1343.68112 Goldreich, Oded 13 2011 Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard. Zbl 1343.68093 Goldreich, Oded 11 2011 Short locally testable codes and proofs. Zbl 1309.68220 Goldreich, Oded 10 2011 Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: the state of the art. Zbl 1343.94053 Goldreich, Oded 10 2011 In a world of \(\mathrm{P}=\mathrm{BPP}\). Zbl 1343.68084 Goldreich, Oded 9 2011 Simplified derandomization of BPP using a hitting set generator. Zbl 1343.68303 Goldreich, Oded; Vadhan, Salil; Wigderson, Avi 7 2011 Introduction to testing graph properties. Zbl 1343.68299 Goldreich, Oded 7 2011 On constructing 1-1 one-way functions. Zbl 1343.94056 Goldreich, Oded; Levin, Leonid A.; Nisan, Noam 6 2011 Another proof that \(\mathcal{BPP}\subseteq \mathcal{PH}\) (and more). Zbl 1343.68085 Goldreich, Oded; Zuckerman, David 6 2011 On probabilistic versus deterministic provers in the definition of proofs of knowledge. Zbl 1343.94042 Bellare, Mihir; Goldreich, Oded 6 2011 On the complexity of computational problems regarding distributions. Zbl 1343.68115 Goldreich, Oded; Vadhan, Salil 6 2011 A brief introduction to property testing. Zbl 1343.68298 Goldreich, Oded 6 2011 Notes on Levin’s theory of average-case complexity. Zbl 1343.68111 Goldreich, Oded 5 2011 Algorithmic aspects of property testing in the dense graphs model. Zbl 1234.68137 Goldreich, Oded; Ron, Dana 4 2011 From absolute distinguishability to positive distinguishability. Zbl 1343.68290 Brakerski, Zvika; Goldreich, Oded 4 2011 Testing graph blow-up. Zbl 1343.68286 Avigad, Lidor; Goldreich, Oded 4 2011 Basic facts about expander graphs. Zbl 1343.68182 Goldreich, Oded 4 2011 The GGM construction does NOT yield correlation intractable function ensembles. Zbl 1343.94052 Goldreich, Oded 3 2011 Proximity oblivious testing and the role of invariances. Zbl 1343.68301 Goldreich, Oded; Kaufman, Tali 2 2011 Bravely, moderately: a common theme in four recent works. Zbl 1343.68113 Goldreich, Oded 2 2011 Average case complexity, revisited. Zbl 1343.68114 Goldreich, Oded 2 2011 On security preserving reductions – revised terminology. Zbl 1343.94054 Goldreich, Oded 2 2011 Contemplations on testing graph properties. Zbl 1291.05195 Goldreich, Oded 2 2011 Testing graph blow-up. Zbl 1343.68285 Avigad, Lidor; Goldreich, Oded 1 2011 Proximity oblivious testing and the role of invariances. Zbl 1343.68300 Goldreich, Oded; Kaufman, Tali 1 2011 Proving computational ability. Zbl 1343.94041 Bellare, Mihir; Goldreich, Oded 1 2011 Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs. Zbl 1343.68094 Goldreich, Oded 1 2011 From logarithmic advice to single-bit advice. Zbl 1343.68080 Goldreich, Oded; Sudan, Madhu; Trevisan, Luca 1 2011 On the average-case complexity of property testing. Zbl 1343.68296 Goldreich, Oded 1 2011 Randomness and computation. Zbl 1343.68181 Goldreich, Oded 1 2011 Property testing. Current research and surveys. Zbl 1197.68012 25 2010 More constructions of lossy and correlation-secure trapdoor functions. Zbl 1281.94024 Freeman, David Mandell; Goldreich, Oded; Kiltz, Eike; Rosen, Alon; Segev, Gil 23 2010 On testing computability by small width OBDDs. Zbl 1305.68330 Goldreich, Oded 12 2010 On the implementation of huge random objects. Zbl 1225.68132 Goldreich, Oded; Goldwasser, Shafi; Nussboim, Asaf 11 2010 Introduction to testing graph properties. Zbl 1309.68219 Goldreich, Oded 10 2010 On the randomness complexity of property testing. Zbl 1204.68097 Goldreich, Oded; Sheffet, Or 9 2010 Short locally testable codes and proofs: a survey in two parts. Zbl 1309.68218 Goldreich, Oded 7 2010 A primer on pseudorandom generators. Zbl 1210.68061 Goldreich, Oded 6 2010 A brief introduction to property testing. Zbl 1308.68149 Goldreich, Oded 4 2010 Hierarchy theorems for property testing. Zbl 1309.68221 Goldreich, Oded; Krivelevich, Michael; Newman, Ilan; Rozenberg, Eyal 4 2010 P, NP, and NP-completeness. The basics of computational complexity. Zbl 1230.68006 Goldreich, Oded 4 2010 On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits. Zbl 1196.94052 Goldreich, Oded 3 2010 Erratum for: “On basing one-way functions on NP-hardness”. Zbl 1302.68131 Akavia, Adi; Goldreich, Oded; Goldwasser, Shafi; Moshkovitz, Dana 3 2010 Algorithmic aspects of property testing in the dense graphs model. Zbl 1309.68222 Goldreich, Oded; Ron, Dana 3 2010 Foundations of cryptography. II: Basic applications. Reprint of the 2004 hardback ed. Zbl 1179.94063 Goldreich, Oded 52 2009 On proximity oblivious testing. Zbl 1304.05134 Goldreich, Oded; Ron, Dana 6 2009 Hierarchy theorems for property testing. Zbl 1255.68290 Goldreich, Oded; Krivelevich, Michael; Newman, Ilan; Rozenberg, Eyal 4 2009 Algorithmic aspects of property testing in the dense graphs model. Zbl 1255.68291 Goldreich, Oded; Ron, Dana 1 2009 Computational complexity. A conceptual perspective. Zbl 1154.68056 Goldreich, Oded 119 2008 Universal arguments and their applications. Zbl 1180.94047 Barak, Boaz; Goldreich, Oded 44 2008 ...and 136 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 4,165 Authors 103 Goldreich, Oded 55 Ishai, Yuval 38 Pass, Rafael 36 Ron, Dana 36 Sahai, Amit 31 Ostrovsky, Rafail 31 Wichs, Daniel 29 Pelc, Andrzej 28 Applebaum, Benny 28 Canetti, Ran 28 Vaikuntanathan, Vinod 27 Bitansky, Nir 27 Waters, Brent 26 Hazay, Carmit 26 Lindell, Yehuda 25 Brakerski, Zvika 24 Garg, Sanjam 24 Naor, Moni 24 Segev, Gil 24 Zhandry, Mark 23 Yung, Moti 22 Bellare, Mihir 22 Hofheinz, Dennis 22 Kiltz, Eike 22 Komargodski, Ilan 22 Rothblum, Ron D. 22 Vadhan, Salil P. 21 Alon, Noga 21 Boyle, Elette 21 Chiesa, Alessandro 21 Lin, Huijia 20 Nishimaki, Ryo 20 Shi, Elaine 20 Venkitasubramaniam, Muthuramakrishnan 19 Jain, Abhishek 19 Katz, Jonathan N. 19 Rubinfeld, Ronitt 19 Wang, Huaxiong 18 Khurana, Dakshita 18 Kushilevitz, Eyal 18 Libert, Benoît 18 Malavolta, Giulio 18 Srinivasan, Akshayaram 18 Wu, David J. 17 Asharov, Gilad 17 Ben-Sasson, Eli 17 Cohen, Ran 17 Couteau, Geoffroy 17 Gur, Tom 17 Haitner, Iftach 17 Halevi, Shai 17 Servedio, Rocco A. 17 Susilo, Willy 16 Chung, Kai-Min 16 Goyal, Vipul 16 Håstad, Johan Torkel 16 Kowalski, Dariusz R. 16 Patra, Arpita 16 Pietrzak, Krzysztof 16 Rosen, Alon 16 Shaltiel, Ronen 15 Ananth, Prabhanjan Vijendra 15 Czumaj, Artur 15 Goldwasser, Shafi 15 Peleg, David 15 Persiano, Giuseppe 15 Rothblum, Guy N. 15 Shapira, Asaf 15 Sudan, Madhu 15 Wigderson, Avi 15 Yamakawa, Takashi 14 Bhattacharyya, Arnab 14 Gu, Dawu 14 Jain, Aayush 14 Maurer, Ueli M. 14 Paneth, Omer 14 Tauman Kalai, Yael 14 Visconti, Ivan 14 Yamada, Shota 13 Damgård, Ivan Bjerre 13 Dinur, Irit 13 Döttling, Nico 13 Gilboa, Niv 13 Grigorescu, Elena 13 Omri, Eran 13 Raskhodnikova, Sofya 13 Seshadhri, Comandur 13 Wee, Hoeteck 12 Beimel, Amos 12 Boneh, Dan 12 Mu, Yi 12 Nielsen, Jesper Buus 12 O’Neill, Adam 12 Tessaro, Stefano 12 Zuckerman, David 11 Bartusek, James 11 Dodis, Yevgeniy 11 Fischer, Eldar 11 Hanaoka, Goichiro 11 Kaufman, Tali ...and 4,065 more Authors all top 5 Cited in 245 Serials 240 Journal of Cryptology 198 Theoretical Computer Science 95 SIAM Journal on Computing 85 Journal of Computer and System Sciences 77 Information Processing Letters 73 Computational Complexity 63 Algorithmica 58 Designs, Codes and Cryptography 54 Information Sciences 52 Distributed Computing 45 Information and Computation 42 Quantum Information Processing 34 Discrete Applied Mathematics 33 Theory of Computing Systems 31 Random Structures & Algorithms 21 Combinatorica 18 International Journal of Theoretical Physics 15 SIAM Journal on Discrete Mathematics 15 Journal of Mathematical Cryptology 12 Combinatorics, Probability and Computing 11 Journal of the ACM 10 Journal of Mathematical Sciences (New York) 10 Science China. Information Sciences 9 Discrete Mathematics 9 Israel Journal of Mathematics 9 International Journal of Foundations of Computer Science 9 Journal of Discrete Algorithms 9 Science in China. Series F 9 Advances in Mathematics of Communications 9 Cryptography and Communications 9 Matematicheskie Voprosy Kriptografii 8 Theory of Computing 8 Prikladnaya Diskretnaya Matematika 7 Journal of Complexity 7 Annals of Mathematics. Second Series 7 Computer Science Review 6 Linear Algebra and its Applications 6 Applicable Algebra in Engineering, Communication and Computing 6 Soft Computing 6 Journal of Combinatorial Optimization 6 Journal of Shanghai Jiaotong University (Science) 5 Networks 5 European Journal of Combinatorics 5 Discrete & Computational Geometry 5 MSCS. Mathematical Structures in Computer Science 5 International Journal of Computer Mathematics 5 Annals of Mathematics and Artificial Intelligence 5 Journal of Discrete Mathematical Sciences & Cryptography 4 Acta Informatica 4 Computers & Mathematics with Applications 4 Advances in Mathematics 4 Applied Mathematics and Computation 4 Journal of Combinatorial Theory. Series A 4 Journal of Computational and Applied Mathematics 4 Annals of Pure and Applied Logic 4 Journal of Symbolic Computation 4 Journal of Computer Science and Technology 4 Mathematical and Computer Modelling 4 Journal of Parallel and Distributed Computing 4 Cybernetics and Systems Analysis 4 Wuhan University Journal of Natural Sciences (WUJNS) 4 Journal of Systems Science and Complexity 4 Logical Methods in Computer Science 4 Frontiers of Computer Science 4 ACM Transactions on Computation Theory 3 Artificial Intelligence 3 Communications in Mathematical Physics 3 The Annals of Statistics 3 Automatica 3 Duke Mathematical Journal 3 Mathematical Systems Theory 3 Proceedings of the American Mathematical Society 3 Formal Aspects of Computing 3 Machine Learning 3 European Journal of Operational Research 3 Bulletin of the American Mathematical Society. New Series 3 Formal Methods in System Design 3 Mathematical Problems in Engineering 3 Informatica (Vilnius) 3 Electronic Commerce Research 3 Journal of Machine Learning Research (JMLR) 3 International Journal of Quantum Information 3 Mathematical Biosciences and Engineering 3 Discrete Mathematics, Algorithms and Applications 3 Groups, Complexity, Cryptology 3 Symmetry 3 ACM Transactions on Algorithms 2 Problems of Information Transmission 2 Computing 2 Journal of Graph Theory 2 Journal of Number Theory 2 Mathematics of Operations Research 2 Synthese 2 Transactions of the American Mathematical Society 2 Cryptologia 2 Science of Computer Programming 2 Operations Research Letters 2 New Generation Computing 2 Computers & Operations Research 2 Journal of Automated Reasoning ...and 145 more Serials all top 5 Cited in 46 Fields 2,083 Information and communication theory, circuits (94-XX) 1,937 Computer science (68-XX) 318 Combinatorics (05-XX) 200 Quantum theory (81-XX) 118 Operations research, mathematical programming (90-XX) 111 Number theory (11-XX) 64 Mathematical logic and foundations (03-XX) 64 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 55 Probability theory and stochastic processes (60-XX) 53 Statistics (62-XX) 42 Numerical analysis (65-XX) 40 Group theory and generalizations (20-XX) 22 Order, lattices, ordered algebraic structures (06-XX) 18 Linear and multilinear algebra; matrix theory (15-XX) 15 Algebraic geometry (14-XX) 14 Convex and discrete geometry (52-XX) 11 Biology and other natural sciences (92-XX) 9 Manifolds and cell complexes (57-XX) 8 Systems theory; control (93-XX) 6 Geometry (51-XX) 6 General topology (54-XX) 5 General and overarching topics; collections (00-XX) 5 Commutative algebra (13-XX) 5 Dynamical systems and ergodic theory (37-XX) 5 Statistical mechanics, structure of matter (82-XX) 4 General algebraic systems (08-XX) 4 Measure and integration (28-XX) 3 History and biography (01-XX) 3 Field theory and polynomials (12-XX) 3 Associative rings and algebras (16-XX) 3 Category theory; homological algebra (18-XX) 3 Functional analysis (46-XX) 3 Mechanics of particles and systems (70-XX) 2 Real functions (26-XX) 2 Difference and functional equations (39-XX) 2 Approximations and expansions (41-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 1 Nonassociative rings and algebras (17-XX) 1 Special functions (33-XX) 1 Ordinary differential equations (34-XX) 1 Abstract harmonic analysis (43-XX) 1 Operator theory (47-XX) 1 Differential geometry (53-XX) 1 Relativity and gravitational theory (83-XX) 1 Geophysics (86-XX) 1 Mathematics education (97-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.