Fact-checked by Grok 2 weeks ago

Oded Goldreich

Oded Goldreich (born February 4, 1957) is an Israeli theoretical computer scientist and professor of computer science at the Weizmann Institute of Science, where he holds the Meyer W. Weisgal Professorial Chair. His research centers on the interplay between randomness and computation, with foundational contributions to pseudorandomness, zero-knowledge proofs, property testing, and the theoretical underpinnings of cryptography and computational complexity. Goldreich received the 2017 Knuth Prize from ACM SIGACT and IEEE TC for his lasting impact on theoretical computer science, particularly in pseudorandomness and probabilistic proof systems. In 2021, he was awarded the Israel Prize in mathematics and computer science, the nation's highest academic honor in the field, though the selection process drew political controversy due to his left-leaning public stances and affiliations. He has authored influential texts such as Foundations of Cryptography and Modern Cryptography, Probabilistic Proofs and Pseudorandomness, emphasizing rigorous, complexity-based foundations over heuristic approaches.

Early Life and Education

Formative Years in Israel

Oded Goldreich was born on February 4, 1957, in , . His parents were Jewish immigrants from Europe who had escaped Nazi persecution: his mother, born in 1912 in Hannover, , immigrated to with her family shortly after the Nazis seized power in 1933; his father, born in 1906 in (then part of the Austro-Hungarian Monarchy), earned an engineering degree in the mid-1930s before relocating. Growing up in , Goldreich developed an early interest in , influenced by his father's profession. As a child around age 10, Goldreich displayed a , questioning whether widely held opinions reflected genuine reasoning or mere . In high school, he participated in an experimental course covering finite automata and programming, which he found engaging and later influenced his academic choices. Following standard Israeli practice, Goldreich served in the after high school. His military career was cut short by a car accident, after which he enrolled at the Technion in 1977, prioritizing based on his high school exposure. This sequence of experiences—family heritage amid Israel's post-independence milieu, early intellectual curiosity, and abrupt transition from military service—shaped his entry into .

University Studies at the Technion

Goldreich obtained a B.A. in from the in 1980. He pursued graduate studies at the same institution, earning an M.Sc. in in 1982 and a D.Sc. in in 1983. These degrees marked the completion of his formal university education, all conducted within a compressed timeframe of approximately three years for the graduate phases. His doctoral research centered on foundational problems in , culminating in a dissertation titled On the Security of Cryptographic Protocols and Cryptosystems, submitted in June 1983. The work examined the theoretical underpinnings of secure cryptographic systems, including protocols resistant to various attack models, reflecting early contributions to the field's emphasis on provable security. This period at the Technion laid the groundwork for Goldreich's subsequent research in .

Academic and Professional Career

Initial Academic Positions

Following his D.Sc. in from the Technion in 1983, Goldreich held a postdoctoral fellowship at the Laboratory for Computer Science from July 1983 to September 1984. He then served as a postdoctoral associate at the same laboratory from 1985 to September 1986. Concurrently with his MIT postdoc, Goldreich began his faculty career at the Technion's Department as a from October 1983 to December 1985. He was promoted to (equivalent to ) from January 1986 to June 1988, during which he continued research in and . In July 1988, he advanced to with tenure, a position he held until February 1994. These roles at the Technion allowed him to supervise students and publish foundational works on pseudorandom generators and zero-knowledge proofs while balancing visiting commitments at .

Career at the Weizmann Institute

Goldreich joined the Weizmann Institute of Science in Rehovot, Israel, in March 1994 as a faculty member in the Department of Computer Science and Applied Mathematics. He advanced to full professor the following year, in 1995. In 1998, Goldreich was appointed incumbent of the Meyer W. Weisgal Professorial Chair, a position he continues to hold. The department later reorganized into the Faculty of Mathematics and Computer Science, where he serves as Professor of Computer Science. Throughout his tenure at Weizmann, Goldreich has maintained an active research program in , while periodically undertaking visiting positions elsewhere, such as at from 1995 to 1998. As of 2025, he remains a full-time faculty member at the institute.

Research Contributions

Pioneering Work in

