×

zbMATH — the first resource for mathematics

Hirsch, Edward A.

Compute Distance To:
Author ID: hirsch.edward-a Recent zbMATH articles by "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

Publications by Year

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.68071
Dantsin, 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.68078
Gramm, 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.68098
Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry
17
2005
New worst-case upper bounds for SAT. Zbl 0960.03009
Hirsch, Edward A.
17
2000
A new algorithm for MAX-2-SAT. Zbl 0959.68047
Hirsch, Edward A.
17
2000
A complete public-key cryptosystem. Zbl 1158.94384
Grigoriev, Dima; Hirsch, Edward A.; Pervyshev, Konstantin
11
2009
MAX SAT approximation beyond the limits of polynomial-time approximation. Zbl 0990.03006
Dantsin, 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.68621
Hirsch, Edward A.; Kojevnikov, Arist
10
2005
Complexity of semialgebraic proofs. Zbl 1027.03044
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrij V.
9
2002
Algorithms for Sat and upper bounds on their complexity. Zbl 1074.68577
Vsemirnov, M. A.; Hirsch, E. A.; Dantsin, E. Ya.; Ivanov, S. V.
9
2001
SAT local search algorithms: Worst-case study. Zbl 0967.68146
Hirsch, Edward A.
8
2000
Complexity of semi-algebraic proofs. Zbl 1054.03035
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.
7
2002
Algorithms for SAT based on search in Hamming balls. Zbl 1122.68590
Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander
6
2004
Worst-case study of local search for MAX-\(k\)-SAT. Zbl 1051.68079
Hirsch, Edward A.
6
2003
Two new upper bounds for SAT. Zbl 0936.68113
Hirsch, Edward A.
6
1998
A fast deterministic algorithm for formulas that have many satisfying assignments. Zbl 0897.03043
Hirsch, Edward A.
6
1998
A feebly secure trapdoor function. Zbl 1248.94069
Hirsch, Edward A.; Nikolenko, Sergey I.
5
2009
Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. Zbl 1183.68305
Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander
5
2006
Solving Boolean satisfiability using local search guided by unit clause elimination. Zbl 1067.68643
Hirsch, Edward A.; Kojevnikov, Arist
5
2001
Deterministic algorithms for \(k\)-SAT based on covering codes and local search. Zbl 0973.68253
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Schöning, Uwe
4
2000
Feebly secure cryptographic primitives. Zbl 1262.94023
Hirsch, E. A.; Melanich, O.; Nikolenko, S. I.
3
2013
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Zbl 1261.03158
Hirsch, Edward A.; Itsykson, Dmitry; Monakhov, Ivan; Smal, Alexander
3
2012
Several notes on the power of Gomory-Chvátal cuts. Zbl 1101.03037
Hirsch, Edward A.; Kojevnikov, Arist
3
2006
Algebraic proof systems over formulas. Zbl 1044.68146
Grigoriev, Dima; Hirsch, Edward A.
3
2003
On the limits of gate elimination. Zbl 1393.68060
Golovnev, Alexander; Hirsch, Edward A.; Knop, Alexander; Kulikov, Alexander S.
2
2016
Optimal acceptors and optimal proof systems. Zbl 1284.03259
Hirsch, Edward A.
2
2010
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
Satisfiability certificates verifiable in subexponential time. Zbl 1331.68101
Dantsin, Evgeny; Hirsch, Edward A.
1
2011
On optimal heuristic randomized semidecision procedures, with application to proof complexity. Zbl 1230.03089
Hirsch, Edward A.; Itsykson, Dmitry
1
2010
An infinitely-often one-way function based on an average-case assumption. Zbl 1205.68164
Hirsch, E. A.; Itsykson, D. M.
1
2010
Theory of computational complexity. Part 9. Zbl 1065.68003
Hirsch, E. A. (ed.)
1
2004
Exponential lower bound for static semi-algebraic proofs. Zbl 1056.03037
Grigoriev, 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.92009
Cerf, R.; El Amri, M.; El Ouasdad, E. H.; Hirsch, E.
1
1999
On the limits of gate elimination. Zbl 1393.68060
Golovnev, Alexander; Hirsch, Edward A.; Knop, Alexander; Kulikov, Alexander S.
2
2016
Feebly secure cryptographic primitives. Zbl 1262.94023
Hirsch, E. A.; Melanich, O.; Nikolenko, S. I.
3
2013
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. Zbl 1261.03158
Hirsch, Edward A.; Itsykson, Dmitry; Monakhov, Ivan; Smal, Alexander
3
2012
Satisfiability certificates verifiable in subexponential time. Zbl 1331.68101
Dantsin, Evgeny; Hirsch, Edward A.
1
2011
Optimal acceptors and optimal proof systems. Zbl 1284.03259
Hirsch, Edward A.
2
2010
On optimal heuristic randomized semidecision procedures, with application to proof complexity. Zbl 1230.03089
Hirsch, Edward A.; Itsykson, Dmitry
1
2010
An infinitely-often one-way function based on an average-case assumption. Zbl 1205.68164
Hirsch, E. A.; Itsykson, D. M.
1
2010
A complete public-key cryptosystem. Zbl 1158.94384
Grigoriev, Dima; Hirsch, Edward A.; Pervyshev, Konstantin
11
2009
A feebly secure trapdoor function. Zbl 1248.94069
Hirsch, Edward A.; Nikolenko, Sergey I.
5
2009
Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. Zbl 1183.68305
Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander
5
2006
Several notes on the power of Gomory-Chvátal cuts. Zbl 1101.03037
Hirsch, Edward A.; Kojevnikov, Arist
3
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
UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. Zbl 1100.68621
Hirsch, Edward A.; Kojevnikov, Arist
10
2005
Algorithms for SAT based on search in Hamming balls. Zbl 1122.68590
Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander
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
Theory of computational complexity. Part 9. Zbl 1065.68003
Hirsch, E. A. (ed.)
1
2004
Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Zbl 1051.68078
Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter
24
2003
Worst-case study of local search for MAX-\(k\)-SAT. Zbl 1051.68079
Hirsch, Edward A.
6
2003
Algebraic proof systems over formulas. Zbl 1044.68146
Grigoriev, Dima; Hirsch, Edward A.
3
2003
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. Zbl 1061.68071
Dantsin, 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.03006
Dantsin, Evgeny; Gavrilovich, Michael; Hirsch, Edward A.; Konev, Boris
11
2002
Complexity of semialgebraic proofs. Zbl 1027.03044
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrij V.
9
2002
Complexity of semi-algebraic proofs. Zbl 1054.03035
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.
7
2002
Exponential lower bound for static semi-algebraic proofs. Zbl 1056.03037
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.
1
2002
Algorithms for Sat and upper bounds on their complexity. Zbl 1074.68577
Vsemirnov, 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.68643
Hirsch, Edward A.; Kojevnikov, Arist
5
2001
New worst-case upper bounds for SAT. Zbl 0960.03009
Hirsch, Edward A.
17
2000
A new algorithm for MAX-2-SAT. Zbl 0959.68047
Hirsch, Edward A.
17
2000
SAT local search algorithms: Worst-case study. Zbl 0967.68146
Hirsch, Edward A.
8
2000
Deterministic algorithms for \(k\)-SAT based on covering codes and local search. Zbl 0973.68253
Dantsin, 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.92009
Cerf, R.; El Amri, M.; El Ouasdad, E. H.; Hirsch, E.
1
1999
Two new upper bounds for SAT. Zbl 0936.68113
Hirsch, Edward A.
6
1998
A fast deterministic algorithm for formulas that have many satisfying assignments. Zbl 0897.03043
Hirsch, Edward A.
6
1998
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

Citations by Year