ask others

Michael Alekhnovich

Mikhail Alekhnovich – Mikhail Alecknovich – Миша Алехнович

> Home > Persons

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

see FAQ

What is the meaning of the colors in the publication lists?

2011
[j16]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cc/Alekhnovich11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cc/Alekhnovich11
Michael Alekhnovich:
Lower Bounds for k-DNF Resolution on Random 3-CNFs. Computational Complexity 20(4): 597-614 (2011)
[j15]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cc/AlekhnovichAT11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cc/AlekhnovichAT11
Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. Computational Complexity 20(4): 615-648 (2011)
[j14]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cc/AlekhnovichR11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cc/AlekhnovichR11
Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin tautologies. Computational Complexity 20(4): 649-678 (2011)
[j13]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cc/AlekhnovichBBIMP11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cc/AlekhnovichBBIMP11
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cc/AlekhnovichKKV11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cc/AlekhnovichKKV11
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cc/Alekhnovich11a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cc/Alekhnovich11a
Michael Alekhnovich:
More on Average Case vs Approximation Complexity. Computational Complexity 20(4): 755-786 (2011)

2000 – 2009

see FAQ

What is the meaning of the colors in the publication lists?

2009
[i7]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AlekhnovichBBIM09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AlekhnovichBBIM09
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/jcss/AlekhnovichBFKP08
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/jcss/AlekhnovichBFKP08
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/AlekhnovichR08
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/AlekhnovichR08
Michael Alekhnovich, Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008)
2007
[j8]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/AlekhnovichB07
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/AlekhnovichB07
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/toc/AlekhnovichJPU07
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/toc/AlekhnovichJPU07
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/jar/AlekhnovichHI05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/jar/AlekhnovichHI05
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/tit/Alekhnovich05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/tit/Alekhnovich05
Michael Alekhnovich:
Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. IEEE Trans. Information Theory 51(7): 2257-2265 (2005)
[c16]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/coco/AlekhnovichBBIMP05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/AlekhnovichBBIMP05
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]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/AlekhnovichKKV05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/AlekhnovichKKV05
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing. FOCS 2005: 216-225
[c14]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/Alekhnovich05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/Alekhnovich05
Michael Alekhnovich:
Lower bounds for k-DNF resolution on random 3-CNFs. STOC 2005: 251-256
[c13]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/AlekhnovichAT05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/AlekhnovichAT05
Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. STOC 2005: 294-303
2004
[j4]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/AlekhnovichBRW04
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/AlekhnovichBRW04
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]
- view
  - electronic edition via DOI
  - electronic edition @ wikidata.org
- export record
  dblp key:
  - journals/tcs/Alekhnovich04
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/tcs/Alekhnovich04
Michael Alekhnovich:
Mutilated chessboard problem is exponentially hard for resolution. Theor. Comput. Sci. 310(1-3): 513-525 (2004)
[c12]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/AlekhnovichBFKP04
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/AlekhnovichBFKP04
Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
Learnability and Automatizability. FOCS 2004: 621-630
[c11]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/icalp/AlekhnovichHI04
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/icalp/AlekhnovichHI04
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]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR04-016
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR04-016
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]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR04-041
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR04-041
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]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR04-117
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR04-117
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]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/Alekhnovich03
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/Alekhnovich03
Michael Alekhnovich:
More on Average Case vs Approximation Complexity. FOCS 2003: 298-307
[c9]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/AlekhnovichB03
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/AlekhnovichB03
Michael Alekhnovich, Eli Ben-Sasson:
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. FOCS 2003: 352-361
2002
[j2]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/AlekhnovichBRW02
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/AlekhnovichBRW02
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space Complexity in Propositional Calculus. SIAM J. Comput. 31(4): 1184-1211 (2002)
[c8]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/Alekhnovich02
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/Alekhnovich02
Michael Alekhnovich:
Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. FOCS 2002: 439-448
[c7]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/AlekhnovichR02
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/AlekhnovichR02
Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin Tautologies. FOCS 2002: 593-603
[c6]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/AlekhnovichJPU02
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/AlekhnovichJPU02
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An exponential separation between regular and general resolution. STOC 2002: 448-456
2001
[j1]
- view
  - electronic edition via DOI
  - electronic edition @ projecteuclid.org
- export record
  dblp key:
  - journals/jsyml/AlekhnovichBMP01
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/jsyml/AlekhnovichBMP01
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]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/AlekhnovichR01
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/AlekhnovichR01
Michael Alekhnovich, Alexander A. Razborov:
Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS 2001: 190-199
[c4]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/AlekhnovichR01a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/AlekhnovichR01a
Michael Alekhnovich, Alexander A. Razborov:
Resolution is Not Automatizable Unless W[P] is Tractable. FOCS 2001: 210-219
[i3]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR01-056
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR01-056
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]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/AlekhnovichBRW00
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/AlekhnovichBRW00
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53
[c2]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/AlekhnovichBRW00
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/AlekhnovichBRW00
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space complexity in propositional calculus. STOC 2000: 358-367
[i2]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR00-023
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR00-023
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

see FAQ

What is the meaning of the colors in the publication lists?

1999
[i1]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR99-040
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR99-040
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/mfcs/AlekhnovichBMP98
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/mfcs/AlekhnovichBMP98
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

see FAQ

maintained by

, founded at