• 625 Citations
  • 16 h-Index
19972018

Research output per year

If you made any changes in Pure these will be visible here soon.

Research Output

  • 625 Citations
  • 16 h-Index
  • 20 статья
  • 14 статья в сборнике материалов конференции
  • 4 статья в журнале по материалам конференции
  • 1 глава/раздел

A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function

Find, M. G., Golovnev, A., Hirsch, E. A. & Kulikov, A. S., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 89-98 10 p. 7782921. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

Research outputpeer-review

10 Citations (Scopus)

A complete public-key cryptosystem

Grigoriev, D., Hirsch, E. A. & Pervyshev, K., 1 Apr 2009, In : Groups, Complexity, Cryptology. 1, 1, p. 1-12 12 p.

Research output

11 Citations (Scopus)

A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search

Dantsin, E., Goerdt, A., Hirsch, E. A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P. & Schöning, U., 23 Oct 2002, In : Theoretical Computer Science. 289, 1, p. 69-83 15 p.

Research output

Open Access
118 Citations (Scopus)

A feebly secure trapdoor function

Hirsch, E. A. & Nikolenko, S. I., 29 Oct 2009, Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. p. 129-142 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5675 LNCS).

Research outputpeer-review

5 Citations (Scopus)

Algebraic proof systems over formulas

Grigoriev, D. & Hirsch, E. A., 28 Jun 2003, In : Theoretical Computer Science. 303, 1, p. 83-102 20 p.

Research output

Open Access
16 Citations (Scopus)
16 Citations (Scopus)

A new algorithm for MAX-2-SAT

Hirsch, E. A., 1 Jan 2000, STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings. Reichel, H. & Tison, S. (eds.). Springer Nature, p. 65-73 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1770).

Research outputpeer-review

25 Citations (Scopus)
Open Access
1 Citation (Scopus)

An infinitely-often one-way function based on an average-case assumption

Hirsch, E. A. & Itsykson, D. M., 28 Jul 2008, Logic, Language, Information and Computation - 15th International Workshop, WoLLIC 2008, Proceedings. p. 208-217 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5110 LNAI).

Research outputpeer-review

Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms

Dantsin, E., Hirsch, E. A. & Wolpert, A., 1 Jan 2006, Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Nature, p. 60-68 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 3998 LNCS).

Research outputpeer-review

9 Citations (Scopus)

Complexity of semi-algebraic proofs

Grigoriev, D., Hirsch, E. A. & Pasechnik, D. V., 1 Jan 2002, STACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Ferreira, A. & Alt, H. (eds.). Springer Nature, p. 419-430 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2285).

Research outputpeer-review

24 Citations (Scopus)

Deterministic algorithms for k-SAT based on covering codes and local search

Dantsin, E., Goerdt, A., Hirsch, E. A. & Schöning, U., 1 Jan 2000, Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings. Montanari, U., Welzl, E. & Rolim, J. D. P. (eds.). Springer Nature, p. 236-247 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1853).

Research outputpeer-review

24 Citations (Scopus)

Exponential lower bound for static semi-algebraic proofs

Grigoriev, D., Hirsch, E. A. & Pasechnik, D. V., 1 Dec 2002, Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. p. 257-268 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2380 LNCS).

Research outputpeer-review

4 Citations (Scopus)

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

Alekhnovich, M., Hirsch, E. A. & Itsykson, D., 1 Oct 2005, In : Journal of Automated Reasoning. 35, 1-3, p. 51-72 22 p.

Research output

41 Citations (Scopus)
4 Citations (Scopus)

Local search algorithms for SAT: Worst-case analysis

Hirsch, E. A., 1 Jan 1998, Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. Arnborg, S. & Ivansson, L. (eds.). Springer Nature, p. 246-254 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1432).

Research outputpeer-review

2 Citations (Scopus)

MAX SAT approximation beyond the limits of polynomial-time approximation

Dantsin, E., Gavrilovich, M., Hirsch, E. A. & Konev, B., 27 Dec 2001, In : Annals of Pure and Applied Logic. 113, 1-3, p. 81-94 14 p.

Research output

Open Access
20 Citations (Scopus)

New worst-case upper bounds for SAT

Hirsch, E. A., 1 Jan 2000, In : Journal of Automated Reasoning. 24, 4, p. 397-420 24 p.

Research output

60 Citations (Scopus)

On an optimal randomized acceptor for graph nonisomorphism

