Michael Alekhnovich

34 papers A* 13A 1B 1Journal 19

Year	Rank	Type	Title / Venue / Authors
2011	J	`jnl`	Lower Bounds for k-DNF Resolution on Random 3-CNFs. Comput. Complex. Michael Alekhnovich
2011	J	`jnl`	More on Average Case vs Approximation Complexity. Comput. Complex. Michael Alekhnovich
2011	J	`jnl`	Satisfiability, Branch-Width and Tseitin tautologies. Comput. Complex. Michael Alekhnovich, Alexander A. Razborov
2011	J	`jnl`	Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2009	J	`jnl`	Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
2008	J	`jnl`	Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. Michael Alekhnovich, Alexander A. Razborov
2008	J	`jnl`	The complexity of properly learning simple concept classes. J. Comput. Syst. Sci. Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi
2007	J	`jnl`	An Exponential Separation between Regular and General Resolution. Theory Comput. Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
2005	J	`jnl`	Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reason. Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2005	J	`jnl`	Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. IEEE Trans. Inf. Theory Michael Alekhnovich
2005	A*	`conf`	Lower bounds for k-DNF resolution on random 3-CNFs. STOC Michael Alekhnovich
2005	A	`conf`	Toward a Model for Backtracking and Dynamic Programming. CCC Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2005	A*	`conf`	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. STOC Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
2004	A*	`conf`	Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. ICALP Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2004	J	`jnl`	Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas Electron. Colloquium Comput. Complex. Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
2004	A*	`conf`	Learnability and Automatizability. FOCS Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi
2004	J	`jnl`	Linear Upper Bounds for Random Walk on Small Density Random 3CNFs Electron. Colloquium Comput. Complex. Michael Alekhnovich, Eli Ben-Sasson
2004	J	`jnl`	Mutilated chessboard problem is exponentially hard for resolution. Theor. Comput. Sci. Michael Alekhnovich
2004	J	`jnl`	Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2003	A*	`conf`	Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. FOCS Michael Alekhnovich, Eli Ben-Sasson
2003	A*	`conf`	More on Average Case vs Approximation Complexity. FOCS Michael Alekhnovich
2002	A*	`conf`	An exponential separation between regular and general resolution. STOC Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
2002	A*	`conf`	Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. FOCS Michael Alekhnovich
2002	A*	`conf`	Satisfiability, Branch-Width and Tseitin Tautologies. FOCS Michael Alekhnovich, Alexander A. Razborov
2002	J	`jnl`	Space Complexity in Propositional Calculus. SIAM J. Comput. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2001	J	`jnl`	An Exponential Separation between Regular and General Resolution Electron. Colloquium Comput. Complex. Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
2001	A*	`conf`	Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS Michael Alekhnovich, Alexander A. Razborov
2001	J	`jnl`	Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. J. Symb. Log. Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
2001	A*	`conf`	Resolution is Not Automatizable Unless W[P] is Tractable. FOCS Michael Alekhnovich, Alexander A. Razborov
2000	J	`jnl`	Pseudorandom Generators in Propositional Proof Complexity Electron. Colloquium Comput. Complex. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2000	A*	`conf`	Pseudorandom Generators in Propositional Proof Complexity. FOCS Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2000	A*	`conf`	Space complexity in propositional calculus. STOC Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
1999	J	`jnl`	Space Complexity in Propositional Calculus Electron. Colloquium Comput. Complex. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
1998	B	`conf`	Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi