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-8zbMATH Open1380.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
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
- Theory and Applications of Satisfiability Testing
- Title not available (Why is that?)
- Theory and Applications of Satisfiability Testing
- Hardness vs randomness
- Expander graphs and their applications
- Hard examples for resolution
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Candidate one-way functions based on expander graphs
- 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
- On the security of Goldreich's one-way function
- Pseudorandom Generators in Propositional Proof Complexity
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- On the one-way function candidate proposed by Goldreich
- Short proofs are narrow—resolution made simple
- Applications of SAT Solvers to Cryptanalysis of Hash Functions
- Lower bounds for myopic DPLL algorithms with a cut heuristic
Cited In (4)
- Resolution over linear equations modulo two
- 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
- The complexity of inversion of explicit Goldreich's function by DPLL algorithms
Uses Software
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)