Hirsch, E. A. & Itsykson, D., 28 Feb 2012, In : Information Processing Letters. 112, 5, p. 166-171 6 p.

Research output

3 Citations (Scopus)

On optimal heuristic randomized semidecision procedures, with application to proof complexity

Hirsch, E. A. & Itsykson, D., 1 Dec 2010, STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science. p. 453-464 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 5).

Research outputpeer-review

8 Citations (Scopus)

On the limits of gate elimination

Golovnev, A., Hirsch, E. A., Knop, A. & Kulikov, A. S., 1 Sep 2018, In : Journal of Computer and System Sciences. 96, p. 107-119 13 p.

Research output

On the limits of gate elimination

Golovnev, A., Hirsch, E. A., Knop, A. & Kulikov, A. S., 1 Aug 2016, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. Muscholl, A., Faliszewski, P. & Niedermeier, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 46. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 58).

Research outputpeer-review

2 Citations (Scopus)

On the probabilistic closure of the loose unambiguous hierarchy

Hirsch, E. A. & Sokolov, D., 1 Sep 2015, In : Information Processing Letters. 115, 9, p. 725-730 6 p.

Research output

Optimal acceptors and optimal proof systems

Hirsch, E. A., 15 Jul 2010, Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings. p. 28-39 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6108 LNCS).

Research outputpeer-review

7 Citations (Scopus)

Optimal heuristic algorithms for the image of an injective function

Hirsch, E. A., Itsykson, D. M., Nikolaenko, V. O. & Smal, A. V., 1 Jan 2013, In : Journal of Mathematical Sciences (United States). 188, 1, p. 7-16 10 p.

Research output

1 Citation (Scopus)

Satisfiability certificates verifiable in subexponential time

Dantsin, E. & Hirsch, E. A., 27 Jun 2011, Theory and Application of Satisfiability Testing - 14th International Conference, SAT 2011, Proceedings. p. 19-32 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6695 LNCS).

Research outputpeer-review

2 Citations (Scopus)

SAT local search algorithms: worst-case study

Hirsch, E. A., 1 Feb 2000, In : Journal of Automated Reasoning. 24, 1-2, p. 127-143 17 p.

Research output

17 Citations (Scopus)

Several notes on the power of Gomory-Chvátal cuts

Hirsch, E. A. & Kojevnikov, A., 1 Sep 2006, In : Annals of Pure and Applied Logic. 141, 3, p. 429-436 8 p.

Research output

Open Access
2 Citations (Scopus)
4 Citations (Scopus)

Solving Boolean satisfiability using local search guided by unit clause elimination

Hirsch, E. A. & Kojevnikov, A., 1 Jan 2001, Principles and Practice of Constraint Programming - CP 2001 - 7th International Conference, CP 2001, Proceedings. Walsh, T. (ed.). Springer Nature, p. 605-609 5 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2239).

Research outputpeer-review

6 Citations (Scopus)

The SAT2002 competition

Simon, L., Le Berre, D. & Hirsch, E. A., Jan 2005, In : Annals of Mathematics and Artificial Intelligence. 43, 1-4, p. 307-342 36 p.

Research output

22 Citations (Scopus)

Time hierarchies for cryptographic function inversion with advice

Grigoriev, D. Y., Hirsch, E. A. & Pervyshev, K. V., 1 May 2009, In : Journal of Mathematical Sciences . 158, 5, p. 633-644 12 p.

Research output

Two new upper bounds for SAT

Hirsch, E. A., 1 Dec 1998, p. 521-530. 10 p.

Research output

22 Citations (Scopus)
44 Citations (Scopus)

Worst-case study of local search for MAX-k-SAT

Hirsch, E. A., 15 Aug 2003, In : Discrete Applied Mathematics. 130, 2, p. 173-184 12 p.

Research output

Open Access
16 Citations (Scopus)

Worst-case upper bounds

Dantsin, E. & Hirsch, E. A., 1 Jan 2009, Handbook of Satisfiability. 1 ed. IOS Press, p. 403-424 22 p. (Frontiers in Artificial Intelligence and Applications; vol. 185, no. 1).

Research outputpeer-review

26 Citations (Scopus)

Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT

Gramm, J., Hirsch, E. A., Niedermeier, R. & Rossmanith, P., 15 Aug 2003, In : Discrete Applied Mathematics. 130, 2, p. 139-155 17 p.

Research output

Open Access
53 Citations (Scopus)