×

zbMATH — the first resource for mathematics

Andreev, Alexander E.

Compute Distance To:
Author ID: andreev.alexander-e Recent zbMATH articles by "Andreev, Alexander E."
Published as: Andreev, A. E.; Andreev, Alexander E.; Andreev, A.; Andreyev, A.; Andreev, Alexander
External Links: Wikidata · GND
Documents Indexed: 60 Publications since 1979, including 2 Books

Publications by Year

Citations contained in zbMATH Open

31 Publications have been cited 108 times in 81 Documents Cited by Year
On a method for obtaining lower bounds for the complexity of individual monotone functions. Zbl 0616.94019
Andreev, A. E.
23
1985
A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes. Zbl 0645.94022
Andreev, A. E.
12
1987
Weak random sources, hitting sets, and BPP simulations. Zbl 0943.68064
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.; Trevisan, Luca
10
1999
A new general derandomization method. Zbl 0903.68089
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
9
1998
Small pseudo-random sets yield hard functions: New tight explicit lower bounds for branching programs. Zbl 0941.68567
Andreev, Alexander E.; Baskakov, Juri L.; Clementi, Andrea E. F.; Rolim, José D. P.
7
1999
Hitting sets derandomize BPP. Zbl 1046.68536
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
5
1996
Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs. Zbl 0930.68064
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
4
1999
On some methods for obtaining more than quadratic effective lower bounds of the complexity of \(\pi\)-circuits. Zbl 0633.94024
Andreev, A. E.
4
1987
On some method for obtaining effective lower bounds of monotone complexity. Zbl 0643.94027
Andreev, A. E.
4
1987
On the complexity of realization of partial Boolean functions by circuits of functional elements. Zbl 0733.94026
Andreev, A. E.
3
1991
A method for obtaining efficient lower bounds for monotone complexity. Zbl 0659.94020
Andreev, A. E.
2
1987
On the synthesis of disjunctive normal forms which are close to minimal. Zbl 0556.94015
Andreev, A. E.
2
1983
On the asymptotic behaviour of the number of dead-lock tests and of the minimal length of a test for almost all tables. Zbl 0566.68071
Andreev, A. E.
2
1984
On the complexity of the realization of partial Boolean functions by circuits of functional elements. Zbl 0719.94028
Andreev, A. E.
2
1989
Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs. Zbl 1401.68093
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
2
1997
Theory of test recognition. (Теория тестового распознавания.) Zbl 1154.68099
Kudryavtsev, V. B.; Andreev, A. E.; Gasanov, Eh. Eh.
2
2007
On irredundant and minimal tests. Zbl 0487.68079
Andreev, A. E.
1
1981
On stability for perturbed differential equations. Zbl 0930.34035
Andreev, Alexander; Zappalà, Giuseppe
1
1996
Optimal bounds for the approximation of Boolean functions and some applications. Zbl 0911.94010
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
1
1997
The parallel complexity of approximating the high degree subgraph problem. Zbl 0913.68095
Andreev, A. E.; Clementi, A.; Crescenzi, P.; Dahlhaus, E.; De Agostino, S.
1
1998
A deciding algorithm for linear isomorphism of types with complexity \(O(n\log^ 2(n))\). Zbl 0884.68057
Andreev, A.; Soloviev, S.
1
1997
On a family of Boolean matrices. Zbl 0627.05010
Andreev, A. E.
1
1986
On the complexity of monotone functions. Zbl 0578.94030
Andreev, A. E.
1
1985
On the problem of minimizing disjunctive normal forms. Zbl 0581.94028
Andreev, A. E.
1
1984
On a modification of the gradient algorithm. Zbl 0591.94037
Andreev, A. E.
1
1985
On the design of self-correcting control systems. Zbl 0599.94015
Andreev, A. E.
1
1984
A universal principle of self-correction. Zbl 0599.94016
Andreev, A. E.
1
1986
Test recognition. Zbl 1223.68100
Kudryavtsev, V. B.; Andreev, A. E.
1
2010
On algorithm complexity. Zbl 1288.68097
Kudryavtsev, V. B.; Andreev, A. E.
1
2010
Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness. Zbl 1379.68157
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
1
1996
Genus expansion of matrix models and \(\hbar\) expansion of KP hierarchy. Zbl 1457.81054
Andreev, A.; Popolitov, A.; Sleptsov, A.; Zhabin, A.
1
2020
Genus expansion of matrix models and \(\hbar\) expansion of KP hierarchy. Zbl 1457.81054
Andreev, A.; Popolitov, A.; Sleptsov, A.; Zhabin, A.
1
2020
Test recognition. Zbl 1223.68100
Kudryavtsev, V. B.; Andreev, A. E.
1
2010
On algorithm complexity. Zbl 1288.68097
Kudryavtsev, V. B.; Andreev, A. E.
1
2010
Theory of test recognition. (Теория тестового распознавания.) Zbl 1154.68099
Kudryavtsev, V. B.; Andreev, A. E.; Gasanov, Eh. Eh.
2
2007
Weak random sources, hitting sets, and BPP simulations. Zbl 0943.68064
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.; Trevisan, Luca
10
1999
Small pseudo-random sets yield hard functions: New tight explicit lower bounds for branching programs. Zbl 0941.68567
Andreev, Alexander E.; Baskakov, Juri L.; Clementi, Andrea E. F.; Rolim, José D. P.
7
1999
Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs. Zbl 0930.68064
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
4
1999
A new general derandomization method. Zbl 0903.68089
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
9
1998
The parallel complexity of approximating the high degree subgraph problem. Zbl 0913.68095
Andreev, A. E.; Clementi, A.; Crescenzi, P.; Dahlhaus, E.; De Agostino, S.
1
1998
Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs. Zbl 1401.68093
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
2
1997
Optimal bounds for the approximation of Boolean functions and some applications. Zbl 0911.94010
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
1
1997
A deciding algorithm for linear isomorphism of types with complexity \(O(n\log^ 2(n))\). Zbl 0884.68057
Andreev, A.; Soloviev, S.
1
1997
Hitting sets derandomize BPP. Zbl 1046.68536
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
5
1996
On stability for perturbed differential equations. Zbl 0930.34035
Andreev, Alexander; Zappalà, Giuseppe
1
1996
Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness. Zbl 1379.68157
Andreev, Alexander E.; Clementi, Andrea E. F.; Rolim, José D. P.
1
1996
On the complexity of realization of partial Boolean functions by circuits of functional elements. Zbl 0733.94026
Andreev, A. E.
3
1991
On the complexity of the realization of partial Boolean functions by circuits of functional elements. Zbl 0719.94028
Andreev, A. E.
2
1989
A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes. Zbl 0645.94022
Andreev, A. E.
12
1987
On some methods for obtaining more than quadratic effective lower bounds of the complexity of \(\pi\)-circuits. Zbl 0633.94024
Andreev, A. E.
4
1987
On some method for obtaining effective lower bounds of monotone complexity. Zbl 0643.94027
Andreev, A. E.
4
1987
A method for obtaining efficient lower bounds for monotone complexity. Zbl 0659.94020
Andreev, A. E.
2
1987
On a family of Boolean matrices. Zbl 0627.05010
Andreev, A. E.
1
1986
A universal principle of self-correction. Zbl 0599.94016
Andreev, A. E.
1
1986
On a method for obtaining lower bounds for the complexity of individual monotone functions. Zbl 0616.94019
Andreev, A. E.
23
1985
On the complexity of monotone functions. Zbl 0578.94030
Andreev, A. E.
1
1985
On a modification of the gradient algorithm. Zbl 0591.94037
Andreev, A. E.
1
1985
On the asymptotic behaviour of the number of dead-lock tests and of the minimal length of a test for almost all tables. Zbl 0566.68071
Andreev, A. E.
2
1984
On the problem of minimizing disjunctive normal forms. Zbl 0581.94028
Andreev, A. E.
1
1984
On the design of self-correcting control systems. Zbl 0599.94015
Andreev, A. E.
1
1984
On the synthesis of disjunctive normal forms which are close to minimal. Zbl 0556.94015
Andreev, A. E.
2
1983
On irredundant and minimal tests. Zbl 0487.68079
Andreev, A. E.
1
1981
all top 5

Cited by 114 Authors

6 Andreev, Alexander E.
6 Wigderson, Avi
5 Kabanets, Valentine
4 Clementi, Andrea E. F.
4 Raz, Ran
4 Razborov, Aleksandr Aleksandrovich
4 Rolim, José D. P.
4 Yukna, Stasys P.
3 Impagliazzo, Russell
3 Sholomov, Lev A.
3 Tarui, Jun
3 Vadhan, Salil P.
2 Amano, Kazuyuki
2 Chashkin, Alexander V.
2 Chen, Ruiwen
2 Goldreich, Oded
2 Håstad, Johan Torkel
2 Komargodski, Ilan
2 Krause, Matthias
2 Lingas, Andrzej
2 Maksimov, Yu. V.
2 Meinel, Christoph
2 Morizumi, Hiroki
2 Pudlák, Pavel
2 Tal, Avishay
2 Umans, Christopher
1 Aaronson, Scott
1 Alba-Cabrera, Eduardo
1 Allender, Eric W.
1 Arvind, Vikraman
1 Babai, László
1 Bazzi, Louay M. J.
1 Blum, Norbert
1 Cai, Jin-Yi
1 Carrasco-Ochoa, Jesús Ariel
1 Chashkin, Aleksandr V.
1 Chukhrov, I. P.
1 Cook, Stephen Arthur
1 Cortés, Manuel S. Lazo
1 Damm, Carsten
1 Dyukova, Elena Vsevolodovna
1 Dodis, Yevgeniy
1 Frolov, A. B.
1 Gavinsky, Dmitry
1 Goldmann, Mikael
1 Guo, Siyao
1 Hajnal, Péter
1 Haken, Armin
1 Hiltgen, Alain P.
1 Hromkovič, Juraj
1 Hrubeš, Pavel
1 Iwama, Kazuo
1 Karakostas, George L.
1 Karchmer, Mauricio
1 Kawachi, Akinori
1 Kinne, Jeff
1 Köbler, Johannes
1 Kolokolova, Antonina
1 Koucký, Michal
1 Král’, Daniel
1 Kudryavtsev, Valeriĭ Borisovich
1 Kulikov, Alexander S.
1 Kurganskyy, O. M.
1 Lazo Cortés, Manuel
1 Li, Jiyou
1 Limaye, Nutan
1 Luo, Chu
1 Martínez-Trinidad, José Francisco
1 Maruoka, Akira
1 Meir, Or
1 Nahas, Nagi H.
1 Nunkesser, Robin
1 Øhrn, Aleksander
1 Paterson, Mike S.
1 Reingold, Omer
1 Ronneburger, Detlef
1 Rotem, Lior
1 Roy, Sambuddha
1 Rudich, Steven
1 Ruiz-Shulcloper, José
1 Sánchez-Díaz, Guillermo
1 Sapozhenko, Aleksandr Antonovich
1 Sapunov, S. V.
1 Sauerhoff, Martin
1 Saurabh, Nitin
1 Savický, Petr
1 Segev, Gil
1 Seiwert, Hannes
1 Seto, Kazuhisa
1 Shaltiel, Ronen
1 Simon, Janos
1 Sotnezov, R. M.
1 Sreenivasaiah, Karteek
1 Srinivasan, Srikanth
1 Stetsenko, Vladimir
1 Sudan, Madhu
1 Szemerédi, Endre
1 Tamaki, Suguru
1 Trevisan, Luca
1 Tripathi, Utkarsh
...and 14 more Authors

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.