Oded Goldreich | Academic Influence

Oded Goldreich's AcademicInfluence.com Rankings

Oded Goldreich

Computer Science

#263

World Rank

#275

Historical Rank

Theoretical Computer Science

#11

World Rank

#11

Historical Rank

computer-science Degrees

Oded Goldreich

Mathematics

#665

World Rank

#1225

Historical Rank

Complexity Theory

#5

World Rank

#5

Historical Rank

Measure Theory

#168

World Rank

#255

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Oded Goldreich's Degrees

PhD Computer Science Weizmann Institute of Science
Masters Mathematics Weizmann Institute of Science

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Oded Goldreich Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Oded Goldreich is a professor of computer science at the faculty of mathematics and computer science of the Weizmann Institute of Science, Israel. His research interests lie within the theory of computation and are, specifically, the interplay of randomness and computation, the foundations of cryptography, and computational complexity theory. He won the Knuth Prize in 2017 and was selected in 2021 to receive the Israel Prize in mathematics.

(See a Problem?)

Oded Goldreich's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

How to play ANY mental game (1987) (3927)
Private information retrieval (1995) (2485)
How to construct random functions (1986) (2109)
A randomized protocol for signing contracts (1985) (1469)
On the (im)possibility of obfuscating programs (2001) (1429)
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems (1991) (1407)
The Foundations of Cryptography - Volume 2: Basic Applications (2001) (1327)
The random oracle methodology, revisited (2000) (1281)
A hard-core predicate for all one-way functions (1989) (1189)
Property testing and its connection to learning and approximation (1996) (1109)
Foundations of Cryptography: Index (2001) (843)
Foundations of Cryptography: Basic Tools (2000) (746)
Foundations of Cryptography: List of Figures (2001) (696)
Unbiased bits from sources of weak randomness and probabilistic communication complexity (1985) (662)
The random oracle methodology, revisited (preliminary version) (1998) (653)
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (1986) (616)
On Defining Proofs of Knowledge (1992) (614)
Free bits, PCPs and non-approximability-towards tight results (1995) (613)
Public-Key Cryptosystems from Lattice Reduction Problems (1996) (609)
Foundations of Cryptography: Volume 1, Basic Tools (2001) (545)
Adaptively secure multi-party computation (1996) (530)
Foundations of Cryptography: Volume 1 (2006) (508)
Towards a theory of software protection and simulation by oblivious RAMs (1987) (492)
On the Composition of Zero-Knowledge Proof Systems (1990) (490)
Definitions and properties of zero-knowledge proof systems (1994) (484)
Computational complexity: a conceptual perspective (2008) (475)
On-line/off-line digital signatures (1996) (428)
On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization (1992) (425)
Simple construction of almost k-wise independent random variables (1990) (422)
The bit extraction problem or t-resilient functions (1985) (370)
RSA and Rabin Functions: Certain Parts are as Hard as the Whole (1988) (346)
Property Testing in Bounded Degree Graphs (2002) (332)
How to construct constant-round zero-knowledge proof systems for NP (1996) (330)
Incremental Cryptography: The Case of Hashing and Signing (1994) (329)
Modern Cryptography, Probabilistic Proofs and Pseudorandomness (1998) (324)
Simple Constructions of Almost k -wise Independent Random Variables (2002) (309)
A fair protocol for signing contracts (1990) (291)
Robust pcps of proximity, shorter pcps and applications to coding (2004) (290)
Introduction to Property Testing (2017) (274)
Session-Key Generation Using Human Passwords Only (2001) (242)
On the theory of average case complexity (1989) (241)
Everything Provable is Provable in Zero-Knowledge (1990) (237)
The Foundations of Cryptography - Volume 1: Basic Techniques (2001) (227)
Testing Monotonicity (1998) (216)
Universal arguments and their applications (2002) (213)
Chinese remaindering with errors (1999) (212)
Asynchronous secure computation (1993) (203)
On the power of two-point based sampling (1989) (200)
Resettable zero-knowledge (extended abstract) (2000) (197)
Candidate One-Way Functions Based on Expander Graphs (2000) (190)
Locally testable codes and PCPs of almost-linear length (2002) (190)
On the Cryptographic Applications of Random Functions (1984) (187)
On Yao's XOR-Lemma (1995) (186)
Collision-Free Hashing from Lattice Problems (1996) (181)
Three theorems regarding testing graph properties (2001) (181)
How to Solve any Protocol Problem - An Efficiency Improvement (1987) (178)
Learning polynomials with queries: The highly noisy case (1995) (178)
How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design (1986) (175)
On the existence of pseudorandom generators (1988) (173)
How to Construct Random Functions (Extended Abstract) (1984) (171)
On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization (1987) (169)
Foundations of Cryptography (Fragments of a Book) (1995) (168)
A Sample of Samplers - A Computational Perspective on Sampling (survey) (1997) (163)
Improved Testing Algorithms for Monotonicity (1999) (161)
Resettable Zero-Knowledge (1999) (161)
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors (1999) (159)
On the Limits of Nonapproximability of Lattice Problems (2000) (159)
More Constructions of Lossy and Correlation-Secure Trapdoor Functions (2010) (158)
A Sublinear Bipartiteness Tester for Bounded Degree Graphs (1998) (155)
On the security of multi-party ping-pong protocols (1983) (155)
Incremental cryptography and application to virus protection (1995) (148)
On Testing Expansion in Bounded-Degree Graphs (2000) (147)
On-Line/Off-Line Digital Schemes (1989) (144)
Computational complexity - a conceptual perspective (2008) (140)
Approximating average parameters of graphs (2006) (139)
Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge (1998) (133)
Lower bounds for linear locally decodable codes and private information retrieval (2002) (132)
Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme (1986) (131)
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1997) (127)
Zero-Knowledge twenty years after its invention (2002) (124)
Security preserving amplification of hardness (1990) (123)
The Power of Verification Queries in Message Authentication and Authenticated Encryption (2004) (123)
Combinatorial property testing (a survey) (1997) (123)
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) (1985) (122)
On the limits of non-approximability of lattice problems (1998) (117)
Short PCPs verifiable in polylogarithmic time (2005) (116)
On interactive proofs with a laconic prover (2001) (112)
A trade-off between information and communication in broadcast protocols (1990) (112)
Resettably-sound zero-knowledge and its applications (2001) (111)
On the np-completeness of certain network testing problems (1984) (108)
Property Testing in Bounded Degree Graphs (1997) (105)
On Completeness and Soundness in Interactive Proof Systems (1989) (104)
On Promise Problems: A Survey (2006) (103)
A uniform-complexity treatment of encryption and zero-knowledge (1993) (102)
Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK (1998) (100)
Foundations of Cryptography (2004) (100)
Uniform Generation of NP-Witnesses Using an NP-Oracle (2000) (100)
Property Testing - Current Research and Surveys (2010) (98)
On the power of cascade ciphers (1985) (93)
Comparing entropies in statistical zero knowledge with applications to the structure of SZK (1999) (93)
The Minimum-Length Generator Sequence Problem is NP-Hard (1981) (89)
Foundations of Cryptography - A Primer (2005) (88)
On the foundations of cryptography (2019) (86)
Lower Bounds for Sampling Algorithms for Estimating the Average (1995) (86)
On basing one-way functions on NP-hardness (2006) (86)
Approximations of general independent distributions (1992) (85)
On the Complexity of Interactive Proofs with Bounded Communication (1998) (85)
Randomness in interactive proofs (1990) (84)
A Note on Computational Indistinguishability (1990) (83)
How to write a paper (2005) (82)
Three XOR-Lemmas - An Exposition (1995) (79)
On proximity oblivious testing (2009) (79)
Theory of computing (1997) (78)
Another proof that bpp?ph (and more) (1997) (76)
Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection (1989) (76)
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (1997) (74)
On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes (2004) (72)
Introduction to Testing Graph Properties (2010) (70)
Almost k-wise independence versus k-wise independence (2003) (69)
A Simple Protocol for Signing Contracts (1983) (68)
Quantifying knowledge complexity (1991) (66)
Efficient approximation of product distributions (1998) (64)
Theory of computing: a scientific perspective (1996) (63)
Interactive proof systems: Provers that never fail and random selection (1987) (63)
Fault-tolerant computation in the full information model (1991) (63)
Concurrent zero-knowledge with timing, revisited (2002) (63)
Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier (1999) (62)
How To Construct Randolli Functions (1984) (60)
On the Foundations of Modern Cryptography (1997) (58)
Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard (2011) (58)
Cryptography and cryptographic protocols (2003) (58)
The uniform distribution is complete with respect to testing identity to a fixed distribution (2016) (57)
Foundations of Cryptography: General Cryptographic Protocols (2004) (56)
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop (1998) (55)
On the implementation of huge random objects (2003) (55)
On the (im)possibility of obfuscating programs : (Extended abstract) (2001) (55)
P, Np, and Np-Completeness: The Basics of Computational Complexity (2010) (54)
Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs (1995) (51)
The Random Oracle Hypothesis Is False (1994) (51)
Notes on Levin's Theory of Average-Case Complexity (1997) (51)
Finding cycles and trees in sublinear time (2010) (50)
A theory of goal-oriented communication (2012) (49)
Derandomization that is rarely wrong from short advice that is typically good (2002) (48)
DES-like functions can generate the alternating group (1983) (47)
Towards a Theory of Software Protection (1986) (42)
Computational sample complexity (1997) (41)
Short Locally Testable Codes and Proofs (Survey) (2005) (41)
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators (2003) (41)
RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure (1984) (41)
The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols (1990) (39)
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem (1997) (39)
On Promise Problems (a survey in memory of Shimon Even [1935-2004]) (2005) (38)
In a World of P=BPP (2010) (37)
Enhancements of Trapdoor Permutations (2012) (36)
Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art (2011) (36)
On Testing Computability by Small Width OBDDs (2010) (35)
Algorithmic Aspects of Property Testing in the Dense Graphs Model (2009) (35)
A Tradeoff between Information and Communication in Broadcast Protocols (1988) (35)
On the Security of Ping-Pong Protocols when Implemented using the RSA (1985) (34)
On Sample-Based Testers (2016) (33)
Electronic Wallet (1983) (32)
Hashing Functions can Simplify Zero-Knowledge Protocol Design (too) (1994) (32)
Computational Complexity and Knowledge Complexity (1998) (30)
Bounds on tradeoffs between randomness and communication complexity (1990) (30)
A Primer on Pseudorandom Generators (2010) (30)
Sparse Pseudorandom Distributions (1989) (30)
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge (2006) (29)
A quantitative approach to dynamic networks (1990) (29)
Theoretical Computer Science, Essays in Memory of Shimon Even (2006) (28)
Improved Derandomization of BPP Using a Hitting Set Generator (1999) (28)
Hierarchy Theorems for Property Testing (2009) (28)
On the possibility of basing Cryptography on the assumption that P ≠ NP (1998) (28)
An improved parallel algorithm for integer GCD (1990) (27)
On the possibilities and limitations of pseudodeterministic algorithms (2013) (27)
On Constructing 1-1 One-Way Functions (1995) (27)
Matrix rigidity of random Toeplitz matrices (2016) (27)
Simplified Derandomization of BPP Using a Hitting Set Generator (2000) (26)
Proximity Oblivious Testing and the Role of Invariances (2011) (26)
Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems (2018) (26)
Velickovic approximations of general independent distributions (1992) (25)
On derandomizing algorithms that err extremely rarely (2014) (25)
Bounds on 2-Query Codeword Testing (2003) (25)
Short Locally Testable Codes and Proofs: A Survey in Two Parts (2010) (25)
Strong Locally Testable Codes with Relaxed Local Decoders (2015) (25)
The tensor product of two good codes is not necessarily robustly testable (2012) (25)
On The Randomness Complexity of Property Testing (2007) (25)
A Fair Protocol for Signing Contracts (Extended Abstract) (1985) (24)
Another proof that BPP subseteq PH (and more) (1997) (24)
On Post-Modern Cryptography (2006) (24)
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits (2007) (24)
Randomness and Computation (2011) (24)
Addendum to "Simple Construction of Almost k-wise Independent Random Variables" (1993) (23)
Computer Security and Cryptography (1997) (23)
A Brief Introduction to Property Testing (2011) (23)
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions (2013) (22)
Open Problems in Data Streams, Property Testing, and Related Topics (2011) (21)
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets (2017) (21)
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing (2013) (20)
Foundations of Cryptography: Encryption Schemes (2004) (20)
The effects of link failures on computations in asynchronous rings (1986) (20)
Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali (2019) (19)
A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm (1993) (19)
From logarithmic advice to single-bit advice (2004) (18)
On the complexity of computational problems regarding distributions (a survey) (2011) (18)
Randomized Methods in Computation-Lecture Notes (2001) (18)
RSA/Rabin Least Significant Bits are 1/2 + 1/(poly(log N)) Secure (1985) (17)
Property testing in massive graphs (2002) (17)
A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm (1988) (17)
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs (2015) (17)
Randomness, interactive proofs, and zero-knowledge—A survey (1988) (17)
On Approximating the Average Distance Between Points (2007) (17)
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs (2001) (16)
Worst-case to Average-case reductions for subclasses of P (2017) (16)
Public-key cryptography from lattice reduction problems (1997) (16)
Probabilistic Proof Systems (1994) (16)
On Doubly-Efficient Interactive Proof Systems (2018) (15)
Source to destination communication in the presence of faults (1989) (15)
Probabilistic Proof Systems: A Primer (2008) (15)
On Randomness Extraction in AC0 (2015) (15)
On the Number of Close-and-Equal Pairs of Bits in a String (1984) (14)
Testing Graph Blow-Up (2011) (14)
Basic Facts about Expander Graphs (2011) (14)
On Pseudorandomness with respect to Deterministic Observes (2000) (14)
On Multiple Input Problems in Property Testing (2013) (13)
Cryptography and Computer Security (2003) (13)
Computational indistinguishability: a sample hierarchy (1998) (13)
P, NP, and NP-Completeness: The Basics of Complexity Theory (2010) (13)
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP (2021) (12)
Deterministic amplification of space-bounded probabilistic algorithms (1999) (12)
Universal Locally Testable Codes (2016) (12)
Zero-Knowledge (2002) (12)
Two‐sided error proximity oblivious testing (2016) (12)
The Foundations of Modern Cryptography (1999) (12)
Pseudorandom Generators: A Primer (2008) (11)
Every set in P is strongly testable under a suitable encoding (2018) (11)
Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing (1994) (11)
On Estimating the Average Degree of a Graph (2004) (11)
On (Valiant's) Polynomial-Size Monotone Formula for Majority (2020) (11)
On Security Preserving Reductions - Revised Terminology (2000) (11)
Computational Indistinguishability: Algorithms vs. Circuits (1998) (10)
Testing graphs in vertex-distribution-free models (2019) (10)
A taxonomy of proof systems (1998) (10)
Multi-pseudodeterministic algorithms (2019) (10)
On Promise Problems in Memory of Shimon Even (1935{2004) (10)
Monotone Circuits: One-Way Functions versus Pseudorandom Generators (2012) (10)
Proving Computational Ability (2011) (9)
Erratum for: on basing one-way functions on NP-hardness (2010) (9)
Short Locally Testable Codes and Proofs (2011) (9)
Towards a computational theory of statistical tests (1992) (9)
Electing a leader in a ring with link failures (1987) (9)
From absolute distinguishability to positive distinguishability (2009) (9)
Contemplations on Testing Graph Properties (2005) (9)
A Short Tutorial of Zero-Knowledge (2013) (9)
Interleaved Zero-Knowledge in the Public-Key Model (1999) (8)
Probabilistic Proof Systems - A Survey (1997) (8)
The GGM Construction does NOT yield Correlation Intractable Function Ensembles (2002) (8)
Concurrent Zero-Knowledge With Timing (2002) (8)
A Candidate Counterexample to the Easy Cylinders Conjecture (2009) (8)
Introduction to Complexity Theory Notes for a One{semester Course (7)
Bravely, Moderately: A Common Theme in Four Recent Works (2011) (7)
On Teaching the Basics of Complexity Theory (2006) (7)
On the Theory of Average Case Complexity (abstract) (1989) (7)
On Chosen Ciphertext Security of Multiple Encryptions (2002) (7)
Computational complexity and knowledge complexity (extended abstract) (1994) (7)
Computational Complexity (2008) (7)
The future of computational complexity theory: part I (1996) (7)
Testing Isomorphism in the Bounded-Degree Graph Model (2019) (7)
On Counting $t$-Cliques Mod 2 (2020) (7)
RSA/Rabin least significant bits are \( \tfrac{1} {2} + \tfrac{1} {{poly \left( {\log N} \right)}} \) secure (Extended Abstract) (1984) (7)
The Bit Security of Modular Squaring Given Partial Factorization of the Modulos (1985) (7)
Bravely, Moderately: A Common Theme in Four Recent Results (2005) (6)
On Sample-Based Testers (2015) (6)
General Cryptographic Protocols: The Very Basics (2013) (6)
Two Comments on Targeted Canonical Derandomizers (2011) (6)
Randomness Extraction from Somewhat Dependent Sources (2019) (6)
Lecture Notes on Pseudorandomness { Part I (6)
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity (2019) (5)
A theory of goal-oriented communication (2011) (5)
ON THE POWER OF TWO-POINTS BASED SAMPLING (1989) (5)
The random oracle model (1998) (5)
Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword (2007) (5)
On Universal Learning Algorithms (1997) (5)
On the doubly-efficient interactive proof systems of GKR (2017) (5)
On the Circuit Complexity of Perfect Hashing (1996) (5)
Flexible models for testing graph properties (2018) (5)
On the Complexity of Estimating the Effective Support Size (2019) (5)
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract) (2012) (5)
Robustly self-ordered graphs: constructions and applications to property testing (2021) (5)
On the Average-Case Complexity of Property Testing (2007) (4)
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model (2022) (4)
On Learning and Testing Dynamic Environments (2014) (4)
On Concurrent Identification Protocols (1984) (4)
A Note on Computational Indistinguishability 1 (1990) (4)
Computational Complexity: P, NP, and NP-Completeness (2008) (4)
On Testing Hamiltonicity in the Bounded Degree Graph Model (2020) (4)
Super-Perfect Zero-Knowledge Proofs (2014) (4)
Foundations of Cryptography – a Primer Foundations of Cryptography – a Primer Boston – Delft Foundations and Trends (2005) (4)
On Testing Asymmetry in the Bounded Degree Graph Model (2020) (3)
On the lowest level of query complexity in testing graph properties (2009) (3)
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly (2015) (3)
Proofs that Release Minimum Knowledge (1986) (3)
A Lower Bound on the Complexity of Testing Grained Distributions (2021) (3)
On the complexity of computation in the presence of link failures: the case of a ring (1991) (3)
Bridging a Small Gap in the Gap Amplification of Assignment Testers (2020) (3)
The Graph Clustering Problem has a Perfect Zero-Knowledge Interactive Proof (1999) (3)
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof (1996) (3)
A Probabilistic Error-Correcting Scheme (1997) (3)
Another Motivation for Reducing the Randomness Complexity of Algorithms (2011) (3)
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model (2019) (3)
Information Theory versus Complexity Theory: Another Test Case (1995) (3)
On the Existence of Pseudorandom Generators (Extended Abstract) (1988) (3)
Towards a Computational Theory of Statistical Tests (Extended Abstract) (1992) (3)
On the complexity of global computation in the presence of link failures: the case of uni-directional faults (1992) (3)
Reducing testing affine spaces to testing linearity (2016) (3)
A Combinatorial Consistency Lemma with application to the PCP Theorem (1996) (3)
On the Message Complexity of Interactive Proof Systems (1996) (2)
Improved bounds on the AN-complexity of multilinear functions (2019) (2)
On Emulating Interactive Proofs with Public Coins (2016) (2)
Foundations of Cryptography: Introduction (2001) (2)
Testing Graph Properties in the Dense Graph Model 2 2 Testing Graph Properties in the Bounded-Degree Graph Model 4 3 Testing Graph Properties in the General Graph Model 5 (2018) (2)
On the Locally Testable Code of Dinur et al. (2021) (2021) (2)
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions (2017) (2)
On the Optimal Analysis of the Collision Probability Tester (an Exposition) (2020) (2)
A Common Theme in Four Recent Works (2)
On Constructing Expanders for Any Number of Vertices (2020) (2)
Notes on Linearity ( Group Homomorphism ) Testing (2016) (2)
On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition) (2020) (2)
Preface to Special Issue on General Secure Multi-party Computation Background on General Secure Multi-party Computation (1999) (2)
On properties that are non-trivial to test (2022) (2)
Modern Cryptography, Probabilistic Proofs and Pseudorandomness (Second Edition - author's copy) (2000) (1)
Property Testing and Its Connection to Learning andApproximationOded (2014) (1)
On struggle and competition in scientic fields (2012) (1)
Sparse pseudorandom distributions (extended abstract) (1989) (1)
Special Issue on Randomness and Complexity (2006) (1)
On the Effect of the Proximity Parameter on Property Testers (2012) (1)
On the Implementation of Huge Random Objects ( Preliminary Version ) (2003) (1)
How NOT to write a paper (2017) (1)
Computational Complexity: On the Foundations of Modern Cryptography (2008) (1)
Invitation to complexity theory (2012) (1)
A taxonomy of proof systems (part 2) (1994) (1)
Deconstructing 1-local expanders (2016) (1)
Overview of the doubly-efficient interactive proof systems of RRR (2017) (1)
One-Sided Error Testing of Monomials and Affine Subspaces (2020) (1)
Constant-round interactive proof systems for AC0[2] and NC1 (2018) (1)
Foundations of Cryptography: Corrections and Additions to Volume 1 (2004) (1)
Strong Proofs of Knowledge (2011) (1)
On the impact of cryptography on complexity theory (2019) (1)
Open Problems in Property Testing of Graphs (2021) (1)
Concurrent Zero-knowledge with Timing, Revisited (preliminary Version) (2001) (1)
The Subgraph Testing Model (2020) (1)
Testing Distributions of Huge Objects (2022) (1)
Robust Self-Ordering versus Local Self-Ordering (2021) (1)
Estimating Simple Graph Parameters in Sublinear Time (2016) (1)
More Constructions of Lossy and Correlation-Secure Trapdoor Functions (2011) (1)
Reducing Testing Affine Spaces to Testing Linearity of Functions (2020) (1)
Foundations of Cryptography Class Notes Spring 1989 (2014) (1)
Foundations of Cryptography: Background in Computational Number Theory (2001) (1)
A taxonomy of proof systems (part 1) (1993) (1)
Hierarchy Theorems for Property Testing (2011) (1)
The Second Part of the next Claim Follows from a Standard Application of Chernoo Bounds. B General Commodity Testing (1999) (1)
Matrix rigidity of random Toeplitz matrices (2016) (1)
Average Case Complexity, Revisited (2011) (1)
Zero-knowledge: abstract of a tutorial (2002) (1)
P, NP, and NP-Completeness: NP-Completeness (2010) (1)
Brief Announcement : A Theory of Goal-Oriented Communication ∗ (2011) (0)
Correction to 'DES-like functions can generate the alternating group' (Nov 83 863-865) (1984) (0)
P, NP, and NP-Completeness: Polynomial-time Reductions (2010) (0)
More Resources, More Power? (2008) (0)
Testing Dictatorships, Juntas, and Monomials (2017) (0)
Work and Publications (2011) (0)
Approximations of General Independent Distributions 1 (2014) (0)
Sparse and Evasive Pseudorandom Distributions (2014) (0)
Variations on P and NP (2008) (0)
It Follows That M K = N (1997) (0)
Special issue from RANDOM’09: Editors’ Foreword (2012) (0)
On randomness extractors (2010) (0)
The cryptographic lens: Shafi Goldwasser's Turing lecture (2019) (0)
An interview with Silvio Micali (2019) (0)
On the Complexity of Interactive Proof with Bounded Communication (1997) (0)
Cryptographic applications of pseudorandom functions (2010) (0)
Basics of Probability Theory ( for Theory of Computation courses ) (2008) (0)
Probabilistic Preliminaries and Advanced Topics in Randomization (2008) (0)
Texts in Computational Complexity : (2005) (0)
On Interactive Proofs of Proximity with Proof-Oblivious Queries (2022) (0)
On the number of monochromatic close pairs of beads in a rosary (1990) (0)
Lessons from Kant : On Knowledge , Morality , and Beauty (2012) (0)
Special Issue on the 10th Theory of Cryptography Conference: Editor’s Foreword (2016) (0)
Preface (2019) (0)
Notes for the first lecture in a course on Property Testing (2016) (0)
General-purpose pseudorandom generators (2010) (0)
Some Computational Problems (2008) (0)
Testing Bipartiteness in the Dense-Graph Model (2016) (0)
Main Definitions and Results (2010) (0)
The Program of the Mini-Workshop (2010) (0)
Probabilistic Preliminaries for Lecture Notes on Property Testing (2015) (0)
The Bright Side of Hardness: Relating Computational Complexity and Cryptography (notes for an overview talk) (2008) (0)
Transitive Transfer of Conndence: a Per- Fect Zero-knowledge Interactive Proto- Col for Sat and Beyond. 5.1 Additional Security for the User (1997) (0)
Dispositif pour effectuer et enregistrer des transactions monétaires (1985) (0)
Preface to "Week Three: Randomness in Computation" (2004) (0)
Computational Tasks and Models (2010) (0)
On the status of intellectual values in TOC (2011) (0)
Computational Complexity: Space Complexity (2008) (0)
On our duties as scientists (2009) (0)
To the Teacher (2010) (0)
The P versus NP Question (2010) (0)
PODIUM: Procuring Opinions from Diverse Users in a Multi-Dimensional World (2017) (0)
Testing by Implicit Sampling (2017) (0)
Probabilistic Proof Systems - Lecture Notes (1996) (0)
cs . C R ] 1 1 O ct 2 00 0 The Random Oracle Methodology , Revisited ∗ (2008) (0)
Zero-knowledge.and the Desi~ of Secure Protocols (an Exposition for Engineers) (an Exposition for Engineers) (2013) (0)
Foundations of Cryptography: Brief Outline of Volume 2 (2001) (0)
A SKETCH OF SCHNORR AND ALEXI IMPROVEMENT (2002) (0)
4 Secret Sharing over the Reals (2007) (0)
Notes for Lower Bounds Techniques (2016) (0)
Computational Complexity: Epilogue (2008) (0)
Organization and Chapter Summaries (2008) (0)
Epilogue: A Brief Overview of Complexity Theory (2010) (0)
An interview with Shafi Goldwasser (2019) (0)
One obsession at a time: a brief biography of Silvio Micali (2019) (0)
A Second Look at the XOR-Lemma (2014) (0)
Testing Property of graphs: Introduction and a few examples (2008) (0)
Mathematisches Forschungsinstitut Oberwolfach Complexity Theory (2007) (0)
Quantifying Knowledge Complexity ( Preliminary Version ) (2014) (0)
Computational Complexity: a Conceptual Perspective Variations on P and Np 3.1.1 Boolean Circuits (0)
Pseudorandomness - Part I (2004) (0)
Interleaved Zero-Knowledge ( A Preliminary Version ) (1999) (0)
Foundations of Cryptography : List of References July 1989 (2014) (0)
How to Use My 1989 Lecture Notes on Encryption, Signatures and Crypto-protocols (1996) (0)
FoC : The Computational Model (2008) (0)
Preface (2003) (0)
Chinese Remaindering with ErrorsOded Goldreich (2014) (0)
Computational Complexity: Some Computational Problems (2008) (0)
Preface to the Special Issue from Random’06 (2008) (0)
Critique of some trends in the TCS community in light of two controversies (1992) (0)
Testing Graph Properties in the Bounded-Degree Graph Model (2017) (0)
Lecture Notes on Testing Dictatorships , Juntas , and Monomials (2016) (0)
Lecture Notes for Testing Properties of Distributions (2016) (0)
Space-bounded distinguishers (2010) (0)
Notations and Conventions (2010) (0)
Lecture Notes on Low Degree Tests (2015) (0)
Leader in the Prese : q . ce of Faults : a Ring as a Special Case (2012) (0)
ON THE SKCURITY' OF IlULn-pARTYPING-PONG PROTOCOLS" (1983) (0)
A Male ' s Exper ience of Being a Gender Minor ity (0)
Special Issue on the 10th Theory of Cryptography Conference: Editor’s Foreword (2016) (0)
On Testing Bipartiteness in the Bounded-Degree Graph Model (2017) (0)
Hierarchy Theorems for Property TestingOded Goldreich (2014) (0)
The Bright Side of Hardness (2008) (0)
Quantifying Knowledge Complexity (preliminary Version) Quantifying Knowledge Complexity @bullet (preliminary Version) (2014) (0)
Ööòòóññþþøøóò Øøøø × Ööööðý Ûöóòò Öóñ ××óöø Úúúú Øøøø × Øýôôôôððý Óóó´èööððññòòöý (0)
Texts in Computational Complexity IP AM and round speed up (2005) (0)
On some noncryptographic works of Goldwasser and Micali (2019) (0)
Three Relatively Advanced Topics (2010) (0)
Computational Complexity: a Conceptual Perspective List of Figures Probabilistic Proof Systems (0)
Computational Complexity: Glossary of Complexity Classes (2008) (0)
Low-Degree Tests (2017) (0)
A Note on Testing MonotonicityOded Goldreich (2007) (0)
Advice , Critique , and a Technical Topic (2017) (0)
Timed Modal Specifications........ 8 (0)
Texts in Computational Complexity: Probabilistic Preliminaries and Advanced Topics in Randomization (2006) (0)
Pseudorandomness, Volume 46, Number 10 (1999) (0)
Relaxing the Requirements (2008) (0)
Computational Complexity: Introduction and Preliminaries (2008) (0)
Foundations of Cryptography: Pseudorandom Generators (2001) (0)
Pseudo-Mixing Time of Random Walks Itai Benjamini (2019) (0)
Diverse User Selection for Opinion Procurement (2020) (0)
Computational Complexity: On the Quest for Lower Bounds (2008) (0)
Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More) (2011) (0)
Foundations of Cryptography: Zero-Knowledge Proof Systems (2001) (0)
Derandomization of time-complexity classes (2010) (0)
On intellectual and instrumental values in science (2012) (0)
Communication complexity with defective randomness (2021) (0)
Proofs, according to Silvio: Silvio Micali's Turing lecture (2019) (0)
IV.20 Computational Complexity (2010) (0)
On the philosophical basis of computational theories (2014) (0)
Content-Oblivious Quality Measures and the Control of Academia (2015) (0)
DES-Like Functions Can Generate the 863 Alternating Group (1998) (0)
Lower Bounds Techniques (2017) (0)
A story behind every problem: a brief biography of Shafi Goldwasser (2019) (0)
Brief Announcement : A Theory of Goal-Oriented (2011) (0)
Enhancements of Trapdoor Permutations (2012) (0)
Quantitative Analysis of Dynamic Network Protocols (1994) (0)
Improved bounds on the AN-complexity of O(1)-linear functions (2022) (0)
Using randomness in computation (2010) (0)
Testing in the bounded-degree graph model with degree bound two (2022) (0)
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity (2019) (0)
Testing Linearity (Group Homomorphism) (2017) (0)
Computational Complexity: Randomness and Counting (2008) (0)
Tentative Collection of Reading Material (2011) (0)
On Scientific Evaluation and its relation to Understanding , Imagination , and Taste (2012) (0)
Randomized Broadcasting in Radio Networks , 1992 (2007) (0)
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network (2020) (0)
Two Lectures on Advanced Topics in Computability (2009) (0)
On Approximating the Average Distance Between PointsK r (2014) (0)
Lecture Notes on Testing by Implicit Sampling (2016) (0)
Preface to Shafi & Silvio ’ s book ∗ (2019) (0)
Complexity Theory (2019) (0)
Ramifications and Related Topics (2017) (0)
Resettably-Sound Zero-Knowledge and its Applications ( preliminary version ) (2001) (0)
Lecture Notes on Locally Testable Codes and Proofs (2016) (0)
Demystifying the Master Thesis and Research in General : The Story of Some Master Theses (2014) (0)
Secure Multi-party Computation Dedication a Warning (1998) (0)
Mathematisches Forschungsinstitut Oberwolfach Report No . 26 / 2005 Complexity Theory (0)
Locally Testable Codes and Proofs (2017) (0)
現代暗号・確率的証明・擬似乱数 (2001) (0)
Testing Properties of Distributions (2017) (0)
Testing Bipartiteness of Graphs in Sublinear Time (2016) (0)
Computational Complexity: a Conceptual Perspective Organization and Chapter Summaries (0)
Pseudo-Mixing Time of Random Walks (2019) (0)
Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation (2020) (0)
Appeared I N Siam Journal on Computing Computational Complexity and Knowledge Complexity Appeared I N Siam Journal on Computing (1998) (0)
Some basic complexity classes (2010) (0)
Notes on Testing Graph Properties in the Dense Graph Model (2016) (0)
Collision-Free Hashing from Lattice ProblemsOded Goldreich (2014) (0)
Foundations of Cryptography: Digital Signatures and Message Authentication (2004) (0)
On the Use of Complexity In Cryptography (2011) (0)
A generic hard-core predicate (2010) (0)
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy (2020) (0)
Special issue from RANDOM’09: Editors’ Foreword (2012) (0)
Foundations of Cryptography: Preface (2001) (0)
The KW Games as a Teaser (2021) (0)
Preface (2000) (0)
The Main Themes: Approximate Decision and Sublinear Complexity (2017) (0)
Special purpose generators (2010) (0)
Approximating Average Parameters of Graphs In Memory of Shimon Even (1935{2004) (2006) (0)
Lecture Notes on Testing Monotonicity (2016) (0)
Testing Graph Properties in the General Graph Model (2017) (0)
Monotonicity Testing Jul 1 5* (2013) (0)
Some Omitted Proofs (2008) (0)

This paper list is powered by the following services:

Other Resources About Oded Goldreich

What Schools Are Affiliated With Oded Goldreich?

Oded Goldreich is affiliated with the following schools:

Image Attributions

Image Source for Oded Goldreich