Special issue in memory of Misha Alekhnovich. Foreword

DOI10.1007/S00037-011-0032-2MaRDI QIDQ430839zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Biographies, obituaries, personalia, bibliographies (01A70)

Cites work

• scientific article; zbMATH DE number 5899257 (Why is no real title available?)
• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Hardness of approximating the closest vector problem with pre-processing
• Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Lower bounds for k-DNF resolution on random 3-CNFs
• Minimum propositional proof length is NP-hard to linearly approximate
• More on average case vs approximation complexity
• Mutilated chessboard problem is exponentially hard for resolution
• Pseudorandom Generators in Propositional Proof Complexity
• Resolution Is Not Automatizable Unless W[P] Is Tractable
• Satisfiability, branch-width and Tseitin tautologies
• Space Complexity in Propositional Calculus
• The complexity of properly learning simple concept classes
• Toward a model for backtracking and dynamic programming

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)