Michael Alekhnovich

Available identifiers

zbMath Open alekhnovich.michaelMaRDI QIDQ430822

List of research outcomes

Publication	Date of Publication	Type
Space complexity in propositional calculus	2014-09-26	Paper
Satisfiability, branch-width and Tseitin tautologies	2012-06-26	Paper
More on average case vs approximation complexity	2012-06-26	Paper
Towards strong nonapproximability results in the Lovász-Schrijver hierarchy	2012-06-26	Paper
Hardness of approximating the closest vector problem with pre-processing	2012-06-26	Paper
Toward a model for backtracking and dynamic programming	2012-06-26	Paper
Lower bounds for \(k\)-DNF resolution on random 3-CNFs	2012-06-26	Paper
https://portal.mardi4nfdi.de/entity/Q3002781	2011-05-24	Paper
Lower bounds for k-DNF resolution on random 3-CNFs	2010-08-16	Paper
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy	2010-08-16	Paper
An exponential separation between regular and general resolution	2010-08-05	Paper
Resolution Is Not Automatizable Unless W[P] Is Tractable	2009-08-20	Paper
Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes	2008-12-21	Paper
Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs	2007-10-22	Paper
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas	2007-01-24	Paper
Automata, Languages and Programming	2005-08-24	Paper
Pseudorandom Generators in Propositional Proof Complexity	2005-02-21	Paper
Mutilated chessboard problem is exponentially hard for resolution	2004-10-27	Paper
Space Complexity in Propositional Calculus	2002-09-29	Paper
Minimum propositional proof length is NP-hard to linearly approximate	2002-01-21	Paper
https://portal.mardi4nfdi.de/entity/Q4218098	1999-03-02	Paper

Research outcomes over time

This page was built for person: Michael Alekhnovich