The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms

DOI10.1007/978-3-642-20712-9_11zbMath1332.68058OpenAlexW143547490MaRDI QIDQ3007623

Dmitry Itsykson, Dmitry Sokolov

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_11

zbMATH Keywords

lower boundsexpanderone-way functionDPLL algorithm

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Resolution over linear equations modulo two

Cites Work

• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Candidate One-Way Functions Based on Expander Graphs
• 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
• Short proofs are narrow—resolution made simple

This page was built for publication: The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms