Нижние оценки монотонной сложности логического перманента
А. А. Разборов

Эта публикация цитируется в следующих статьяx:

1. Saeed Mehraban, Mehrdad Tahmasbi, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024, 608  
2. Ján Pich, “Localizability of the approximation method”, comput. complex., 33:2 (2024)  
3. Andrzej Lingas, Lecture Notes in Computer Science, 13878, SOFSEM 2023: Theory and Practice of Computer Science, 2023, 301  
4. Stasys Jukna, “Notes on Hazard-Free Circuits”, SIAM J. Discrete Math., 35:2 (2021), 770  
5. Stasys Jukna, Hannes Seiwert, “Approximation Limitations of Pure Dynamic Programming”, SIAM J. Comput., 49:1 (2020), 170  
6. Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, Karteek Sreenivasaiah, “On the Complexity of Hazard-free Circuits”, J. ACM, 66:4 (2019), 1  
7. Mateus De Oliveira Oliveira, Pavel Pudlák, “Representations of Monotone Boolean Functions by Linear Programs”, ACM Trans. Comput. Theory, 11:4 (2019), 1  
8. Meena Mahajan, Nitin Saurabh, “Some Complete and Intermediate Polynomials in Algebraic Complexity Theory”, Theory Comput Syst, 62:3 (2018), 622  
9. Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, Karteek Sreenivasaiah, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, 878  
10. Meena Mahajan, Nitin Saurabh, Lecture Notes in Computer Science, 9691, Computer Science – Theory and Applications, 2016, 251  
11. Scott Aaronson, Open Problems in Mathematics, 2016, 1  
12. Stasys Jukna, “Lower Bounds for Tropical Circuits and Dynamic Programs”, Theory Comput Syst, 57:1 (2015), 160  
13. Sajin Koroth, Jayalal Sarma, Lecture Notes in Computer Science, 8591, Computing and Combinatorics, 2014, 596  
14. Lance Fortnow, Steven Homer, Handbook of the History of Logic, 9, Computational Logic, 2014, 495  
15. Alexander A. Razborov, The Mathematics of Paul Erdős I, 2013, 425  
16. А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168            ; A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165      
17. А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 65–87    ; A. P. Davydow, S. I. Nikolenko, “Circuit complexity of linear functions: gate elimination and feeble security”, J. Math. Sci. (N. Y.), 188:1 (2013), 35–46  
18. С. Б. Гашков, И. С. Сергеев, “Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочлены”, Матем. сб., 203:10 (2012), 33–70          ; S. B. Gashkov, I. S. Sergeev, “A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials”, Sb. Math., 203:10 (2012), 1411–1447    
19. Siu Man Chan, Aaron Potechin, Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 2012, 495  
20. А. Д. Коршунов, “Некоторые нерешенные задачи дискретной математики и математической кибернетики”, УМН, 64:5(389) (2009), 3–20            ; A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803      
21. В. Б. Кудрявцев, А. Е. Андреев, “О сложности алгоритмов”, Фундамент. и прикл. матем., 15:3 (2009), 135–181    ; V. B. Kudryavtsev, A. E. Andreev, “On algorithm complexity”, J. Math. Sci., 168:1 (2010), 89–122    
22. BENOIT LAROSE, MATT VALERIOTE, LÁSZLÓ ZÁDORI, “OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT”, Int. J. Algebra Comput., 19:05 (2009), 647  
23. Oded Goldreich, Lecture Notes in Computer Science, 3895, Theoretical Computer Science, 2006, 254  
24. Michael Wooldridge, Paul E Dunne, “On the computational complexity of qualitative coalitional games”, Artificial Intelligence, 158:1 (2004), 27  
25. А. Д. Коршунов, “Монотонные булевы функции”, УМН, 58:5(353) (2003), 89–162          ; A. D. Korshunov, “Monotone Boolean functions”, Russian Math. Surveys, 58:5 (2003), 929–1001      
26. Tomás Feder, Moshe Y. Vardi, “The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory”, SIAM J. Comput., 28:1 (1998), 57  
27. Satyanarayana V. Lokam, Lecture Notes in Computer Science, 1530, Foundations of Software Technology and Theoretical Computer Science, 1998, 307  
28. R. Raz, P. McKenzie, Proceedings 38th Annual Symposium on Foundations of Computer Science, 1997, 234  
29. Alexander A Razborov, Steven Rudich, “Natural Proofs”, Journal of Computer and System Sciences, 55:1 (1997), 24  
30. S. Jukna, Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, 1997, 302  
31. A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Изв. РАН. Сер. матем., 59:1 (1995), 201–224      ; Izv. Math., 59:1 (1995), 205–227    
32. Mikael Goldmann, “A note on the power of majority gates and modular gates”, Information Processing Letters, 53:6 (1995), 321  
33. Alexander A. Razborov, Feasible Mathematics II, 1995, 344  
34. Mauricio Karchmer, Feasible Mathematics II, 1995, 245  
35. A.C.-C. Yao, Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, 302  
36. Lance Fortnow, Lecture Notes in Computer Science, 880, Foundation of Software Technology and Theoretical Computer Science, 1994, 256  
37. M. Karchmer, [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993, 112  
38. Michael D. Plummer, “Matching theory—a sampler: from Dénes König to the present”, Discrete Mathematics, 100:1-3 (1992), 177  
39. Mihalis Yannakakis, “Expressing combinatorial optimization problems by Linear Programs”, Journal of Computer and System Sciences, 43:3 (1991), 441  
40. M. Grigni, M. Sipser, [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991, 294  
41. Christoph Meinel, Lecture Notes in Computer Science, 452, Mathematical Foundations of Computer Science 1990, 1990, 61  
42. J. Hastad, M. Goldmann, Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, 1990, 610  
43. Ravi B. BOPPANA, Michael SIPSER, Algorithms and Complexity, 1990, 757  
44. Elias Dahlhaus, Marek Karpinski, Lecture Notes in Computer Science, 318, SWAT 88, 1988, 139  
45. Matthias Krause, Christoph Meinel, Stephan Waack, Lecture Notes in Computer Science, 324, Mathematical Foundations of Computer Science 1988, 1988, 405  
46. А. А. Разборов, “Нижние оценки размера схем ограниченной глубины в базисе $\{\&,\vee,\oplus\}$”, УМН, 41:4(250) (1986), 219–220        ; A. A. Razborov, “Lower estimates of the dimension of schemes of bounded depth in the basis $\{\&,\vee,\oplus\}$”, Russian Math. Surveys, 41:4 (1986), 181–182    
47. David S Johnson, “The NP-completeness column: An ongoing guide”, Journal of Algorithms, 7:2 (1986), 289