The complexity of inverting explicit Goldreich's function by DPLL algorithms

DOI10.1007/s10958-012-1105-8zbMath1261.68171OpenAlexW2752096583MaRDI QIDQ1946844

D. O. Sokolov, Dmitry Itsykson

Publication date: 9 April 2013

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-012-1105-8

zbMATH Keywords

complexityexpanderpredicateinvertingGoldreich's functionarityDPLL algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On the One-Way Function Candidate Proposed by Goldreich

Uses Software

• MiniSat

Cites Work

• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• One way functions and pseudorandom generators
• Hardness vs randomness
• Expander graphs and their applications
• Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms
• Randomness conductors and constant-degree lossless expanders
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• Hard examples for resolution
• Short proofs are narrow—resolution made simple
• Pseudorandom Generators in Propositional Proof Complexity
• Theory and Applications of Satisfiability Testing
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing
• Applications of SAT Solvers to Cryptanalysis of Hash Functions

This page was built for publication: The complexity of inverting explicit Goldreich's function by DPLL algorithms