Goldreich played a pivotal role in establishing the theoretical foundations of modern during the and , emphasizing provable reductions and assumptions over ad-hoc designs. His early work focused on zero-knowledge proofs, interactive protocols that allow a prover to convince a verifier of a statement's truth without revealing underlying secrets. In , alongside Yair , he introduced refined definitions of zero-knowledge and analyzed their properties, addressing limitations in prior notions by , Micali, and Rackoff from 1985; this included classifications of perfect, computational, and statistical zero-knowledge, proving that honest-verifier zero-knowledge implies general zero-knowledge under certain conditions. These contributions clarified composition rules for zero-knowledge systems, such as sequential and parallel repetitions, which are essential for practical constructions like identification schemes and . A cornerstone of Goldreich's cryptographic innovations lies in , where he advanced the construction and analysis of pseudorandom generators (PRGs)—efficient algorithms stretching short random seeds into longer sequences indistinguishable from uniform randomness by polynomial-time adversaries. In joint work with and Micali around 1986, he helped formalize (PRFs), key-derivation tools secure against adaptive queries, constructed via PRGs assuming one-way functions exist; this paradigm underpins symmetric , including block ciphers and message authentication. Further, with Krawczyk and Luby in , Goldreich established between PRG existence and efficiently constructible distributions fooling specific complexity classes, linking to derandomization and amplification. These results demonstrated that pseudorandom objects amplify weak into strong security, a principle central to reducing cryptographic tasks to minimal assumptions. Goldreich's methodologies extended to secure function evaluation and property testing in cryptographic contexts, influencing protocols for privacy-preserving computations. His 1998 book Modern Cryptography, Probabilistic Proofs and synthesized these paradigms, providing a framework for defining and solving cryptographic problems via indistinguishability and reductionist proofs. Later volumes of Foundations of (2001 and 2004) formalized these techniques, treating , signatures, and as applications of basic primitives like one-way functions and ZK. These efforts, recognized by his 2009 IACR Fellowship, elevated to a rigorous grounded in computational limits rather than unproven trust in specific algorithms.

Advances in Pseudorandomness and Derandomization

Goldreich contributed to the foundational theory of pseudorandom generators (PRGs), which stretch short random seeds into longer sequences indistinguishable from truly random bits by any efficient probabilistic polynomial-time algorithm. In a 1993 paper co-authored with Hugo Krawczyk and Michael Luby, he established the existence of PRGs under standard cryptographic assumptions, such as the existence of one-way functions, providing a rigorous framework for constructing such generators that fool general-purpose distinguishers. This work built on earlier paradigms by , , Silvio Micali, and , emphasizing computational indistinguishability as the core metric for . His expositions, including the 2010 monograph A Primer on Pseudorandom Generators, systematized the construction and analysis of PRGs, highlighting their role in derandomizing probabilistic algorithms by replacing uniform randomness with pseudorandom outputs from short seeds. Goldreich also advanced pseudorandom functions (PRFs), co-defining them in 1984 with and Micali as efficient keyed functions whose outputs mimic random functions to distinguishers without the key; he proposed constructions based on pseudorandom generators, enabling secure like private-key encryption. In derandomization, Goldreich collaborated with Avi Wigderson on techniques to convert probabilistic algorithms with rare errors into deterministic ones using limited or hitting sets. Their 2002 paper introduced derandomization methods that succeed except on a small fraction of inputs, leveraging short advice strings that are correct on most instances, thus advancing unconditional derandomization under circuit lower bound assumptions. A 2013 joint work further explored derandomizing algorithms erring on exponentially few random strings, showing that even such sparse bad inputs do not simplify derandomization beyond general BPP cases, relying on non-explicit hitting set generators. These results connect to complexity classes like BPP, supporting conjectures such as prBPP = prP, where derandomization holds relative to pseudorandom reductions. Goldreich's surveys, such as chapters in Foundations of Cryptography and , underscore how PRGs facilitate derandomizing space-bounded computation and specific probabilistic tests, influencing broader efforts to prove P = BPP under hardness-vs-randomness paradigms. His emphasis on explicit constructions and indistinguishability gaps has informed subsequent research, including improved hitting set generators for BPP derandomization.

Development of Probabilistically Checkable Proofs

Goldreich contributed to the foundational development of probabilistically checkable proofs (PCPs) by constructing efficient variants that improved query complexity and enabled stronger hardness-of-approximation results for -complete problems. In 1993, alongside Safra, he presented a PCP construction with logarithmic randomness and constant queries, refining the parameters of earlier PCP theorems to better support reductions from to approximation problems like Max-3SAT. This work demonstrated how PCPs could yield inapproximability factors, such as showing that approximating Max-3SAT within a constant factor is -hard unless P=. Building on this, Goldreich collaborated with Mihir Bellare and in 1995 (extended in 1998) to introduce the concept of "free bits" in , which quantify the prover's flexibility in encoding information while maintaining verifiability. Their analysis used long-code tests to establish tighter connections between PCP structure and non-approximability, proving, for instance, that certain optimization problems resist approximation ratios better than prior bounds unless ⊆ DTIME(n^{log log n}). These advancements were pivotal in the post- theorem era, where transitioned from existence proofs to tools for concrete hardness results in . Goldreich's expositions further solidified PCPs as a core paradigm, with his 2001 survey and 2008 primer detailing their construction, error reduction, and ties to interactive proofs, serving as references for subsequent research. By emphasizing reductions and verifier efficiency, these works highlighted PCPs' role in characterizing and deriving causal links to derandomization barriers.

Broader Impacts in Theoretical Computer Science

