Michael Alekhnovich
Mikhail Alekhnovich – Mikhail Alecknovich – Миша Алехнович
Person information
- affiliation: Institute for Advanced Study, Princeton, NJ, USA
- unicode name: Миша Алехнович
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – today
- 2011
- [j16]Michael Alekhnovich:
Lower Bounds for k-DNF Resolution on Random 3-CNFs. Computational Complexity 20(4): 597-614 (2011) - [j15]Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. Computational Complexity 20(4): 615-648 (2011) - [j14]Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin tautologies. Computational Complexity 20(4): 649-678 (2011) - [j13]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. Computational Complexity 20(4): 679-740 (2011) - [j12]Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing. Computational Complexity 20(4): 741-753 (2011) - [j11]Michael Alekhnovich:
More on Average Case vs Approximation Complexity. Computational Complexity 20(4): 755-786 (2011)
2000 – 2009
- 2009
- [i7]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen:
Toward a Model for Backtracking and Dynamic Programming. Electronic Colloquium on Computational Complexity (ECCC) 16: 38 (2009) - 2008
- [j10]Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
The complexity of properly learning simple concept classes. J. Comput. Syst. Sci. 74(1): 16-34 (2008) - [j9]Michael Alekhnovich, Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008) - 2007
- [j8]Mikhail Alekhnovich, Eli Ben-Sasson:
Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs. SIAM J. Comput. 36(5): 1248-1263 (2007) - [j7]Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution. Theory of Computing 3(1): 81-102 (2007) - 2005
- [j6]Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson:
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reasoning 35(1-3): 51-72 (2005) - [j5]Michael Alekhnovich:
Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. IEEE Trans. Information Theory 51(7): 2257-2265 (2005) - [c16]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. IEEE Conference on Computational Complexity 2005: 308-322 - [c15]Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing. FOCS 2005: 216-225 - [c14]
- [c13]Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. STOC 2005: 294-303 - 2004
- [j4]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. 34(1): 67-88 (2004) - [j3]Michael Alekhnovich:
Mutilated chessboard problem is exponentially hard for resolution. Theor. Comput. Sci. 310(1-3): 513-525 (2004) - [c12]Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
Learnability and Automatizability. FOCS 2004: 621-630 - [c11]Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson:
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. ICALP 2004: 84-96 - [i6]Michael Alekhnovich, Eli Ben-Sasson:
Linear Upper Bounds for Random Walk on Small Density Random 3CNFs. Electronic Colloquium on Computational Complexity (ECCC)(016) (2004) - [i5]Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson:
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Electronic Colloquium on Computational Complexity (ECCC)(041) (2004) - [i4]Mikhail Alecknovich, Sanjeev Arora, Iannis Tourlakis:
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. Electronic Colloquium on Computational Complexity (ECCC)(117) (2004) - 2003
- [c10]
- [c9]Michael Alekhnovich, Eli Ben-Sasson:
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. FOCS 2003: 352-361 - 2002
- [j2]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space Complexity in Propositional Calculus. SIAM J. Comput. 31(4): 1184-1211 (2002) - [c8]Michael Alekhnovich:
Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. FOCS 2002: 439-448 - [c7]Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin Tautologies. FOCS 2002: 593-603 - [c6]Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An exponential separation between regular and general resolution. STOC 2002: 448-456 - 2001
- [j1]Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi:
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. J. Symb. Log. 66(1): 171-191 (2001) - [c5]Michael Alekhnovich, Alexander A. Razborov:
Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS 2001: 190-199 - [c4]Michael Alekhnovich, Alexander A. Razborov:
Resolution is Not Automatizable Unless W[P] is Tractable. FOCS 2001: 210-219 - [i3]Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution. Electronic Colloquium on Computational Complexity (ECCC) 8(056) (2001) - 2000
- [c3]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53 - [c2]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space complexity in propositional calculus. STOC 2000: 358-367 - [i2]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. Electronic Colloquium on Computational Complexity (ECCC) 7(23) (2000)
1990 – 1999
- 1999
- [i1]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space Complexity in Propositional Calculus. Electronic Colloquium on Computational Complexity (ECCC)(40) (1999) - 1998
- [c1]Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi:
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS 1998: 176-184
Coauthor Index
last updated on 2019-01-09 01:16 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint