On Pseudorandom Generators with Linear Stretch in NC0

We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC⁰, namely ones in which each bit of the output depends on just a constant number of input bits. Previous constructions of such PRGs were limited to stretching a seed of n bits to n + o(n) bits. This leaves open the existence of a PRG with a linear (let alone superlinear) stretch in NC⁰. In this work we study this question and obtain the following main results:

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.      

Randomness-Efficient Sampling within NC1

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC ⁰[⊕]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC ¹. For example, we obtain the following results:

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.      

Modeling and Processing Information for Context-Aware Computing: A Survey

Context-awareness is emerging as a central issue in ubiquitous computing research. Context-aware computing refers to the idea that computing devices can sense and react to the physical environment where they are deployed. A great deal of research on context-awareness has been conducted to explore and address the various challenges related to context acquisition, representation, distribution, and abstraction. This paper surveys the most relevant approaches to modeling context for ubiquitous computing. It also evaluates how the existing works utilize contextual information, with respect to the query processing approaches used to access and manage that information. We also discuss typical problems, shortcomings, and challenges posed by context modeling at large, and highlight some proposals to address some of them.

Exponential queuing system with negative customers and bunker for ousted customers

Consideration was given to the queuing system with Poisson flows of incoming positive and negative customers. For the positive customers, there is an infinite-capacity buffer. The arriving negative customer knocks out a positive customer queued in the buffer and moves it to an infinite-capacity buffer of ousted customers (bunker). If the buffer is empty, then the negative customer discharges the system without affecting it. After servicing the current customer, the server receives a customer from the buffer or, if the buffer is empty, the bunker. The customers arriving from both the buffer and bunker are distributed exponentially with the same parameter. Relations for calculation of the stationary distributions of the queues in the buffer and bunker were obtained.     

Boolean models and planning methods for parallel abstract programs

For the parallel computer systems, a new formulation of the problem of constructing parallel asynchronous abstract programs of the desired length was proposed. The conditions for the problem of planning were represented as a system of Boolean equations (constraints) whose solutions define the feasible plans for activation of the program modules specified in the planner’s knowledge base. The constraints on the number of processors and time delays arising at execution of the program modules were taken into consideration.     

Decomposition of problems of optimal control and estimation for discrete systems with fast and slow variables

Consideration was given to the linear-quadratic problem of optimal control for the discrete linear system with fast and slow variables under incomplete information about system state. Decomposition of the discrete matrix Riccati equations was carried out. The proposed decomposition algorithm relies on a geometrical approach using the properties of the invariant manifolds of slow and fast motions of the nonlinear multirate discrete systems as basis. The splitting transformation was constructed in the form of asymptotic decomposition in the degrees of a small parameter.     

On instability of control systems for a certain class of objects and methods of its elimination

In practice of design of control systems, the cases occur when some of the roots of the transfer function of a controllable object are disposed on the imaginary axis of the complex plane. The optimal controller constructed for such objects, despite its realizability, will not afford the robustness properties in the system. The methods of removal of this phenomenon are given. The comparative estimate of the solution of this problem is provided both in the space of states and in the input-output relations (in the space of operators).     

Invariance for impulsive control systems

The conventional concepts of invariance are extended in this article to include impulsive control systems represented by measure driven differential inclusions. Invariance conditions and some of their main features are derived. The solution concept plays a critical role in the extension of the conditions for conventional problems to the impulsive control context.     

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:

Modernization of one criterion for absolute stability

A new form of a partial frequency criterion of absolute stability for nonlinear automatic control systems is obtained basing on a quadratic transformation of the state vector. As is shown, the obtained criterion is stronger than V.M. Popov’s one. An alternative formulation of the criterion is given in terms excluding the notions of quadratic transformation.