All reports by Author Michael Alekhnovich:

__
TR09-038
| 14th April 2009
__

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen#### Toward a Model for Backtracking and Dynamic Programming

__
TR04-117
| 1st December 2004
__

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis#### Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

__
TR04-041
| 18th May 2004
__

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson#### Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

__
TR04-016
| 3rd March 2004
__

Michael Alekhnovich, Eli Ben-Sasson#### Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

__
TR01-056
| 6th August 2001
__

Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart#### An Exponential Separation between Regular and General Resolution

__
TR00-023
| 11th May 2000
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Pseudorandom Generators in Propositional Proof Complexity

__
TR99-040
| 20th October 1999
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Space Complexity in Propositional Calculus

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

We propose a model called priority branching trees (pBT ) for backtracking and dynamic

programming algorithms. Our model generalizes both the priority model of Borodin, Nielson

and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence

spans a wide spectrum of algorithms. After witnessing the ...
more >>>

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

We prove strong nonapproximability results in this model for well-known problems such ... more >>>

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... more >>>

Michael Alekhnovich, Eli Ben-Sasson

We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time

of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the ...
more >>>

Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

This paper gives two distinct proofs of an exponential separation

between regular resolution and unrestricted resolution.

The previous best known separation between these systems was

quasi-polynomial.

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em

hard} for a propositional proof system $P$ if $P$ can not efficiently

prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for

{\em any} string $b\in\{0,1\}^m$. We consider a variety of

``combinatorial'' pseudorandom generators inspired by the

Nisan-Wigderson generator on the one hand, and ...
more >>>

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

We study space complexity in the framework of

propositional proofs. We consider a natural model analogous to

Turing machines with a read-only input tape, and such

popular propositional proof systems as Resolution, Polynomial

Calculus and Frege systems. We propose two different space measures,

corresponding to the maximal number of bits, ...
more >>>