In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size and propose a novel decomposition of the bias via a linearization technique. We analyze the structure of the bias and show that the leading-order term is linear in the step size and cannot be eliminated by PR averaging. To address this, we apply the Richardson-Romberg (RR) extrapolation procedure, which effectively cancels the leading bias term. We derive high-order moment bounds for the RR iterates and show that the leading error term aligns with the asymptotically optimal covariance matrix of the vanilla averaged LSA iterates. We validate applicability of our findings for the temporal difference algorithm in reinforcement learning.

In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communication complexity of FedLSA scales polynomially with the inverse of the desired accuracy ϵ. To overcome this, we propose SCAFFLSA a new variant of FedLSA that uses control variates to correct for client drift, and establish its sample and communication complexities. We show that for statistically heterogeneous agents, its communication complexity scales logarithmically with the desired accuracy, similar to Scaffnew. An important finding is that, compared to the existing results for Scaffnew, the sample complexity scales with the inverse of the number of agents, a property referred to as linear speed-up. Achieving this linear speed-up requires completely new theoretical arguments. We apply the proposed method to federated temporal difference learning with linear function approximation and analyze the corresponding complexity improvements.

The paper studies a new polynomial representation of Multi Output Functions (MOFs). The new representation, called GITE-polynomials, is based on a newly introduced Generalized If-Then-Else (GITE) function. Being a compact form of representation of MOFs, the GITE-polynomials allow efficient manipulation with a set of functions. The paper introduces algebra of GITE-polynomials. Properties of this algebra are used for solving the MOF-decomposition problem. The solution provides a compact representation of MOFs.

A Trojan horse is a malicious altering of hardware specification or implementation in such a way that its functionality is altered under a set of conditions defined by the attacker. The paper presents a technique for designing secure systems that can detect an active Trojan. The technique is based on utilizing specific information about the system's behavior, which is known to the designer of the system and/or is hidden in the functional specification of the system. A case study of the proposed technique conducted on an arithmetic unit of a microprocessor is provided. The study indicated a high level of Trojan detection with a small hardware overhead.

This paper deals with the number of paths in multiterminal binary decision diagrams (MTBDDs) and shared binary decision diagrams (SBDDs) representing a set of Boolean functions. It is shown that the number of paths in an MTBDD (SBDD) can be uniquely determined by values of specific weighted-autocorrelation coefficients. An analytical expression for the number of paths as a linear function of the values of the weighted-autocorrelation coefficients is presented. Based on this expression, a method of minimization of the number of paths is proposed. The method is based on replacing the initial set of input variables with their linear combinations. By using this method, a deterministic paths-reduction procedure, which provides MTBDDs and SBDDs with a reduced number of paths, is presented. The efficiency of the suggested approach is demonstrated on benchmark functions.

The paper deals with significant technological changes in society when it moves into Post-Industrial age. Some of these changes have fundamental social consequences. The paper analyses the main social trends such as Virtualization of the society in their interaction with newest technology trends and their influence on education. The concept of Virtualization allows formulating the main feature of the Post-Industrial education, which is personalization. The phenomenon of personalization is supported by newly developed and introduced personal communication means forming totally person-dedicated, unique learning environment.

The paper deals with designing fault tolerant finite state machines (FSMs) by nanoelectronic programmable logic arrays (PLAs). Two main critical parameters of the fault tolerant nano-PLAs, the area and the number of crosspoint devices, are considered as optimization criteria for the synthesis. The paper introduces a method for synthesizing fault tolerant nano-PLA based FSMs. The method is based on decomposing an initial PLA description of the FSM into a three interacting portions. The proposed solution provides significant reduction of the area without meaningful increasing of a number of crosspoint devices in comparison with known solutions and provides a trade-off between the area and the number of devices in designing FSMs by PLAs.

This paper discusses reduction of the number of product terms in representation of totally symmetric Boolean functions by Sum of Products (SOP) and Fixed Polarity Reed- Muller (FPRM) expansions. The suggested method reduces the number of product terms, correspondingly, the implementation cost of symmetric functions based on these expressions by exploiting Gray decoding of input variables. Although this decoding is a particular example of all possible linear transformation of Boolean variables, it is efficient in the case of symmetric functions since it provides a significant simplification of SOPs and FPRMs. Mathematical analysis as well as experimental results demonstrate the efficiency of the proposed method.

