Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms

DOI10.1007/s00224-013-9514-8zbMath1380.68199OpenAlexW2148342551MaRDI QIDQ1678752

Dmitry Itsykson

Publication date: 7 November 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9514-8

zbMATH Keywords

lower boundexpanderDPLLGoldreich's function

Mathematics Subject Classification ID

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

Related Items (1)

Resolution over linear equations modulo two

Uses Software

• MiniSat

Cites Work

• Unnamed Item
• On the security of Goldreich's one-way function
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Hardness vs randomness
• On the One-Way Function Candidate Proposed by Goldreich
• Candidate One-Way Functions Based on Expander Graphs
• Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic
• Expander graphs and their applications
• Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms
• 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: Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms