Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch

No abstract is available for this paper.

• Publication year

  2014

• Venue

  Cybersecurity and Cyberforensics Conference

• Publication date

  2014-06-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CCC.2014.9
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Locally Computable UOWHF with Linear Shrinkage

  2013cited by this paper
• Cryptographic Hardness of Random Local Functions

  2013cited by this paper
• LS+ Lower Bounds from Pairwise Independence

  2013cited by this paper
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results

  2013cited by this paper
• Pseudorandom generators with long stretch and low locality from random local one-way functions

  2012cited by this paper
• SDP Gaps from Pairwise Independence

  2012cited by this paper
• On the security of Goldreich’s one-way function

  2012cited by this paper
• Hypercontractivity, sum-of-squares proofs, and their applications

  2012cited by this paper
• A Dichotomy for Local Small-Bias Generators

  2012cited by this paper
• Robust satisfiability of constraint satisfaction problems

  2012cited by this paper
• Approximability and proof complexity

  2012cited by this paper
• Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems

  2012cited by this paper
• Directed Steiner Tree and the Lasserre Hierarchy

  2011cited by this paper
• Input Locality and Hardness Amplification

  2011cited by this paper
• Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

  2011cited by this paper
• Approximating Non-Uniform Sparsest Cut Via Generalized Spectra

  2011cited by this paper
• Approximating CSPs with global cardinality constraints using SDP hierarchies

  2011cited by this paper
• Rounding Semidefinite Programming Hierarchies via Global Correlation

  2011cited by this paper
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives

  2011cited by this paper
• Candidate One-Way Functions Based on Expander Graphs

  2011cited by this paper
• New Tools for Graph Coloring

  2011cited by this paper
• Detecting High Log-Densities – an O ( n 1 / 4 ) Approximation for Densest k -Subgraph

  2010cited by this paper
• Goldreich ’ s One-Way Function Candidate and Drunken Backtracking Algorithms

  2010cited by this paper
• Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms

  2010cited by this paper
• Pseudorandomness against Depth-2 Circuits and Analysis of Goldreich's Candidate One-Way Function

  2010cited by this paper
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

  2010cited by this paper
• Public-key cryptography from different assumptions

  2010cited by this paper
• Approximating Sparsest Cut in Graphs of Bounded Treewidth

  2010cited by this paper
• Robust Algorithms for Max Independent Set on Minor-Free Graphs Based on the Sherali-Adams Hierarchy

  2009cited by this paper
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

  2009cited by this paper
• CSP gaps and reductions in the lasserre hierarchy

  2009cited by this paper
• Integrality gaps for Sherali-Adams relaxations

  2009cited by this paper
• Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms

  2009cited by this paper
• Constraint Satisfaction Problems of Bounded Width

  2009cited by this paper
• MaxMin allocation via degree lower-bounded arborescences

  2009cited by this paper
• SDP Integrality Gaps with Local ell_1-Embeddability

  2009cited by this paper
• SDP Integrality Gaps with Local̀ 1-Embeddability Subhash Khot

  2009cited by this paper
• Approximating np-hard problems efficient algorithms and their limits

  2009cited by this paper
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies

  2008cited by this paper
• Cryptography with constant computational overhead

  2008cited by this paper
• Optimal algorithms and inapproximability results for every CSP?

  2008cited by this paper
• Linear Level Lasserre Lower Bounds for Certain k-CSPs

  2008influential reference
• One-way multiparty communication lower bound for pointer jumping with applications

  2007cited by this paper
• Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

  2007cited by this paper
• A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

  2007cited by this paper
• Linear programming relaxations of maxcut

  2007cited by this paper
• New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy

  2006cited by this paper
• On ε‐biased generators in NC0

  2006cited by this paper
• On Pseudorandom Generators with Linear Stretch in NC0

  2006cited by this paper
• Euclidean distortion and the sparsest cut

  2005cited by this paper
• Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy

  2005cited by this paper
• Expander flows, geometric embeddings and graph partitioning

  2004cited by this paper
• Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

  2004cited by this paper
• Cryptography in NC0

  2004cited by this paper
• Easily refutable subformulas of large random 3CNF formulas

  2004cited by this paper
• Maximizing quadratic programs: extending Grothendieck's inequality

  2004cited by this paper
• Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations

  2004cited by this paper
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set

  2003cited by this paper
• More on Average Case vs Approximation Complexity

  2003cited by this paper
• Rank bounds and integrality gaps for cutting planes procedures

  2003cited by this paper
• Proving integrality gaps without knowing the linear program

  2002cited by this paper
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs

  2002cited by this paper
• Query efficient PCPs with perfect completeness

  2001influential reference
• On Pseudorandom Generators in NC

  2001influential reference
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

  2001cited by this paper
• On pseudorandom generators in NC 0 ⋆

  2001cited by this paper
• Optimisation globale et théorie des moments

  2000cited by this paper
• Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization

  2000cited by this paper
• Efficient Parallel Pseudo-random Number Generation

  2000influential reference
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• Cones of Matrices and Set-Functions and 0-1 Optimization

  1991cited by this paper
• A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems

  1990cited by this paper
• Eigenvalues and graph bisection: An average-case analysis

  1987cited by this paper
• Correlation-immunity of nonlinear combining functions for cryptographic applications

  1984cited by this paper

• Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders

  2025cites this paper
• Quartic quantum speedups for community detection

  2025cites this paper
• BitGC Made (More) Efficient

  2025cites this paper
• Improved Search-to-Decision Reduction for Random Local Functions

  2025influential citation
• SoK: On Shallow Weak PRFs A Common Symmetric Building Block for MPC Protocols

  2025cites this paper
