Oded Goldreich | Academic Influence

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 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 Papers

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

Oded Goldreich's AcademicInfluence.com Rankings

Computer Science

Image Attributions

Image Source for Oded Goldreich