The paper deals with synthesis technique for designing circuits with cascade errors detection. The proposed technique is based on partitioning a scheme into a number of cascades followed by parity checking their output logic. The algorithm for partitioning the scheme into cascades is provided. An universal scheme of finite state machine (FSM) with the cascade errors detection is presented and investigated. The scheme does not require any redundant coding variables. Benchmark results are presented and show significantly low overhead requirement

The AC side current of some high switching frequency AC-DC converters may be programmed so as to draw a sinusoidal current with adjustable amplitude and phase with respect to at AC applied voltage. This may be viewed as virtual capacitance emulation. Simultaneously to rectifying real power, such converters may be applied for compensation of reactive power system currents and for generators output reactance, thus increasing their power throughput. Experimental evidence are provided, which support the proposed method

The paper describes a specific method for designing self-checking checkers for m-out-of-n codes. The method is oriented to the field programmable gate arrays technology and is based on decomposing the sum-of-minterms corresponding to an m-out-of-n code. The self-testing property of the proposed checker is proven for a set of multiple stuck-at faults at input and output poles of a logic cell. An estimated complexity of obtained m-out-of-n checker demonstrates high efficiency of the proposed method.

Implementation of checkers on the basis of threshold functions is problematic due to low stability of component threshold schemes. The paper proposes two methods allowing increasing the implementability: a) by introducing a relatively small overhead for preliminary exclusion of defective circuits; and b) by using a specific procedure of calibration. The first method is proposed upon considering a method of majority reservation while the second is based on a specific learning procedure that is known from studying /spl beta/-driven threshold elements as a basis for CMOS artificial neurons.

In this paper we introduce concepts of a potential fault latency and a real fault latency for Finite State Machines (FSMs). The potential latency defines a minimal value of the possible latency for an FSM, while the real latency relates to the certain implementation of the FSM A method for investigation of latencies for online checking FSMs is described This technique is based on selection of trajectories of the Markov chain, which describes behavior of the fault free FSM as well as the faulty FSM We also estimate the lowest bound for an average latency. This estimation may be useful at an initial stage of the design when information concerning requirements to the FSM and conditions of its functioning is limited.

In this paper we deal with totally self-checking (TSC) synchronous sequential circuits (SSCs), that are able to recover after an occurrence of a fault. We call SSC owing this property as a self-healing SSC. A concept of a partially monotonic SSC is used in the paper. It is shown that the partially monotonic SSCs satisfy the self-healing property. A novel reduced m-out-of-n code is developed. It is proposed applying this code to the synthesis of a TSC checker for the state monotonic SSCs. The proposed method of synthesis is based on a LUT implementation of monotonic functions.For most circuits in a standard benchmark set, the proposed approach leads to a reduction of about 10-20% of the overhead as compared with the traditional methods.

In this paper we present a new technique for on-line checking of FPGA-based sequential devices defined by their algorithmic state machines (ASMs). The technique utilizes specific properties of ASMs for achieving the totally self-checking goal with a low hardware overhead. This technique is based on the architecture that consists of two portions: a self-checking sequential device and a separate totally self-checking (TSC) checker. Each of these portions is implemented as a combination of an "evolution" block and an "execution" block. Comparison of code vectors transferred between these blocks provides for the totally self-checking property. The proposed technique does not require any redundant encoding of output words and uses a one-rail design, thereby drastically decreasing the required overhead. The paper presents overhead estimations and results for benchmarks for the proposed architecture.

The paper introduces a new technique for on-line checking of FPGA based Control Units (CUs). This technique is based on the architecture comprising two portions. A self-checking CU and a separate totally self-checking (TSC) checker. Each of these portions is implemented as a combination of an Evolution block and an Execution block. Comparison of code vectors being transferred between the blocks of the portions enables providing a totally self-checking property. The self-checking CU is implemented in a form of a one-rail network of interconnected pre-designed LUT-based configurable logical blocks. The self-checking checker is a Sum-Of-Minterms based checker. The proposed technique: a) does not require any encoding of output words; and b) uses one-rail design, thereby drastically decreasing the required overhead.