Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2012/Program2/Podolskii_summary.pdf Дата изменения: Tue Oct 16 11:18:50 2012 Дата индексирования: Mon Feb 4 19:01:47 2013 Кодировка:

Summary of Research Statement
Vladimir Podolskii
In this pro ject we plan to work in several directions in Computational Complexity theory which are mostly connected through the methods and techniques. One of the directions is devoted to one specific computational model, namely to threshold gates and threshold circuits. This model has been extensively studied in Computational Complexity theory since 1960s and found numerous application in circuit complexity, structural complexity, learning theory and communication complexity. The main ob jective in this area is to understand the computational power of this model and in particular to prove lower bounds on the complexity parameters of threshold gates and threshold circuits computing explicit functions. In previous work the author has proved a lower bound on the weights of threshold gates in various settings, an exponential lower bound on the size of constant depth circuits with a logarithmic number of threshold gates. Also, in the joint work with K.A. Hansen, the author has refined the hierarchy of constant depth threshold circuits. It is planned to continue the investigation in this direction and in particular to study the computational power of threshold gates with the variables ranging over {1, 2} and to relate this model to the usual threshold circuits. We suppose that this study will lead to new results on the usual threshold circuits. Another direction is studying algorithmic problems in min-plus algebra. The most basic algebraic algorithmic problem is to solve systems of linear equations. In the case of classical algebra the well known Gauss algorithm solves linear systems in polynomial time. In the case of min-plus semiring things turn out to be more complicated and no polynomial time algorithm is known for both of the two standard types of linear equations: neither for tropical linear systems, nor for min-plus linear systems (here by min-plus linear system we call the system of standard two sided linear equations over min-plus algebra and by tropical linear system we call the system of linear min-plus polynomials; solution to the tropical linear system is a vector of values of variables such that for each polynomial of the system the minimum of the values of monomials is attained on at least two monomials). It is however known that this problem for min-plus linear systems is equivalent to the well known and long standing mean payoff games problem. In the joint paper with D. Grigoriev we prove that the same is true for tropical linear systems. We further investigate algorithmic problems in min-plus linear algebra. We plan to continue this work. In particular, we plan to investigate structural connections between tropical and min-plus systems. Also we plan to work on the analog of Hilbert's Nullstellensatz in min-plus algebra. This problem is also likely to be related to tropical linear systems. It is also planned to work in this pro ject in communication complexity, the area which appeared at the end of 1970s and has already found numerous applications through all the Computational Complexity theory. It is planned to study multi-party communication complexity in the "Number on the forehead" model. For such communication protocols strong lower bounds are known when the number of players is less than log n. To prove a strong lower bound for more than log n players is a ma jor open problem in the area. We plan to study the behavior of communication complexity of some standard functions in this area for more than log n players and, in particular, to prove probably weak, but still nontrivial lower bounds on communication complexity of these functions. Finally, one more direction is devoted to the area of query rewritings for ontology databases. This is a rather new area applying studies in mathematical logic to data storage. The typical way to handle queries to such databases is to rewrite it in such a form that the query can be answered without studying the first-order theory of the given database. Jointly with S. Kikot, R. Kontchakov and M. Zakharyaschev the author showed for several different settings that the size of such a rewriting can be exponentially longer than the original query. Interestingly, these results are proved through the connection to Boolean circuit complexity. We plan to continue work in this direction.