Goldreich's foundational contributions to have extended beyond specific constructions to underpin derandomization efforts in , enabling the design of deterministic algorithms that simulate randomized ones with minimal overhead under cryptographic assumptions. This paradigm shift has influenced subfields like algorithm design and average-case analysis, where provide efficient substitutes for true randomness, as detailed in his surveys on the topic. The , advanced through Goldreich's collaborative work, has reshaped by proving that many NP-complete problems resist efficient approximation within constant factors, barring breakthroughs in hierarchies. This result, achieved in the , catalyzed the hardness-of-approximation research program, linking interactive proofs to inapproximability barriers and informing practical limits in optimization problems across and . Goldreich's monographs, such as Computational Complexity: A Conceptual (2008), emphasize intrinsic computational limits over algorithmic minutiae, fostering a unified theoretical framework that integrates , , and proof systems. These texts, alongside primers on probabilistic proofs and , have standardized pedagogical approaches in graduate curricula, promoting rigorous, assumption-based reasoning over empirical heuristics. His surveys on promise problems further highlight their role in modeling realistic computational tasks, influencing modern analyses that distinguish feasible promise-restricted settings from intractable language recognition.

Awards and Honors

Major Scientific Awards

Oded Goldreich was awarded the Donald E. Knuth Prize in 2017 by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) for fundamental and lasting contributions to theoretical computer science, encompassing areas such as cryptography, probabilistically checkable proofs, and pseudorandomness. The prize, which includes a $10,000 award, recognizes outstanding contributions to the foundations of computer science over an extended period. In 2021, Goldreich was selected as the recipient of the in and for advancements in , with the award formally presented in 2022. This biennial honor, Israel's highest civilian accolade, carries a monetary grant of 75,000 shekels (approximately $22,000 USD at the time) and acknowledges exceptional scientific achievement.

Israel Prize Selection and Legal Disputes

In March 2021, the Israel Prize selection committee for mathematics and computer science unanimously recommended Oded Goldreich, a at the , as the recipient in the exact sciences category, recognizing his contributions to . This decision aligned with established procedures where expert committees evaluate candidates based on scientific merit, though final approval rests with the Minister of Education. The recommendation sparked controversy when then-Education Minister sought to overturn it, citing Goldreich's political activism, particularly his signing of a , 2021, by over 500 Israeli academics urging the to suspend research funding for and other institutions located in settlements. Opponents, including and his successor , argued that such advocacy constituted support for selective against Israeli entities aligned with government policy on settlements, rendering Goldreich unworthy of a state honor regardless of his academic achievements. explicitly stated in November 2021 that "a person who calls for a ... is not worthy of a state prize." Goldreich and supporting petitioners challenged the ministerial interventions in Israel's , contending they violated procedural norms, , and prior court precedents limiting political overrides of committee decisions. In August 2021, the court unanimously overturned Gallant's block, directing Shasha-Biton to reconsider without undue political influence. Despite this, Shasha-Biton reaffirmed the disqualification in November 2021, prompting a rehearing in February 2022. On March 30, 2022, the ruled by majority (Justices Yael Willner and Amit) that the disqualification was incoherent and exceeded ministerial authority, emphasizing that "the harm to ... is much worse" than isolated political expressions; Justice Noam Sohlberg dissented, upholding the minister's discretion. Goldreich received the prize on April 11, 2022, in a low-key ceremony at the Ministry of , waiving the traditional Independence Day public event; it was presented by committee chair David Felber, as Shasha-Biton declined to attend. The saga highlighted tensions between scientific recognition and political vetting, with critics of the ministerial actions arguing against left-leaning academics, while supporters maintained that state prizes should exclude boycott advocates.

Political Views and Activism

Positions on Academic Boycotts and Settlements

Oded Goldreich has consistently criticized the occupation of the , describing it in January 2003 as "the most dominant source of evil in the " and a violation of the basic human right to freedom for millions of . He has advocated for the "immediate ending" of the occupation, attributing its persistence to the invested interests of settlers and right-wing elements that prioritize territorial claims over , which explicitly forbids settling citizens in occupied territories. Regarding settlements, Goldreich views their expansion as a systematic violation and a moral imperative for sanctions, distinguishing such measures from broader actions against itself. In line with this, he signed a calling for a of , located in the settlement of , and in March 2021 endorsed another urging the to cease funding the institution due to its placement in occupied territory. On academic boycotts more broadly, Goldreich argues that they can be justifiable if aimed at enforcing moral norms against human rights abuses, though he questions their practical effectiveness when confined to academic targets alone. He explicitly separates sanctions targeting settlements from those against Israeli state institutions or academia at large, maintaining neutrality on general academic boycotts of Israel due to the absence of a clear moral imperative or personal stake in advocating for them. His endorsement of selective boycotts, particularly of Ariel University, sparked significant controversy, including Education Minister Yifat Shasha-Biton's 2021 decision to withhold his Israel Prize—initially upheld by the Supreme Court but later overturned in March 2022—on grounds that such support undermined academic values, a ruling the court deemed insufficiently substantiated.

