×

zbMATH — the first resource for mathematics

Alekhnovich, Michael

Compute Distance To:
Author ID: alekhnovich.michael Recent zbMATH articles by "Alekhnovich, Michael"
Published as: Alekhnovich, Michael; Alekhnovich, Mikhail
Documents Indexed: 21 Publications since 1998

Publications by Year

Citations contained in zbMATH Open

21 Publications have been cited 225 times in 172 Documents Cited by Year
Space complexity in propositional calculus. Zbl 1004.03047
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
34
2002
Resolution is not automatizable unless W[P] is tractable. Zbl 1169.03044
Alekhnovich, Michael; Razborov, Alexander A.
32
2008
Pseudorandom generators in propositional proof complexity. Zbl 1096.03070
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
26
2004
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1109.68098
Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry
17
2005
Toward a model for backtracking and dynamic programming. Zbl 1252.68130
Alekhnovich, Michael; Borodin, Allan; Buresh-Oppenheim, Joshua; Impagliazzo, Russell; Magen, Avner; Pitassi, Toniann
16
2011
Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182
Alekhnovich, Michael; Razborov, Alexander
14
2011
Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes. Zbl 1282.94101
Alekhnovich, Michael
14
2005
Minimum propositional proof length is NP-hard to linearly approximate. Zbl 0977.03032
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
11
2001
Minimum propositional proof length is NP-hard to linearly approximate (extended abstract). Zbl 0911.03028
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
8
1998
More on average case vs approximation complexity. Zbl 1242.68109
Alekhnovich, Michael
7
2011
Linear upper bounds for random walk on small density random 3-CNFs. Zbl 1124.68041
Alekhnovich, Mikhail; Ben-Sasson, Eli
7
2006
Mutilated chessboard problem is exponentially hard for resolution. Zbl 1071.68028
Alekhnovich, Michael
6
2004
An exponential separation between regular and general resolution. Zbl 1192.03039
Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair
6
2002
An exponential separation between regular and general resolution. Zbl 1213.68303
Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair
5
2007
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. Zbl 1192.90123
Alekhnovich, Mikhail; Arora, Sanjeev; Tourlakis, Iannis
5
2005
Space complexity in propositional calculus. Zbl 1296.03032
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
5
2000
Lower bounds for \(k\)-DNF resolution on random 3-CNFs (extended abstract). Zbl 1192.68307
Alekhnovich, Michael
4
2005
Hardness of approximating the closest vector problem with pre-processing. Zbl 1252.68132
Alekhnovich, Mikhail; Khot, Subhash A.; Kindler, Guy; Vishnoi, Nisheeth K.
3
2011
Towards strong nonapproximability results in the Lovász-Schrijver hierarchy. Zbl 1252.68131
Alekhnovich, Mikhail; Arora, Sanjeev; Tourlakis, Iannis
2
2011
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1098.68052
Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry
2
2004
Lower bounds for \(k\)-DNF resolution on random 3-CNFs. Zbl 1252.68129
Alekhnovich, Michael
1
2011
Toward a model for backtracking and dynamic programming. Zbl 1252.68130
Alekhnovich, Michael; Borodin, Allan; Buresh-Oppenheim, Joshua; Impagliazzo, Russell; Magen, Avner; Pitassi, Toniann
16
2011
Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182
Alekhnovich, Michael; Razborov, Alexander
14
2011
More on average case vs approximation complexity. Zbl 1242.68109
Alekhnovich, Michael
7
2011
Hardness of approximating the closest vector problem with pre-processing. Zbl 1252.68132
Alekhnovich, Mikhail; Khot, Subhash A.; Kindler, Guy; Vishnoi, Nisheeth K.
3
2011
Towards strong nonapproximability results in the Lovász-Schrijver hierarchy. Zbl 1252.68131
Alekhnovich, Mikhail; Arora, Sanjeev; Tourlakis, Iannis
2
2011
Lower bounds for \(k\)-DNF resolution on random 3-CNFs. Zbl 1252.68129
Alekhnovich, Michael
1
2011
Resolution is not automatizable unless W[P] is tractable. Zbl 1169.03044
Alekhnovich, Michael; Razborov, Alexander A.
32
2008
An exponential separation between regular and general resolution. Zbl 1213.68303
Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair
5
2007
Linear upper bounds for random walk on small density random 3-CNFs. Zbl 1124.68041
Alekhnovich, Mikhail; Ben-Sasson, Eli
7
2006
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1109.68098
Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry
17
2005
Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes. Zbl 1282.94101
Alekhnovich, Michael
14
2005
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. Zbl 1192.90123
Alekhnovich, Mikhail; Arora, Sanjeev; Tourlakis, Iannis
5
2005
Lower bounds for \(k\)-DNF resolution on random 3-CNFs (extended abstract). Zbl 1192.68307
Alekhnovich, Michael
4
2005
Pseudorandom generators in propositional proof complexity. Zbl 1096.03070
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
26
2004
Mutilated chessboard problem is exponentially hard for resolution. Zbl 1071.68028
Alekhnovich, Michael
6
2004
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1098.68052
Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry
2
2004
Space complexity in propositional calculus. Zbl 1004.03047
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
34
2002
An exponential separation between regular and general resolution. Zbl 1192.03039
Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair
6
2002
Minimum propositional proof length is NP-hard to linearly approximate. Zbl 0977.03032
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
11
2001
Space complexity in propositional calculus. Zbl 1296.03032
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
5
2000
Minimum propositional proof length is NP-hard to linearly approximate (extended abstract). Zbl 0911.03028
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
8
1998
all top 5

