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

DOI10.1007/S00224-013-9514-8zbMATH1380.68199OpenAlexW2148342551MaRDI QIDQ1678752FDOQ1678752

Authors 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)

Recommendations

• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• The complexity of inversion of explicit Goldreich's function by DPLL algorithms
• The complexity of inverting explicit Goldreich's function by DPLL algorithms
• On the one-way function candidate proposed by Goldreich
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms

Cites work

• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Applications of SAT Solvers to Cryptanalysis of Hash Functions
• Candidate one-way functions based on expander graphs
• Expander graphs and their applications
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• Hard examples for resolution
• Hardness vs randomness
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Lower bounds for myopic DPLL algorithms with a cut heuristic
• On the one-way function candidate proposed by Goldreich
• On the security of Goldreich's one-way function
• Pseudorandom Generators in Propositional Proof Complexity
• Short proofs are narrow—resolution made simple
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

Cited in

(4)

• Resolution over linear equations modulo two
• The complexity of inversion of explicit Goldreich's function by DPLL algorithms
• The complexity of inverting explicit Goldreich's function by DPLL algorithms
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms

Describes a project that uses

Uses Software

• MiniSat

This page was built for publication: Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1678752)