### Working paper

## Towards a Reverse Newman's Theorem in Interactive Information Complexity

A Euclidean distance matrix D(α) is defined by D_ij=(α_i−α_j)^2, where α=(α_1,…,α_n) is a real vector. We prove that D(α) cannot be written as a sum of [2sqrt(n)−2] nonnegative rank-one matrices, provided that the coordinates of α are algebraically independent. As a corollary, we provide an asymptotically optimal separation between the complexities of quantum and classical communication protocols computing a given matrix in expectation.

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha- y gin. Randomized Individual Communication Complexity. IEEE Con- ference on Computational Complexity 2008: 321-331] considered com- munication complexity of the following problem. Alice has a bi- nary string x and Bob a binary string y, both of length n, and they want to compute or approximate Kolmogorov complexity C(x|y) of x conditional to y. It is easy to show that deterministic communica- tion complexity of approximating C(x|y) with precision α is at least n − 2α − O(1). The above referenced paper asks what is random- ized communication complexity of this problem and shows that for r- round randomized protocols its communication complexity is at least Ω((n/α)1/r ). In this paper, for some positive ε, we show the lower bound 0.99n for (worst case) communication length of any random- ized protocol that with probability at least 0.01 approximates C(x|y) with precision εn for all input pairs.

Newman's theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new direct sum theorems through the compression of interactive communication in the bounded-round setting. Furthermore, we show that if a Reverse Newman's Theorem can be proven in full generality, then full compression of interactive communication and fully-general direct-sum theorems will result.

We initiate a comprehensive study of the complexity of computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains (as opposed to domains such as $\zon$ or $\mon$ that enforce multilinearity). A typical example of such a general Boolean domain, for the purpose of our results, is $\{1,2\}^n$. We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest. First we motivate the study of PTFs over the $\{1,2\}^n$ domain by showing their close relation to depth two threshold circuits. In particular we show that PTFs of polynomial length and polynomial degree compute exactly the functions computed by polynomial size $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf MAJ}}$ circuits. We note that known lower bounds for $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf MAJ}}$ circuits extends to the likely strictly stronger model of PTFs (with no degree restriction). We also show that a ``max-plus'' version of PTFs are related to $\mathsf{AC}^0 \circ \ensuremath{{\rm \sf THR}}$ circuits. We exploit this connection to gain a better understanding of threshold circuits. In particular, we show that (super-logarithmic) lower bounds for 3-player randomized communication protocols with unbounded error would yield (super-polynomial) size lower bounds for $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf THR}}$ circuits. Finally, having thus motivated the model, we initiate structural studies of PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length.

This book constitutes the refereed proceedings of the First International Conference on Data Compression, Communications and Processing held in Palinuro, Italy, in June 2011.

The manual is intended for students of Department of computer engineering MIEM HSE. In the textbook based on the courses "Economics of firm" and "the development strategy of the organization." Discusses the key conceptual and methodological issues of the theory and practice of Economics and development planning of the organization. The use of textbooks will enable students: to analyze key performance indicators, and use the tools of strategic analysis with reference to concrete situations in contemporary Russian and international business. Special attention is paid to the methods and systems of information support of the life support functions of business organizations and management methodology of innovation and investment. An Appendix contains source data for analysis of competition in a particular industry.

The paper provides a number of proposed draft operational guidelines for technology measurement and includes a number of tentative technology definitions to be used for statistical purposes, principles for identification and classification of potentially growing technology areas, suggestions on the survey strategies and indicators. These are the key components of an internationally harmonized framework for collecting and interpreting technology data that would need to be further developed through a broader consultation process. A summary of definitions of technology already available in OECD manuals and the stocktaking results are provided in the Annex section.

Over the last two decades national policy makers drew special attention to the implementation of policy tools which foster international cooperation in the fields of science, technology, and innovation. In this paper, we look at cases of Russian-German collaboration to examine the initiatives of the Russian government aimed at stimulating the innovation activity of domestic corporations and small and medium enterprises. The data derived from the interviews with companies’ leaders show positive effects of bilateral innovative projects on the overall business performance alongside with major barriers hindering international cooperation. To overcome these barriers we provide specific suggestions relevant to the recently developed Russian Innovation Strategy 2020.