Edit Profile Hirsch, Edward A. Compute Distance To: Compute Author ID: hirsch.edward-a Published as: Hirsch, E.; Hirsch, E. A.; Hirsch, Edward; Hirsch, Edward A.; Hirsch, È. A. Documents Indexed: 55 Publications since 1998, including 4 Books all top 5 Co-Authors 9 single-authored 9 Grigor’ev, Dmitriĭ Yur’evich 8 Itsykson, Dmitry M. 6 Dantsin, Evgeny 4 Kojevnikov, Arist 4 Nikolenko, Sergey I. 3 Kulikov, Alexander S. 3 Pasechnik, Dmitrii V. 2 Alekhnovich, Michael 2 Goerdt, Andreas 2 Golovnev, Alexander 2 Karhumaki, Juhani 2 Knop, Alexander 2 Pin, Jean-Eric 2 Schöning, Uwe 2 Smal, Alexander V. 2 Wolpert, Alexander 1 Ablaev, Farid M. 1 Alekseev, Yaroslav 1 Bulatov, Andrei A. 1 Chernov, V. P. 1 Dantsin, E. Ya. 1 Davydov, G. V. 1 Gavrilovich, Michael 1 Gramm, Jens 1 Harrison, John 1 Kannan, Ravindran 1 Karavaev, Eh. F. 1 Kleinberg, Jon Michael 1 Konev, B. Yu. 1 Konev, Boris 1 Kossovsky, N. K. 1 Kuznetsov, Sergei O. 1 Lepistö, Arto 1 Lifschitz, Vladimir 1 Margenstern, Maurice 1 Matiyasevich, Yuriĭ Vladimirovich 1 Mayr, Ernst W. 1 Melanich, Olga 1 Mints, Grigoriĭ Efroimovich 1 Monakhov, Ivan 1 Niedermeier, Rolf 1 Nikolaenko, V. O. 1 Orevkov, V. P. 1 Papadimitriou, Christos Harilaos 1 Pervyshev, K. V. 1 Pervyshev, Konstantin 1 Pliuškevičius, Regimantas 1 Prilutskii, Michail 1 Raghavan, Prabhakar 1 Razborov, Aleksandr Aleksandrovich 1 Rossmanith, Peter 1 Semenov, Alexei Lvovich 1 Slisenko, A. O. 1 Slissenko, Anatol 1 Sokolev, Dmitry 1 Solov’ëv, Sergeĭ Vladimirovich 1 Tzameret, Iddo 1 Vasil’ev, Aleksandr Valer’evich 1 Vereshchagin, Nikolay K. 1 Vsemirnov, M. A. 1 Zaslavskii, Igor Dmitrievich all top 5 Serials 4 Theory of Computing Systems 4 Lecture Notes in Computer Science 3 Journal of Automated Reasoning 3 Journal of Mathematical Sciences (New York) 2 Discrete Applied Mathematics 2 Information Processing Letters 2 Theoretical Computer Science 2 Annals of Pure and Applied Logic 1 Russian Mathematical Surveys 1 Journal of Computer and System Sciences 1 St. Petersburg Mathematical Journal 1 Annals of Mathematics and Artificial Intelligence 1 Logic Journal of the IGPL 1 Moscow Mathematical Journal 1 Journal of Satisfiability, Boolean Modeling and Computation 1 Groups, Complexity, Cryptology all top 5 Fields 41 Computer science (68-XX) 17 Mathematical logic and foundations (03-XX) 9 Information and communication theory, circuits (94-XX) 7 General and overarching topics; collections (00-XX) 1 History and biography (01-XX) 1 Combinatorics (05-XX) 1 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH 33 Publications have been cited 245 times in 175 Documents Cited by ▼ Year ▼ A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe 38 2002 Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Zbl 1051.68078Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter 24 2003 Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1109.68098Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry 17 2005 New worst-case upper bounds for SAT. Zbl 0960.03009Hirsch, Edward A. 17 2000 A new algorithm for MAX-2-SAT. Zbl 0959.68047Hirsch, Edward A. 17 2000 A complete public-key cryptosystem. Zbl 1158.94384Grigoriev, Dima; Hirsch, Edward A.; Pervyshev, Konstantin 11 2009 MAX SAT approximation beyond the limits of polynomial-time approximation. Zbl 0990.03006Dantsin, Evgeny; Gavrilovich, Michael; Hirsch, Edward A.; Konev, Boris 11 2002 UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. Zbl 1100.68621Hirsch, Edward A.; Kojevnikov, Arist 10 2005 Complexity of semialgebraic proofs. Zbl 1027.03044Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrij V. 9 2002 Algorithms for Sat and upper bounds on their complexity. Zbl 1074.68577Vsemirnov, M. A.; Hirsch, E. A.; Dantsin, E. Ya.; Ivanov, S. V. 9 2001 SAT local search algorithms: Worst-case study. Zbl 0967.68146Hirsch, Edward A. 8 2000 Complexity of semi-algebraic proofs. Zbl 1054.03035Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V. 7 2002 Algorithms for SAT based on search in Hamming balls. Zbl 1122.68590Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander 6 2004 Worst-case study of local search for MAX-\(k\)-SAT. Zbl 1051.68079Hirsch, Edward A. 6 2003 Two new upper bounds for SAT. Zbl 0936.68113Hirsch, Edward A. 6 1998 A fast deterministic algorithm for formulas that have many satisfying assignments. Zbl 0897.03043Hirsch, Edward A. 6 1998 A feebly secure trapdoor function. Zbl 1248.94069Hirsch, Edward A.; Nikolenko, Sergey I. 5 2009 Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. Zbl 1183.68305Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander 5 2006 Solving Boolean satisfiability using local search guided by unit clause elimination. Zbl 1067.68643Hirsch, Edward A.; Kojevnikov, Arist 5 2001 Deterministic algorithms for \(k\)-SAT based on covering codes and local search. Zbl 0973.68253Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Schöning, Uwe 4 2000 Feebly secure cryptographic primitives. Zbl 1262.94023Hirsch, E. A.; Melanich, O.; Nikolenko, S. I. 3 2013 On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Zbl 1261.03158Hirsch, Edward A.; Itsykson, Dmitry; Monakhov, Ivan; Smal, Alexander 3 2012 Several notes on the power of Gomory-Chvátal cuts. Zbl 1101.03037Hirsch, Edward A.; Kojevnikov, Arist 3 2006 Algebraic proof systems over formulas. Zbl 1044.68146Grigoriev, Dima; Hirsch, Edward A. 3 2003 On the limits of gate elimination. Zbl 1393.68060Golovnev, Alexander; Hirsch, Edward A.; Knop, Alexander; Kulikov, Alexander S. 2 2016 Optimal acceptors and optimal proof systems. Zbl 1284.03259Hirsch, Edward A. 2 2010 Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1098.68052Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry 2 2004 Satisfiability certificates verifiable in subexponential time. Zbl 1331.68101Dantsin, Evgeny; Hirsch, Edward A. 1 2011 On optimal heuristic randomized semidecision procedures, with application to proof complexity. Zbl 1230.03089Hirsch, Edward A.; Itsykson, Dmitry 1 2010 An infinitely-often one-way function based on an average-case assumption. Zbl 1205.68164Hirsch, E. A.; Itsykson, D. M. 1 2010 Theory of computational complexity. Part 9. Zbl 1065.68003Hirsch, E. A. (ed.) 1 2004 Exponential lower bound for static semi-algebraic proofs. Zbl 1056.03037Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V. 1 2002 Nonlinear analysis of epileptic seizures. I: Correlation-dimension measurements for absence epilepsy and near-periodic signals. Zbl 0920.92009Cerf, R.; El Amri, M.; El Ouasdad, E. H.; Hirsch, E. 1 1999 On the limits of gate elimination. Zbl 1393.68060Golovnev, Alexander; Hirsch, Edward A.; Knop, Alexander; Kulikov, Alexander S. 2 2016 Feebly secure cryptographic primitives. Zbl 1262.94023Hirsch, E. A.; Melanich, O.; Nikolenko, S. I. 3 2013 On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Zbl 1261.03158Hirsch, Edward A.; Itsykson, Dmitry; Monakhov, Ivan; Smal, Alexander 3 2012 Satisfiability certificates verifiable in subexponential time. Zbl 1331.68101Dantsin, Evgeny; Hirsch, Edward A. 1 2011 Optimal acceptors and optimal proof systems. Zbl 1284.03259Hirsch, Edward A. 2 2010 On optimal heuristic randomized semidecision procedures, with application to proof complexity. Zbl 1230.03089Hirsch, Edward A.; Itsykson, Dmitry 1 2010 An infinitely-often one-way function based on an average-case assumption. Zbl 1205.68164Hirsch, E. A.; Itsykson, D. M. 1 2010 A complete public-key cryptosystem. Zbl 1158.94384Grigoriev, Dima; Hirsch, Edward A.; Pervyshev, Konstantin 11 2009 A feebly secure trapdoor function. Zbl 1248.94069Hirsch, Edward A.; Nikolenko, Sergey I. 5 2009 Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. Zbl 1183.68305Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander 5 2006 Several notes on the power of Gomory-Chvátal cuts. Zbl 1101.03037Hirsch, Edward A.; Kojevnikov, Arist 3 2006 Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1109.68098Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry 17 2005 UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. Zbl 1100.68621Hirsch, Edward A.; Kojevnikov, Arist 10 2005 Algorithms for SAT based on search in Hamming balls. Zbl 1122.68590Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander 6 2004 Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Zbl 1098.68052Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry 2 2004 Theory of computational complexity. Part 9. Zbl 1065.68003Hirsch, E. A. (ed.) 1 2004 Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Zbl 1051.68078Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter 24 2003 Worst-case study of local search for MAX-\(k\)-SAT. Zbl 1051.68079Hirsch, Edward A. 6 2003 Algebraic proof systems over formulas. Zbl 1044.68146Grigoriev, Dima; Hirsch, Edward A. 3 2003 A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe 38 2002 MAX SAT approximation beyond the limits of polynomial-time approximation. Zbl 0990.03006Dantsin, Evgeny; Gavrilovich, Michael; Hirsch, Edward A.; Konev, Boris 11 2002 Complexity of semialgebraic proofs. Zbl 1027.03044Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrij V. 9 2002 Complexity of semi-algebraic proofs. Zbl 1054.03035Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V. 7 2002 Exponential lower bound for static semi-algebraic proofs. Zbl 1056.03037Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V. 1 2002 Algorithms for Sat and upper bounds on their complexity. Zbl 1074.68577Vsemirnov, M. A.; Hirsch, E. A.; Dantsin, E. Ya.; Ivanov, S. V. 9 2001 Solving Boolean satisfiability using local search guided by unit clause elimination. Zbl 1067.68643Hirsch, Edward A.; Kojevnikov, Arist 5 2001 New worst-case upper bounds for SAT. Zbl 0960.03009Hirsch, Edward A. 17 2000 A new algorithm for MAX-2-SAT. Zbl 0959.68047Hirsch, Edward A. 17 2000 SAT local search algorithms: Worst-case study. Zbl 0967.68146Hirsch, Edward A. 8 2000 Deterministic algorithms for \(k\)-SAT based on covering codes and local search. Zbl 0973.68253Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Schöning, Uwe 4 2000 Nonlinear analysis of epileptic seizures. I: Correlation-dimension measurements for absence epilepsy and near-periodic signals. Zbl 0920.92009Cerf, R.; El Amri, M.; El Ouasdad, E. H.; Hirsch, E. 1 1999 Two new upper bounds for SAT. Zbl 0936.68113Hirsch, Edward A. 6 1998 A fast deterministic algorithm for formulas that have many satisfying assignments. Zbl 0897.03043Hirsch, Edward A. 6 1998 all cited Publications top 5 cited Publications all top 5 Cited by 256 Authors 15 Hirsch, Edward A. 10 Itsykson, Dmitry M. 7 Nikolenko, Sergey I. 7 Paschos, Vangelis Th. 6 Tamaki, Suguru 5 Mastrolilli, Monaldo 5 Seto, Kazuhisa 4 Applebaum, Benny 4 Kulikov, Alexander S. 4 Kurpisz, Adam 4 Leppänen, Samuli 3 Alekhnovich, Michael 3 Anjos, Miguel F. 3 Dantsin, Evgeny 3 Escoffier, Bruno 3 Fernau, Henning 3 Fomin, Fedor V. 3 Gaspers, Serge 3 Golovnev, Alexander 3 Impagliazzo, Russell 3 Kojevnikov, Arist 3 Prestwich, Steven D. 3 Shen, Haiou 3 Smal, Alexander V. 3 Sorkin, Gregory B. 3 Teruyama, Junichi 3 Tourniaire, Emeric 3 Tzameret, Iddo 3 Zhang, Hantao 2 Borodin, Allan B. 2 Brueggemann, Tobias 2 Cardinal, Jean-Paul 2 Chen, Jian-er 2 Dantchev, Stefan Stoyanov 2 Della Croce, Federico 2 Gao, Zongsheng 2 Grandoni, Fabrizio 2 Grigor’ev, Dmitriĭ Yur’evich 2 Huang, Ping 2 Iwama, Kazuo 2 Järvisalo, Matti 2 Jonsson, Peter A. 2 Junttila, Tommi A. 2 Kern, Walter 2 Krajíček, Jan 2 Kullmann, Oliver 2 Lauria, Massimo 2 Martin, Barnaby D. 2 Miles, Eric 2 Nagao, Atsuki 2 Niedermeier, Rolf 2 Nordström, Jakob 2 Nummenpalo, Jerri 2 Paturi, Ramamohan 2 Pitassi, Toniann 2 Porschen, Stefan 2 Rhodes, Mark 2 Rossmanith, Peter 2 Sakai, Takayuki 2 Skvortsov, Evgeny S. 2 Sokolev, Dmitry 2 Speckenmeyer, Ewald 2 Szeider, Stefan 2 Viola, Emanuele 2 Welzl, Emo 2 Williams, Richard Ryan 2 Yamamoto, Masaki 2 Zhou, Guangyan 2 Zhou, Yuren 1 Abboud, Amir 1 Adelshin, Alexander 1 Al-Yahya, Tasniem Nasser 1 Atserias, Albert 1 Bach, Eric 1 Baron, Joshua 1 Beame, Paul W. 1 Beigel, Richard 1 Bhalla, Ateet 1 Binkele-Raible, Daniel 1 Bliznets, Ivan A. 1 Bogdanov, Andrej 1 Bonacina, Ilario 1 Branković, Ljiljana 1 Bressan, Stéphane 1 Brglez, Franc 1 Bro Miltersen, Peter 1 Bryant, Randal E. 1 Buresh-Oppenheim, Joshua 1 Buss, Samuel R. 1 Bykova, Valentina Vladimirovna 1 Cai, Zhijie 1 Calabro, Chris 1 Chapdelaine, Philippe 1 Chrabakh, Wahid 1 Cieliebak, Mark 1 Cook, James R. 1 Creignou, Nadia 1 Crespi Reghizzi, Stefano 1 Culberson, Joseph C. 1 Cygan, Marek ...and 156 more Authors all top 5 Cited in 51 Serials 21 Theoretical Computer Science 12 Discrete Applied Mathematics 10 Journal of Mathematical Sciences (New York) 9 Information Processing Letters 8 Annals of Mathematics and Artificial Intelligence 7 Algorithmica 7 Computational Complexity 6 Annals of Pure and Applied Logic 4 Journal of Computer and System Sciences 4 Journal of Discrete Algorithms 3 Journal of Automated Reasoning 3 Mathematical Programming. Series A. Series B 3 Theory of Computing Systems 3 Journal of Combinatorial Optimization 2 Artificial Intelligence 2 SIAM Journal on Computing 2 Operations Research Letters 2 Journal of Symbolic Computation 2 Information and Computation 2 Journal of Cryptology 2 Annals of Operations Research 2 Discrete Optimization 2 Mathematics in Computer Science 1 Journal of Mathematical Physics 1 Problems of Information Transmission 1 Mathematics of Operations Research 1 European Journal of Combinatorics 1 Optimization 1 Journal of Computer Science and Technology 1 Japan Journal of Industrial and Applied Mathematics 1 Discrete Mathematics and Applications 1 Journal of Global Optimization 1 Pattern Recognition 1 SIAM Journal on Optimization 1 International Journal of Bifurcation and Chaos in Applied Sciences and Engineering 1 Cybernetics and Systems Analysis 1 St. Petersburg Mathematical Journal 1 Journal of Heuristics 1 Constraints 1 New Journal of Physics 1 RAIRO. Theoretical Informatics and Applications 1 Journal of Mathematical Logic 1 RAIRO. Operations Research 1 ACM Transactions on Computational Logic 1 4OR 1 1 Operational Research. An International Journal 1 Science China. Information Sciences 1 ACM Transactions on Computation Theory 1 Journal of Mathematical Modelling and Algorithms in Operations Research 1 Prikladnaya Diskretnaya Matematika all top 5 Cited in 18 Fields 133 Computer science (68-XX) 32 Operations research, mathematical programming (90-XX) 25 Information and communication theory, circuits (94-XX) 24 Mathematical logic and foundations (03-XX) 19 Combinatorics (05-XX) 6 Number theory (11-XX) 2 History and biography (01-XX) 2 Quantum theory (81-XX) 2 Biology and other natural sciences (92-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Commutative algebra (13-XX) 1 Associative rings and algebras (16-XX) 1 Group theory and generalizations (20-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Systems theory; control (93-XX) Citations by Year