Cited by 266 Authors

11 Lauria, Massimo
8 Galesi, Nicola
8 Nordström, Jakob
8 Razborov, Aleksandr Aleksandrovich
6 Alekhnovich, Michael
6 Atserias, Albert
6 Borodin, Allan B.
6 Itsykson, Dmitry M.
5 Beyersdorff, Olaf
5 Impagliazzo, Russell
5 Pitassi, Toniann
5 Subramani, Krishnan
5 Szeider, Stefan
5 Thapen, Neil
4 Applebaum, Benny
4 Krajíček, Jan
4 Tzameret, Iddo
3 Bonacina, Ilario
3 Buss, Samuel R.
3 Downey, Rodney Graham
3 Esteban, Juan Luis
3 Filmus, Yuval
3 Johannsen, Jan
3 Mathieu, Claire
3 Mömke, Tobias
3 Müller, Moritz
3 Ordyniak, Sebastian
3 Pudlák, Pavel
3 Nielsen, Johan Sebastian Rosenkilde
3 Torán, Jacobo
3 Vinyals, Marc
2 Alechina, Natasha
2 Andrés Montoya, Juan
2 Beckmann, Arnold
2 Bogdanov, Andrej
2 Bonet, Maria Luisa
2 Boyar, Joan F.
2 Buresh-Oppenheim, Joshua
2 Davis, Sashka
2 De Oliveira Oliveira, Mateus
2 Dinur, Irit
2 Dvir, Zeev
2 Feldman, Vitaly
2 Fischer, Eldar
2 Gaspers, Serge
2 Hirsch, Edward A.
2 Hoffmann, Jan-Philipp
2 Janota, Mikoláš
2 Kindler, Guy
2 Kurpisz, Adam
2 Larsen, Kim Skak
2 Logan, Brian
2 Mastrolilli, Monaldo
2 O’Sullivan, Michael E.
2 Pich, Ján
2 Puchinger, Sven
2 Raz, Ran
2 Safra, Shmuel
2 Sokolev, Dmitry
2 Verdugo, Víctor
2 Wiese, Andreas
2 Wigderson, Avi
2 Zhou, Yuren
1 Albore, Alexandre
1 Alekhnovich, Misha
1 Alwen, Joël
1 Amjad, Hasan
1 Angelopoulos, Spyros
1 Arora, Sanjeev
1 Bäckström, Christer
1 Baron, Joshua
1 Beame, Paul W.
1 Beck, Chris
1 Beelen, Pieter Hendrik Turdus
1 Ben-Sasson, Eli
1 Bennett, Patrick
1 Berkholz, Christoph
1 Bernstein, Daniel Julius
1 Berthomieu, Jérémy
1 Bertoli, Piergiorgio
1 Biere, Armin
1 Blinkhorn, Joshua
1 Bompadre, Agustín
1 Bonnet, Edouard
1 Borodin, A. I.
1 Bossert, Martin
1 Brander, Kristian
1 Braverman, Mark
1 Buss, Sam
1 Chandrasekaran, Ramaswamy
1 Chen, Li-Hsuan
1 Chen, Wenbin
1 Chinchani, Ramkumar
1 Chlamtac, Eden
1 Clemente, Lorenzo
1 Cohn, Henry Lee
1 Coja-Oghlan, Amin
1 Connamacher, Harold S.
1 Cook, James R.
1 Crespi Reghizzi, Stefano
...and 166 more Authors
all top 5

Cited in 50 Serials

16 Theoretical Computer Science
10 SIAM Journal on Computing
10 Computational Complexity
9 Information Processing Letters
9 Algorithmica
7 Information and Computation
7 Theory of Computing Systems
6 Journal of Computer and System Sciences
6 Annals of Pure and Applied Logic
4 Journal of Automated Reasoning
3 Artificial Intelligence
3 Discrete Applied Mathematics
3 Journal of Symbolic Computation
3 Mathematical Logic Quarterly (MLQ)
3 Journal of Combinatorial Optimization
3 ACM Transactions on Computational Logic
2 Journal of Cryptology
2 Designs, Codes and Cryptography
2 Archive for Mathematical Logic
2 Applicable Algebra in Engineering, Communication and Computing
2 Advances in Mathematics of Communications
2 Logical Methods in Computer Science
1 Acta Informatica
1 Problems of Information Transmission
1 Studia Logica
1 Synthese
1 Combinatorica
1 SIAM Journal on Discrete Mathematics
1 Formal Aspects of Computing
1 Random Structures & Algorithms
1 MSCS. Mathematical Structures in Computer Science
1 Journal of Global Optimization
1 Pattern Recognition
1 Bulletin of the American Mathematical Society. New Series
1 Mathematical Programming. Series A. Series B
1 Journal of Mathematical Sciences (New York)
1 The Journal of Artificial Intelligence Research (JAIR)
1 The Bulletin of Symbolic Logic
1 Constraints
1 Journal of Scheduling
1 Journal of the ACM
1 Annals of Mathematics. Second Series
1 RAIRO. Theoretical Informatics and Applications
1 Journal of Mathematical Logic
1 Journal of Discrete Algorithms
1 Journal of Statistical Mechanics: Theory and Experiment
1 Discrete Optimization
1 Algorithms
1 Computer Science Review
1 ACM Transactions on Computation Theory

Citations by Year