Algorithms to construct suboptimal organization hierarchies

The problem of controlling an organization structure (hierarchy of organization control) was considered as that of discrete optimization, that is, minimization by selecting the permissible hierarchy of total costs of maintaining its managers. For the case of the so-called uniform functions of manager costs, the lower estimate of the costs of the optimal hierarchy was obtained allowing one, besides all other things, to determine approximately the main characteristics of the optimal hierarchy such as the number of managers, their norm of controllability, and so on. Quality of this lower estimate was studied, and effective algorithms to construct suboptimal hierarchies with costs slightly exceeding the optimal ones were proposed for some important cases.     

Perfect Parallel Repetition Theorem for Quantum Xor Proof Systems

We consider a class of two-prover interactive proof systems where each prover returns a single bit to the verifier and the verifier’s verdict is a function of the XOR of the two bits received. We show that, when the provers are allowed to coordinate their behavior using a shared entangled quantum state, a perfect parallel repetition theorem holds in the following sense. The prover’s optimal success probability for simultaneously playing a collection of XOR proof systems is exactly the product of the individual optimal success probabilities. This property is remarkable in view of the fact that, in the classical case (where the provers can only utilize classical information), it does not hold. The theorem is proved by analyzing parities of XOR proof systems using semidefinite programming techniques, which we then relate to parallel repetitions of XOR games via Fourier analysis.      

Robust control of composite beams

The structure uncertainty effect is considered on actively controllable composite beam that is a part of the structure of a civil building in a seismodangerous zone. The solution of the problem for active control of vibrations of the composite beam is based on the introduction of a simplified model of sensors and an actuator, which are implemented in the form of piezoelectric plates pasted on two opposite planes of the beam. A suggestion is made of the practical approach that affords the robust control of the composite beam and is founded on the modern H ₂- and H _∞-methods of the theory of control. The effectiveness of the suggested approach for the suppression of vibrations of the composite beam under consideration is illustrated by the examples of numerical modeling.     

Inverse NP Problems

The inverse problem relative to a verifier V of proofs of membership for a NP language is the problem of deciding, given a set π of proofs, whether or not there exists a string x having exactly π as its set of proofs. In this paper, we study the complexity of inverse problems. We develop a new notion of reduction which allows one to compare the complexity of inverse problems. Using this notion, we classify as coNP-complete the inverse problems for the “natural” verifiers of many NP-complete problems. We also show that the inverse complexity of a verifier for a language L cannot be predicted solely from the complexity of L, but rather, is highly dependent upon the choice of verifier used to accept L. In this context, a verifier with a Σ₂ ^p -complete inverse problem is exhibited, giving a new and natural example of a Σ₂ ^p -complete problem.      

Robust stabilization of continuous indeterminate systems

The system of an arbitrary order with one scalar control is considered. It is assumed that coefficients of the system and vectors of distribution of control are bounded and are functionals of an arbitrary character. With the aid of the Lyapunov function in a quadratic form with the constant Jacobian matrix of coefficients of a special form, the conditions for bounds of a change of the coefficients are obtained, in the fulfillment of which the linear stationary control by the state is synthesized. In this control, the system becomes exponentially stable on the whole.     

Robust control of multidimensional nonstationary linear plants

Solved was the problem was of constructing a robust control system with linear nonstationary multidimensional control plant compensating the parametric and external bounded perturbations to within δ if the derivatives of the output vector are not measured and fully if the derivatives are measured.     

Robust filtering under nonrandom disturbances: The invariant ellipsoid approach

We present a simple and universal observer-based approach to solving the problem of robust filtering of unknown-but-bounded exogenous disturbances. The heart of this approach is the method of invariant ellipsoids. Application of this technique allows for a reformulation of the original problem in terms of linear matrix inequalities with reduction to semidefinite programming and one-dimensional optimization, which are easy to solve numerically. Continuous-time and discrete-time cases are studied in equal detail. The efficacy of the approach is demonstrated via the double pendulum example.     

Hardness Hypotheses, Derandomization, and Circuit Complexity

We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences:

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Systems with a switch and estimation of absolute stability region

Two methods are proposed for estimation of absolute stability region in the space of parameters. The first method uses nontrivial necessary conditions, which follow from stability of switching systems. The second method is a modification of the harmonic balance approach; it is used for approximate determination of existence of periodic modes that arise when stability is lost.