Special issue in memory of Misha Alekhnovich. Foreword
From MaRDI portal
Publication:430839
DOI10.1007/s00037-011-0032-2zbMath1241.01030OpenAlexW2099449032MaRDI QIDQ430839
Allan Borodin, Toniann Pitassi, Alexander A. 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
- More on average case vs approximation complexity
- Satisfiability, branch-width and Tseitin tautologies
- 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
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Mutilated chessboard problem is exponentially hard for resolution
- The complexity of properly learning simple concept classes
- Minimum propositional proof length is NP-hard to linearly approximate
- Space Complexity in Propositional Calculus
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
- Pseudorandom Generators in Propositional Proof Complexity
- Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
- Unnamed Item
- Unnamed Item
This page was built for publication: Special issue in memory of Misha Alekhnovich. Foreword