• Spectral Refutations of Semirandom k-LIN over Larger Fields

  2025cites this paper
• Lossy Cryptography from Code-Based Assumptions Dense-Sparse LPN: A New Subexponentially Hard LPN Variant in SZK

  2025cites this paper
• Structured-Seed Local Pseudorandom Generators and their Applications

  2024cites this paper
• How to Simulate Random Oracles with Auxiliary Input

  2024cites this paper
• Quartic quantum speedups for planted inference

  2024influential citation
• Oblivious Transfer with Constant Computational Overhead

  2023cites this paper
• On the algebraic immunity—resiliency trade-off, implications for Goldreich’s pseudorandom generator

  2023cites this paper
• Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

  2023cites this paper
• Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

  2023cites this paper
• Towards Topology-Hiding Computation from Oblivious Transfer

  2023cites this paper
• Derandomization with Minimal Memory Footprint

  2023cites this paper
• Pseudorandom Strings from Pseudorandom Quantum States

  2023cites this paper
• Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments

  2023cites this paper
• New Baselines for Local Pseudorandom Number Generators by Field Extensions

  2023cites this paper
• Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality

  2023cites this paper
• Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs

  2022cites this paper
• Washington University Open Scholarship Washington University Open Scholarship

  2022cites this paper
• Learning Versus Pseudorandom Generators in Constant Parallel Time

  2022cites this paper
• Revisiting the Concrete Security of Goldreich’s Pseudorandom Generator

  2021cites this paper
• A Note on the Pseudorandomness of Low-Degree Polynomials over the Integers

  2021cites this paper
• From Local Pseudorandom Generators to Hardness of Learning

  2021cites this paper
• CSP-Completeness And Its Applications

  2020cites this paper
• Cryptographic Obfuscation: A Survey

  2020cites this paper
• Strongly refuting all semi-random Boolean CSPs

  2020cites this paper
• Indistinguishability obfuscation from well-founded assumptions

  2020cites this paper
• Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification

  2020cites this paper
• Non-interactive Zero-Knowledge in Pairing-Free Groups from Weaker Assumptions

  2020cites this paper
• Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG

  2020influential citation
• Simplifying Constructions and Assumptions for iO

  2019cites this paper
• Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification

  2019cites this paper
• Secure Multi-Party Computation and Privacy

  2019cites this paper
• Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation

  2018cites this paper
• Expander-Based Cryptography Meets Natural Proofs

  2018cites this paper
• University of Birmingham On the Complexity of Random Satisfiability Problems with Planted Solutions

  2018cites this paper
• Low Complexity Pseudorandom Generators and Indistinguishability Obfuscation

  2018cites this paper
• Random Growth Models

  2018cites this paper
• 18 : 2 Expander-Based Cryptography Meets Natural Proofs

  2018cites this paper
• Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

  2018cites this paper
• Extended Formulation Lower Bounds for Combinatorial Optimization

  2018cites this paper
• On the Concrete Security of Goldreich's Pseudorandom Generator

  2018cites this paper
• Minimizing the Complexity of Goldreich's Pseudorandom Generator

  2017cites this paper
• The Complexity of Public-Key Cryptography

  2017cites this paper
• Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs

  2017cites this paper
• 5Gen-C: Multi-input Functional Encryption and Program Obfuscation for Arithmetic Circuits

  2017cites this paper
• Sum of squares lower bounds for refuting any CSP

  2017cites this paper
• Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions

  2017cites this paper
• The Complexity of Public-Key Cryptography Boaz Barak April 27 , 2017

  2017cites this paper
• Advances in Cryptology – CRYPTO 2017

  2017cites this paper
• Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation from Degree-5 Multilinear Maps

  2017cites this paper
• Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation

  2017cites this paper
• Homomorphic Secret Sharing: Optimizations and Applications

  2017cites this paper
• On the Non-Existence of Blockwise 2-Local PRGs with Applications to Indistinguishability Obfuscation

  2017cites this paper
• Secure Arithmetic Computation with Constant Computational Overhead

  2017cites this paper
• Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs

  2017influential citation
• Algebraic attacks against random local functions and their countermeasures

  2016influential citation
• Lower bounds for CSP refutation by SDP hierarchies

  2016cites this paper
• On Refutation of Random Constraint Satisfaction Problems Thesis Proposal

  2016cites this paper
• Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings

  2016cites this paper
• Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes

  2016cites this paper
• Prediction with a short memory

  2016cites this paper
• Fast Pseudorandom Functions Based on Expander Graphs

  2016cites this paper
• Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges

  2015cites this paper
• Birmingham Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's

  2015cites this paper
• Sum of Squares Lower Bounds from Pairwise Independence

  2015cites this paper
• Spectral thresholds in the bipartite stochastic block model

  2015cites this paper
• C C ] 1 7 M ay 2 01 5 How to refute a random CSP

  2015cites this paper
• How to Refute a Random CSP

  2015cites this paper
• The Computational Benefit of Correlated Instances

  2015cites this paper
• Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's

  2014cites this paper
• Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets

  2014cites this paper
• Approximate resilience, monotonicity, and the complexity of agnostic learning

  2014cites this paper
• On the Complexity of Random Satisfiability Problems with Planted Solutions

  2013cites this paper
• Cryptographic Hardness of Random Local Functions

  2013cites this paper
• Attacks on Goldreich’s Pseudorandom Generators by Grouping and Solving

  year unknowncites this paper
• Locally Computable Arithmetic Pseudorandom Generators

  year unknowncites this paper
• WashU Scholarly Repository WashU Scholarly Repository

  year unknowncites this paper
• Bit-fixing Correlation Attacks on Goldreich’s Pseudorandom Generators

  year unknowncites this paper