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
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
Satisfiability, branch-width and Tseitin tautologies	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

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Michael Alekhnovich