The complexity of inverting explicit Goldreich's function by DPLL algorithms
type: Item
instance of: scholarly article
title: The complexity of inverting explicit Goldreich's function by DPLL algorithms
zbMATH Open document ID: 1261.68171
author: D. O. Sokolov
author: Dmitry Itsykson
published in: Journal of Mathematical Sciences (New York)
publication date: 2013-04-09T00:00:00Z
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6152345
zbMATH Keywords: Goldreich's function
zbMATH Keywords: complexity
zbMATH Keywords: DPLL algorithms
zbMATH Keywords: inverting
zbMATH Keywords: predicate
zbMATH Keywords: arity
zbMATH Keywords: expander
describes a project that uses: MiniSat
MaRDI profile type: Publication
full work available at URL: s10958-012-1105-8
OpenAlex ID: W2752096583
cites work: Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
cites work: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
cites work: One way functions and pseudorandom generators
cites work: Short proofs are narrow—resolution made simple
cites work: Expander graphs and their applications
cites work: Hardness vs randomness
cites work: Applications of SAT Solvers to Cryptanalysis of Hash Functions
cites work: Theory and Applications of Satisfiability Testing
cites work: Pseudorandom Generators in Propositional Proof Complexity
cites work: Hard examples for resolution
cites work: A machine program for theorem-proving
cites work: A Computing Procedure for Quantification Theory
cites work: Randomness conductors and constant-degree lossless expanders
cites work: Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms
DOI: 10.1007/S10958-012-1105-8
description: scientific article; zbMATH DE number 6152345