The complexity of inverting explicit Goldreich's function by DPLL algorithms
From MaRDI portal
Publication:1946844
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
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Uses Software
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
