Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
From MaRDI portal
Publication:1678752
DOI10.1007/s00224-013-9514-8zbMath1380.68199OpenAlexW2148342551MaRDI QIDQ1678752
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
Related Items (1)
Uses Software
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