Advocacy Regarding the Israeli-Palestinian Conflict

Goldreich has long opposed Israel's of the and , terming it the "most dominant source of evil" in Israeli society for violating the basic of approximately three million and breaching through construction. He contends that the occupation fails to enhance Israel's security, instead endangering it by necessitating resource-intensive control measures, and proposes that —similar to Israel's from —combined with fortified border defenses would suffice for protection. In his view, the policy cultivates militarism, racist attitudes, and disdain for among Israelis, while stifling domestic discourse on unrelated issues like . To advance these positions, Goldreich has endorsed organizations facilitating conscientious objection to service in the territories, including Yesh Gvul and Ometz Le'Sharv, and aligned with the party as the sole parliamentary group fully committed to ending the occupation. In March 2021, he joined hundreds of academics in signing a petition urging the to deny research funding to , arguing that supporting institutions in settlements legitimizes occupation. He has similarly advocated for Palestinian statehood alongside solidarity with Palestinian academics facing restrictions. Upon receiving the in and in April 2022—following a legal battle over his political stances—Goldreich donated the full award amount to five groups critical of occupation-related policies: , Breaking the Silence, Standing Together, Kav LaOved, and Adalah. These organizations focus on documenting alleged abuses by Israeli forces, supporting soldiers who refuse orders in the territories, aiding migrant workers and , and advancing legal rights for . In May 2024, Goldreich co-signed an open letter from 17 Israeli figures calling for immediate international recognition of a Palestinian state as a step toward resolving the conflict. That October, he was among over 3,300 Israeli signatories of a petition demanding global sanctions on Israel, citing its military operations in Gaza and the West Bank as necessitating external pressure to halt policies perceived as aggressive expansionism. In a November 2, 2024, co-authored piece, he asserted that Gaza's destruction and subsequent escalations to the West Bank, northern Israel, and Lebanon originated from pre-October 7, 2023, dynamics, including blockade and prior military actions, rather than solely responding to Hamas attacks. Throughout, Goldreich frames his advocacy as rooted in a non-Zionist perspective rejecting Israel's state ideology while favoring a negotiated political resolution to the conflict.

Criticisms from Opponents and Defenses

Opponents, particularly from 's political right and pro-settlement advocates, have criticized Goldreich for endorsing targeted academic boycotts against institutions in settlements, viewing such actions as delegitimizing parts of and akin to broader tactics. In 2011, Goldreich signed a petition urging the to suspend funding for , located in the region of the , which critics like Jerusalem Post editorialists described as crossing a "red line" by selectively boycotting an institution based on its location in disputed territory. These opponents, including figures such as then-Defense Minister , argued that Goldreich's history of signing petitions against the —such as a 2002 call for students to refuse military service in —undermines national unity and justifies disqualifying him from honors like the . The 2021 Israel Prize controversy amplified these attacks, with right-wing lawmakers and settlement supporters contending that Goldreich's advocacy politicizes scientific awards and promotes anti- narratives by framing settlements as illegitimate. Gallant publicly opposed the award, claiming Goldreich backed , a movement seeking Israel's isolation, though Goldreich has consistently rejected full BDS support, limiting his stance to criticism of occupation policies. Critics from outlets aligned with nationalist views, such as Israel Academia Monitor, have further accused him of historical misrepresentation in pro-Palestinian advocacy, portraying it as biased activism that erodes Israel's academic standing. In defense, Goldreich has maintained that his positions constitute legitimate against specific policies, not opposition to itself, emphasizing that a full BDS endorsement would preclude accepting state honors like the . He argued in responses to the prize dispute that boycotting targets settlement expansion, which he views as illegal under , without extending to Israeli institutions proper. 's ruled in July 2021 that withholding the prize on political grounds lacked legal basis, leading to its eventual conferral in April 2022 after judicial intervention. Supporters, including theoretical computer scientist , have characterized the backlash as overreach, asserting Goldreich's views fall within acceptable bounds of Israeli political discourse on and . Goldreich reinforced this by donating the prize's monetary award to organizations working to end the , framing it as consistency with his principles rather than rejection of the state.

Personal Life and Legacy

Family and Private Interests

Oded Goldreich was born on February 4, 1957, in Israel. His father, Isidor Goldreich (1906–1995), was born in Vienna and immigrated to Palestine in 1938 along with siblings Arthur (1904–1990) and Gerty; he worked as a construction engineer. His mother, Klara Goldreich (1912–2004), was born in Hannover, Germany, and immigrated to Palestine in 1933 with her parents and sister Karla (1907–1956); she practiced law and headed a law office after 1966. Goldreich's parents married in January 1956 during their honeymoon. No public records detail Goldreich's siblings, , children, or personal hobbies beyond his professional and pursuits.

Influence on the Field and Ongoing Work

