Special issue in memory of Misha Alekhnovich. Foreword
From MaRDI portal
Publication:430839
DOI10.1007/S00037-011-0032-2zbMATH Open1241.01030OpenAlexW2099449032MaRDI QIDQ430839FDOQ430839
Authors: Allan Borodin, Toniann Pitassi, Alexander Razborov 
Publication date: 26 June 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0032-2
Cites Work
- Satisfiability, branch-width and Tseitin tautologies
- Pseudorandom Generators in Propositional Proof Complexity
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
- Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
- Minimum propositional proof length is NP-hard to linearly approximate
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- Title not available (Why is that?)
- Mutilated chessboard problem is exponentially hard for resolution
- The complexity of properly learning simple concept classes
- Title not available (Why is that?)
- Space Complexity in Propositional Calculus
- More on average case vs approximation complexity
- Hardness of approximating the closest vector problem with pre-processing
- Toward a model for backtracking and dynamic programming
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
This page was built for publication: Special issue in memory of Misha Alekhnovich. Foreword
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q430839)