Goldreich's foundational work on pseudorandom generators and systems established key paradigms in , enabling secure protocols that rely on computational indistinguishability from . His contributions to probabilistic proof systems, including interactive proofs, expanded the scope of verifiable computation by incorporating bounded-error randomization, which has informed advancements in complexity classes like =. In , Goldreich advanced concepts such as probabilistically checkable proofs and inapproximability, providing tools to explore the hardness of optimization problems under efficient computation constraints. These ideas have influenced the study of and the limitations of algorithms, with applications in design and theoretical limits of verification. Goldreich's textbooks, including Foundations of Cryptography (volumes 1 and 2, published 2001 and 2004) and Computational Complexity: A Conceptual Perspective (2008), offer rigorous expositions of these topics and serve as standard references for graduate education in . His 2017 book Introduction to Property Testing formalized randomized algorithms for distinguishing datasets with specific properties from those far from them, fostering a subfield with implications for sublinear-time . Goldreich continues active research at the , emphasizing the interplay between randomness and computation. His ongoing efforts focus on property testing, , and probabilistic proof systems, with recent publications exploring constructions like robustly self-ordered graphs and their applications to testing graph properties. As of July 2025, these works extend foundational techniques to new algorithmic challenges in efficient verification and approximation.

References

  1. [1]
    [PDF] Brief Professional Biography
    Jan 30, 2019 · Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and. D.Sc. in Computer Science from the Technion ( ...
  2. [2]
    [PDF] Curriculum Vitae - Faculty of Mathematics and Computer Science
    Oded Goldreich. January 1, 2025. Current Position: Professor of Computer Science, Weizmann Institute of Science, Rehovot,. IsRAEl. Incumbent of the Meyer W ...Missing: biography | Show results with:biography
  3. [3]
    Oded Goldreich - Faculty of Mathematics and Computer Science
    Specifically, my main research areas are the interplay of randomness and computation (specifically, property testing, various types of pseudorandomness and ...Missing: achievements | Show results with:achievements
  4. [4]
    Oded Goldreich - Theory of Computing
    Oded Goldreich (b. 1957) is a professor of Computer Science at the Faculty of Mathematics and Computer Science of the Weizmann Institute of Science, Israel.Missing: born | Show results with:born
  5. [5]
    [PDF] 2017 Knuth prize is Awarded to Oded Goldreich
    Jun 13, 2017 · Knuth Prize will be awarded to Oded Goldreich of the Weizmann Institute of Science for fundamental and lasting contributions to theoretical ...
  6. [6]
    Israel Prize awarded to Oded Goldreich
    Aug 4, 2022 · Prof. Oded Goldreich of the Department of Computer Science and Applied Mathematics has received the Israel Prize, the country's highest honor.
  7. [7]
    Following controversy, left-wing mathematician Goldreich awarded ...
    Dec 4, 2022 · Professor Oded Goldreich was awarded the Israel Prize for his work in mathematics and computer science Monday, following a nearly year-long political battle.
  8. [8]
    [PDF] Modern Cryptography, Probabilistic Proofs and Pseudorandomness
    May 10, 2000 · Modern Cryptography, Probabilistic. Proofs and Pseudorandomness. (Second Edition – author's copy). Oded Goldreich. Department of Computer ...
  9. [9]
    A story behind every problem - ACM Digital Library
    Oded Goldreich was born on February 4, 1957, in. Israel. He received B.A., M.Sc., and D.Sc. degrees in Computer Science at the Technion—Israel In- stitute ...
  10. [10]
    Oded Goldreich - Old Photos (1900 - 1990)
    My father was born in 1906 in Vienna, then the capital of the Austrian-Hungarian Monarchy. He got an Engineering degree in the mid 1930's at the Technological ...Missing: biography | Show results with:biography
  11. [11]
    https://www.wisdom.weizmann.ac.il/~oded/PIC/ph0.html
  12. [12]
    Research-Life Stories – Oded Goldreich (2nd post)
    Feb 26, 2013 · A pre-career story (1977, 1980) I became a TOC-researcher quite by accident, or at least so it seems to me. In fact, it all started with a car ...
  13. [13]
    Research-Life Stories – Oded Goldreich - Windows On Theory
    Feb 26, 2013 · My first research project (1981) ... In one of my first meeting with my predetermined interim supervisor, Shimon Even (who later became my Master ...
  14. [14]
    CV of Oded Goldreich - Faculty of Mathematics and Computer Science
    Personal: Born in 1957 in Tel-Aviv, Israel. Married to Dana Ron. Israeli ... Visiting Scientist at the Laboratory for Computer Science of MIT, 1995-98.Missing: biography | Show results with:biography
  15. [15]
    [PDF] Curriculum Vitae - Faculty of Mathematics and Computer Science
    Curriculum Vitae. Oded Goldreich. January 1, 2025. Current Position: Professor of Computer Science, Weizmann Institute of Science, Rehovot,. IsRAEl. Incumbent ...
  16. [16]
    About the Authors of LNCS Volume 6650
    Oded Goldreich (oded@wisdom.weizmann.ac.il) is a Meyer W. Weisgal Professor at the Fac- ulty of Mathematics and Computer Science of the Weizmann Institute ...
  17. [17]
    CV of Oded Goldreich
    ### Summary of Oded Goldreich's Academic Positions at Weizmann Institute of Science
  18. [18]
    Definitions and properties of zero-knowledge proof systems
    In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff.
  19. [19]
    [PDF] DEFINITIONS AND PROPERTIES OF ZERO-KNOWLEDGE PROOF ...
    In this paper we investigate some aspects of these proof systems. We present new de nitions of zero knowledge, discuss their importance, and investigate their ...
  20. [20]
    [PDF] On the Composition of Zero-Knowledge Proof Systems
    We demonstrate the limitations of the composition of zero- knowledge protocols by proving that the original definition of zero-knowledge is not closed under.
  21. [21]
    [PDF] A Primer on Pseudorandom Generators
    A Primer on Pseudorandom Generators. Oded Goldreich. Department of Computer Science and Applied Mathematics. Weizmann Institute of Science ...
  22. [22]
    [PDF] on the existence of pseudorandom generators
    1163. Page 2. 1164. GOLDREICH, KRAWCZYK, AND LUBY of pseudorandomness was further developed to deal with function generators, and permuta- tion generators, and ...
  23. [23]
    Modern Cryptography, Probabilistic Proofs and Pseudorandomness
    This book provides an introduction to these three, somewhat interwoven domains (ie, cryptography, proofs and randomness).
  24. [24]
    https://www.wisdom.weizmann.ac.il/~oded/foc-book.html
  25. [25]
    Oded Goldreich, 2009 IACR Fellow
    For fundamental pioneering contributions to the scientific foundations of cryptography and for sustained leadership in cryptographic education.
  26. [26]
    Pseudorandom Generators: A Primer (by Oded Goldreich)
    This primer survey the archetypical case of general-purpose pseudorandom generators (withstanding any polynomial-time distinguisher), as well as the ...
  27. [27]
    On the Existence of Pseudorandom Generators
    Pseudorandom generators (suggested and developed by Blum and Micali and Yao) are efficient deterministic programs that expand a randomly selected k-bit seed ...
  28. [28]
    AMS :: Goldreich: A Primer on Pseudorandom Generators
    A primer on pseudorandom generators. Oded Goldreich. Publication Year: 2010. ISBN-10: 0-8218-5192-6. ISBN-13: 978-0-8218-5192-0<|separator|>
  29. [29]
    Pseudorandom Functions: Three Decades Later
    Jul 5, 2017 · In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length- ...Missing: date | Show results with:date
  30. [30]
    [PDF] Derandomization that is rarely wrong from short advice that is ...
    Jun 22, 2002 · Oded Goldreich*. Weizmann Institute of Science. Rehovot, Israel. oded@wisdom.weizmann.ac.il. Avi Wigderson†. Institute for Advanced Study and ...<|separator|>
  31. [31]
    [PDF] On Derandomizing Algorithms that Err Extremely Rarely
    Nov 6, 2013 · Abstract. Does derandomization of probabilistic algorithms become easier when the number of “bad” random inputs is extremely small?
  32. [32]
    Roei Tell's Ph.D - Weizmann Institute of Science
    This thesis focuses on the prBPP=prP conjecture, which asserts that randomness is not crucial for efficiently solving decision problems.
  33. [33]
    Pseudorandom Generators - SpringerLink
    Pseudorandom Generators. Download book PDF. Oded Goldreich. Part of the book series: Algorithms and Combinatorics ((AC,volume 17)). 1072 Accesses. Summary. A ...
  34. [34]
    Pseudorandom Generators (Chapter 8) - Computational Complexity
    8 - Pseudorandom Generators. Published online by Cambridge University Press: 05 June 2012. Oded Goldreich. Show author details. Oded Goldreich: Affiliation:.
  35. [35]
    Improved derandomization of BPP using a hitting set generator
    Improved derandomization of BPP using a hitting set generator. Oded Goldreich, Avi Wigderson. Department of Computer Science and Applied Mathematics. Research ...
  36. [36]
    [PDF] Efficient Probabilistically Checkable Proofs and Applications to ...
    The goal of this paper is to improve the values of. Q and T in such reductions. Thus we need to reduce the complexity of the underlying proof systems. Let us.
  37. [37]
    (PDF) Efficient probabilistically checkable proofs and applications to ...
    Oded Goldreich · Shmuel Safra. The current proof of the probabilistically checkable proofs (PCP) theorem (i.e., N P = P C P ( log ⁡ , O ( 1 ) ...
  38. [38]
    Free Bits, PCPs, and Nonapproximability---Towards Tight Results
    Free Bits, PCPs, and Nonapproximability---Towards Tight Results. Authors: Mihir Bellare, Oded Goldreich, and Madhu SudanAuthors Info & Affiliations. https ...
  39. [39]
    Free Bits, PCPs and Non-Approximability
    by Mihir Bellare, Oded Goldreich and Madhu Sudan. Abstract. We investigates several aspects of the connection between probabilistically checkable proof (PCP) ...
  40. [40]
    [PDF] Probabilistic Proof Systems: A Primer
    Jun 30, 2008 · Probabilistic Proof Systems: A Primer. Oded Goldreich. Department of Computer Science and Applied Mathematics. Weizmann Institute of Science ...
  41. [41]
    Probabilistic Proof Systems (papers by Oded Goldreich)
    All proof systems reviewed are probabilistic and furthermore have a non-zero error probability. However, the error probability is explicitly bounded.Missing: contributions | Show results with:contributions
  42. [42]
    [PDF] Pseudorandomness - Harvard SEAS
    Oct 23, 2012 · My exploration of pseudorandomness began in my graduate and postdoctoral years at MIT and. IAS, under the wonderful guidance of Oded Goldreich, ...
  43. [43]
    Probabilistic Proof Systems: A Primer - Now Publishers
    Aug 8, 2008 · This primer concentrates on three types of probabilistic proof systems: interactive proofs, zero-knowledge proofs, and Probabilistically Checkable Proofs (PCP).
  44. [44]
    [PDF] Computational Complexity: A Modern Approach - Princeton University
    It includes counting complexity, average case complexity, hardness amplifica- tion, derandomization and pseudorandomness, the proof of the PCP theorem, and.
  45. [45]
    Books and Lecture Notes by Oded Goldreich
    Complexity Theory is a central field of the theoretical foundations of Computer Science ... This book offers a conceptual perspective on complexity theory.
  46. [46]
    Surveys by Oded Goldreich
    O. Goldreich, Pseudorandomness, 1999. (extended, 2000.) See other texts in a webpage on pseudorandomness. O. Goldreich, Preface to ...
  47. [47]
    On promise problems: A survey - Weizmann Institute of Science
    Goldreich, Oded. / On promise problems : A survey. Theoretical Computer Science: Essays in Memory of Shimon Even. Vol. 3895 Berlin : Springer Verlag, 2006. pp.
  48. [48]
    ACM SIGACT Announces 2017 Awards
    Jun 19, 2017 · Knuth Prize is awarded to Oded Goldreich of the Weizmann Institute of Science for fundamental and lasting contributions to many areas of ...<|separator|>
  49. [49]
    Oded Goldreich Selected as Winner of 2021 Israel Prize
    Apr 30, 2021 · The Simons Institute enthusiastically congratulates Oded Goldreich for his selection as the winner of the 2021 Israel Prize in mathematics and computer science.Missing: major awards
  50. [50]
    Prof. Oded Goldreich to receive Israel Prize, ending year-long saga
    Mar 30, 2022 · Prof. Oded Goldreich to receive Israel Prize, ending year-long legal battle. The High Court of Justice overruled Education Minister Yifat Shasha ...Missing: selection disputes
  51. [51]
    Mathematician Goldreich receives Israel Prize following year-long ...
    Apr 11, 2022 · Goldreich, a professor of computer science at Israel's Weizmann Institute, received the prize for his work on computational complexity theory.Missing: major | Show results with:major
  52. [52]
    High Court overturns previous minister's denial of Israel Prize to ...
    Aug 12, 2021 · Oded Goldreich's lawyers welcome ruling but say decision should not be made by Gallant's successor Shasha-Biton, nor any other politician.
  53. [53]
    Scandal Hits Israel's Top Prize, With Claims of Witch Hunt Against ...
    Apr 14, 2021 · The education minister's decision opposing giving the prestigious Israel Prize to Prof. Oded Goldreich over his alleged support for BDS is only the latest in a ...Missing: disputes | Show results with:disputes
  54. [54]
    Political views of Oded Goldreich
    My political views. Oded Goldreich, January 2003. ... The most dominant source of evil in the Israeli society is the continued occupation of the West Bank and ...
  55. [55]
    On Possible Justifications of Boycott
    by Oded Goldreich. The public debate in Israel seems to view boycotts ... Obviously, one can envision circumstances in which an academic boycott on a ...
  56. [56]
    Oded Goldreich Promotes anti-Israel Bias
    Nov 21, 2024 · Oded Goldreich is a professor of computer science at the Weizmann Institute and an Israel Prize laureate (2021). He is a member of the Communist Party of ...
  57. [57]
    Controversial Israel Prize winner to donate grant money to human ...
    Apr 14, 2022 · Professor Oded Goldreich, a recent recipient of the Israel Prize in mathematics, announced Wednesday that he will donate his NIS 75,000 ...
  58. [58]
    Math prof again denied Israel Prize over call for Ariel U boycott - Shas
    Nov 18, 2021 · Weizmann Institute math and computer science professor Oded Goldreich again will not receive the Israel Prize this year due to his support of a boycott of ...
  59. [59]
    Court upholds decision to award Israel Prize to pro-boycott ...
    Mar 29, 2022 · Judges overturn decision to deny prize from Professor Oded Goldreich, alleged supporter of BDS; minister says calling for boycott on Israeli ...<|control11|><|separator|>
  60. [60]
    Political views of Oded Goldreich
    ### Summary of Oded Goldreich's Political Views on the Israeli-Palestinian Conflict
  61. [61]
    Israeli computer scientist Prof. Oded Goldreich is under attack by for ...
    Mar 20, 2021 · Israeli computer scientist Prof. Oded Goldreich is under attack by for advocating for Palestinian statehood and solidarity with Palestinian ...Missing: childhood | Show results with:childhood
  62. [62]
    Open letter from 17 Israeli personalities - جريدة القدس
    May 11, 2024 · Open letter from 17 Israeli personalities: “Recognize, now, the State of Palestine” ... Oded Goldreich Professor and winner of the Israel Prize ( ...
  63. [63]
    We, Israelis, Call For Global Sanctions on Israel
    More than 3,300 Israeli citizens have signed this letter. The full list of ... Oded Goldreich, Israel Prize winner, researcher in theoretical computer ...
  64. [64]
    [PDF] Lest We Forget: The Destruction Of Gaza And What Followed Did ...
    Nov 2, 2024 · In the West Bank, the biggest plagues threatening Palestinian existence were the expanding settlements ... Oded Goldreich is a professor of ...<|separator|>
  65. [65]
    Palestine and Israel: Facts and Opinions
    The following document was prepapred by Oded Goldreich towards a private presentation of Facts and Opinions regarding the Israeli-Palestine conflict at the ...Missing: advocacy | Show results with:advocacy
  66. [66]
    Goldreich crossed a red line by calling for boycott - editorial
    Nov 20, 2021 · He wrote that although calls to boycott Israel or state institutions could generally be used as a consideration in granting the Israel Prize, ...
  67. [67]
    Professor's saga highlights nationalists' reach in Israel | AP News
    Oded Goldreich was awarded the Israel Prize, the country's highest honor, a year ago. But the computer science professor ...Missing: childhood | Show results with:childhood
  68. [68]
    The Israel Prize Is Meant to Unify. More Often, It's Mired in Controversy.
    Apr 14, 2021 · The annual Israel Prize ceremony is supposed to be an august and unifying event, a beloved highlight of the Independence Day celebrations that fall on Thursday ...
  69. [69]
    Court battle and donation bring politics to the Israel Prize
    May 13, 2022 · Court battle and donation bring politics to the Israel Prize. Oded Goldreich, a professor and progressive activist, almost lost the prize.Missing: selection | Show results with:selection
  70. [70]
    He was selected to receive Israel's highest honor. Then his political ...
    Apr 11, 2021 · And critics of Goldreich said he supported the movement to boycott, divest from and sanction Israel, known as BDS, a charge that Goldreich ...<|separator|>
  71. [71]
    Withholding Israel Prize From Leftist Scientist 'Cannot Legally Stand ...
    Jul 22, 2021 · He rejected Goldreich's argument that supporting boycotts against Ariel University, which is located in the West Bank, is a legitimate political ...
  72. [72]
    Blog Archive » Just some prizes - Shtetl-Optimized
    Apr 9, 2021 · Oded Goldreich is a theoretical computer scientist at the Weizmann Institute in Rehovot, Israel. He's best known for helping to lay the ...
  73. [73]
    Academic Profile of Oded Goldreich
    ### Oded Goldreich's Key Contributions to Cryptography
  74. [74]
    Probabilistic Proof Systems (expositions by Oded Goldreich)
    All proof systems reviewed are probabilistic and furthermore have a non-zero error probability. However, the error probability is explicitly bounded.<|control11|><|separator|>
  75. [75]
    https://www.wisdom.weizmann.ac.il/~/oded/cc-book.html
  76. [76]
    Israel Prize awarded to Oded Goldreich
    His theoretical work on pseudo-randomness and zero-knowledge proof systems is considered fundamental to today's computing technologies. The Israel Prize ...
  77. [77]
    Introduction to Property Testing [Goldreich]
    Oded Goldreich · Two surveys of Dana Ron. · Xin Lyu and Orr Paradise provided me with simple and natural proofs for Facts 1 and 2 stated on page 107, which ...
  78. [78]
    Some Recent Papers by Oded Goldreich
    Some Recent Papers by Oded Goldreich. last updated: July 2025. The following papers can be obtained in Postscript or PDF. N. Amir, O. Goldreich, ...