Search

Physically unclonable functions(PUFs) emerged as a stable hardware security primitive which utilizes the intrinsic complexity and irreproducibility property of the circuit by extracting the unique signature specific to the underling hardware. PUF maps challenges to unique responses. PUF is a powerful alternative to the traditional cryptographic approach of storing secret key in non-volatile memory, as PUFs are not explicitly stored, rather can be regenerated when necessary.CMOS PUF suffers from reliability and susceptibility issues. Memristor, leveraging nanotechnological platform and high nonlinear behavior can be an efficient alternative. This paper proposes memristive polimino PUF based on symmetric functions. The proposed model provide higher degree of complexity and simulation time for the attacker, yet exploiting the simple algorithm of symmetric functions. The experimental results show the correctness of our proposal.

We focus on a set of r-valued n-variable functions that are defined by a partition P on the set of rn input vectors. Specifically, each block of P specifies input vectors, all of which map to the same function value. For example, a symmetric function is defined by a partition where input vectors in the same block are permutations of each other. Given the partition P and the set S of functions associated with P, we analyze the set S' of functions that are a maximal distance from S. Such functions hold promise for use in crypto-systems.In this paper, we characterize functions in S'. From this, we compute the distance to their corresponding partition functions. We show that, when r and n increase without bound, this distance approaches the maximum possible, rn. Bent functions achieve only half the maximum possible distance when n is large. We show that functions a maximal distance from partition functions tend to have a uniform distribution across the r possible function values. Such functions tend to be immune to statistics-based attacks. Finally, we show that, if the set S' of functions is maximally distant from a set S of partition functions, then the converse is true; that is, S is maximally distant from S'.

In traditional depth from defocus (DFD) models, the blur kernel is a symmetric function whose width is proportional to the absolute distance in diopters between the scene point and the focal plane. A symmetric blur kernel implies a two-fold front-back ambiguity in the depth estimates, however. To resolve this ambiguity using only a single image of a scene, one typically introduces an asymmetry into the optics. Here we propose a fast and simple solution which uses a Transmissive Diffraction Mask (TDM), namely a transmissive grating placed directly in front the sensors. The grating is vertically oriented with a period of two pixels, and yields two interleaved images which both have asymmetric blur kernels. The sum of the two kernels behaves like a traditional symmetric blur kernel, and so we can apply a classical single-image edge-based DFD method to the sum of the two TDM images to estimate depth up to a sign ambiguity at each point. We then show how to use the difference of the two TDM images to resolve this sign ambiguity. The result is a sparse depth map which one can interpolate to a dense depth map using standard techniques.

Symmetric Simplicial (SS) PWL functions can be used to implement nonlinear functions with high power and area efficiency in VLSI architectures. However, they have a representation limitation, since they can only implement symmetric functions. In this paper we propose a method to achieve generic piecewise-linear (PWL) functions in an efficient way, no limited to symmetrical functions, by using a combination of Symmetric Simplicial (SS) PWL functions. We present preliminary results in 2 and 3-dimensional domains.

The asymmetry of a function $f(x_{1},\ x_{2},\ \ldots,\ x_{n})$ is the fewest elements of the range of $f$ that must be changed so that $f$ becomes a symmetric function. The functions with maximal asymmetry for the case of r-valued n-variable functions have been characterized and counted for $r=2$ in two previous papers. In this paper, we extend these results to $r > 2$ . We do this for two types of symmetry, functions whose value is unchanged by 1) any permutation of the variable labels and by 2) any permutation of variable labels and variable values. We also derive the maximum possible asymmetry. We show that, as $n\rightarrow\infty$ and $r$ is fixed, the maximum asymmetry approaches $(r-1)r^{n-1}$ .

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt{n}) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma_2 norm) of F: X x Y -> {0,1} grows by a factor of Omega~(sqrt{n}) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrt{n}) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well., 46 pages; to appear at FOCS 2018

Let $\mathbb{Z}_{m}\overset{\text{def}}{=}\{0,1, \ldots, (m-1)\}$ be the m-ary alphabet, $m\in \mathbb{N}$ . This paper gives some new theory and efficient designs of $\mathbb{Z}_{m}$ linear error control codes based on the elementary symmetric functions of m-ary words. Here, a $\mathbb{Z}_{m}$ linear code is a sub-module of the module $(\mathbb{Z}_{m}^{n}, +\text{mod}\ m, \mathbb{Z}_{m}, \cdot \text{mod}\ m), n\in \mathbb{N}$ , and the errors are measured in the $L_{1}$ or Lee metric. In particular, given a field, K, of characteristic $p$ = char(K) = $2, 3,5, \ldots$ prime, and given $d, m=vp^{l}, v, l, n\in \mathbb{N}$ with $d\leq m/v=p^{l}$ and $n\leq\vert K\vert -1$ , we introduce a new class of (d-1) asymmetric error correcting $\mathbb{Z}_{m}$ linear codes, $\mathcal{C}_{d}$ , of length $n$ whose redundancy is only $\rho(\mathcal{C}_{d})=n-\log_{m}\vert\mathcal{C}_{d}\vert \leq(d-1)\log_{m}\vert K\vert$ . For these codes we give very efficient field based algebraic decoding algorithms to control $d - 1$ errors actually in the Lee distance. Also for the extended codes, we give new efficient field based decoding algorithms.

The concept of rotation symmetric functions from the Boolean domain is extended to the multiple-valued (MV) domain. It is shown that symmetric functions are a subset of the rotation symmetric functions. Functions exhibiting these kinds of symmetry may be given a compact value vector representation. It is shown that the Reed-Muller-Fourier spectrum of a function preserves the kind of symmetry and therefore it may be given a compact vector representation of the same length as the compact value vector of the corresponding function. A method is presented for calculating the RMF spectrum of symmetric and rotation symmetric functions from their compact representations.

Decomposition properties of symmetric Boolean functions, represented with the help of the set-theoretical procedures (q-partition minterms) and constructions (decomposition clones), allowed to simplify logic synthesis of digital combinational circuits. Advantages of the presented set-theoretical approach based on the q-partition minterms are illustrated on the example of logical synthesis of the digital circuit on the basis of the programmable module of FPGA.

The paper considers a class of symmetric Boolean functions called Reed-Muller type Fundamental Symmetric Functions, it reviews some of their properties and presents some new ones. The main contribution of the paper is a proof that the Reed-Muller transform of a symmetric Boolean function is also symmetric and that of a rotation symmetric Boolean function is also rotation symmetric. Since symmetric n-place Boolean functions may be given a compact representation with a value vector of n+1 elements and this holds also for its Reed-Muller spectrum, some methods are reviewed, to calculate the Reed-Muller spectrum of a symmetric Boolean function based on its compact value vector. Furthermore a method is presented to calculate the Reed-Muller spectrum of a rotation symmetric Boolean function from the compact value vector representation of the function.

The self-dual graph is a beautiful topic in graph theory. Based on DeMorgan's theorem, all CMOS circuits are series-parallel graphs. Thus self-dual graphs are few in CMOS circuits. The paper reveals a self-dual diamond-graph CMOS H-bridge circuit family, and then displays the characteristics and properties of the self-dual graphs on CMOS circuits. A basic diamond graph makes an H-bridge on the circuit. A complementary H-bridge which exists separately in p-tree or n-tree can construct various series or parallel forms for different functions. Because of the structure duality, all self-dual graph CMOS circuits can produce symmetric AOI and OAI functions, and the number of AOI and OAI functions is equal. For example, if a self-dual graph CMOS circuit can build AOI422 function, the circuit must also can make OAI422 function. Thus the self-dual graph CMOS circuits can realize symmetric function generators. Due to the above features, the self-dual graph CMOS circuits are suitable for intelligent signal processing and configurable computing.

The current European space launcher ARIANE 5 has an avionics system designed in the 90's. Possible benefits of introducing Integrated Modular Avionics (IMA) to it have been investigated with a model-based optimization approach. From this investigation two novel features for avionics architecture optimization are presented, first, a method for logically structured allocation and, second, a method symmetric function allocation. IMA are state-of-the art in large aircraft. The high degree of freedom in software allocation sizing and placement makes an optimal manual planning, however, hardly possible. Optimization algorithms achieve objectively better results, but their results often lack non-functional requirements which are inherently incorporated in manual designs. For an existing avionics architecture optimization framework extensions are presented, which improve the convenience, quality, and subjective attractiveness of automatically derived architectures. All features are demonstrated for an IMA-based avionics architecture optimization for the ARIANE 5 and future launchers. The solution quality, optimization time, and subjective impressions are analyzed. It is shown how the extended optimization methods help to improve fragmentation and sensor distances by 14% and 24% respectively without degrading the primary design objective.

The problem of eliminating harmonics with total harmonic distortion minimizing in a switching converter is considered. Existing popular methods for solving the problem were analyzed. Conventional implementations of harmonic elimination technique given not all possible solution to this problem. In this paper, the basic algebraic properties of the optimal pulse modulation problem for single-phase inverters are revealed. A new solution of this problem based on straight-line searching method and properties of symmetric functions was proposed. The result for bipolar pulse modulation scheme to eliminate the 3th harmonic was presented.

This paper introduces a new three-stage circuit structure for synthesizing symmetric Boolean functions. The first stage of the proposed method improves upon an earlier approach to the synthesis of a special class of symmetric functions, known as matriochka symmetric functions. The second stage realizes the elementary symmetric functions from the matriochka symmetric functions of the first stage. Finally, in the third stage of the design, these elementary symmetric functions are used to synthesize any arbitrary symmetric function. Experiments on several benchmark functions show a reduction in circuit area compared to earlier results.

In this paper, we introduce a novel method to realize symmetric functions with reversible circuits. The key idea is based on a regular cascade tree structure of reversible gates that revel efficient realization of symmetric functions. The proposed structure uses low-cost reversible gates which reduce the overall circuit design cost and produces more arbitrary symmetric functions with a little increase of garbage outputs. Our synthesis technique is more simplified compared to earlier synthesis methods. Experimental results show the effectiveness of our method.

Quantum-dot cellular automata (QCA) is a technology which has the potential of faster speed, smaller size and minimum power consumption compared to transistor based technology. In quantum-dot cellular automata, the basic elements are simple cells. The cells are used to construct majority voter gate, inverter and wire. This paper utilizes the unique characteristics of QCA majority voter gate to realize symmetric functions. In this paper, we introduce a synthesis technique for implementing totally symmetric Boolean functions using Quantum-dot Cellular Automata (QCA) logic. First, a simple regular module is designed to synthesize unate symmetric functions. The structure uses 3-input majority voter gates. General symmetric Boolean functions are then realized following a unate decomposition method. We study the synthesis of some well known benchmark symmetric functions using the proposed method. The designs are simulated and the simulation result indicates the complexity, area and delay of the proposed designs.

In this paper, we propose a method to realize symmetric binary functions as quaternary quantum/reversible circuits. In contrast to the existing binary synthesis methods, our design in quaternary domain offers a simple and regular cascade structure composed of quaternary quantum modules which enables significant reductions with respect to number of lines, levels and quantum costs. Further, a method to obtain an optimal realization is presented, this uses a few special quaternary quantum modules of low quantum cost. Experimental results confirm that our new method leads to realizations in quaternary domain with a significant reduction in number of lines, levels and quantum cost compared to the existing approaches in binary domain. Hence, our design in quaternary logic offers a useful alternative to existing designs in binary logic for realizing symmetric functions.

In this paper we provide a definition and characterisation of negative imaginary systems for not necessarily rational but symmetric transfer functions along the same lines of the classic definition of positive real systems. We then derive a necessary and sufficient condition that characterises symmetric negative imaginary transfer functions in terms of a matrix sign condition on the imaginary axis.

One major cause of the error explosion is the overestimation of a non-affine function introducing a new noise symbol term with non-minimum coefficient. This paper proposes theorems and its proofs to construct the best univariate affine approximation to a non-affine function in the exception case, Signed-symmetric function, that the existing theorem is not sufficient to determine the optimum one. And, as the result, it shows the use by evaluating the power function and approximating sine function.

International audience; This paper is concerned with the fast and accurate evaluation of elementary symmetric functions. We present a new compensated algorithm by applying error-free transformations to improve the accuracy of the so-called Summation Algorithm, which is used, by example, in the MATLAB's poly function. We derive a forward round off error bound and running error bound for our new algorithm. The round off error bound implies that the computed result is as accurate as if computed with twice the working precision and then rounded to the current working precision. The running error analysis provides a shaper bound along with the result, without increasing significantly the computational cost. Numerical experiments illustrate that our algorithm runs much faster than the algorithm using the classic double-double library while sharing similar error estimates. Such an algorithm can be widely applicable for example to compute characteristic polynomials from eigen values. It can also be used into the Rasch model in psychological measurement.

This paper gives some new theory and design of codes capable of correcting/detecting errors measured under the Lee distance defined over m-ary words, m Є IN. Based on the elementary symmetric functions (instead of the power sums), a key equation is derived which can be used to design new symmetric (or, asymmetric) error control algorithms for some new and already known error control codes for the Lee metric. In particular, it is shown that if K is any field with characteristic char(K) = p, p odd, and u, h, n, m = uph, t Є IN are such that n ≤ (|K| − 1)/2 and t ≤ (ph − 1)/2 then there exist m-ary codes C of length n and cardinality |C| ≥ mn/|Κ|t which are capable of, say, correcting t symmetric errors (i. e., the minimum Lee distance of C is d Lee (C) ≥ 2t + 1) with t steps of the Extended Euclidean Algorithm. Furthermore, if t ≤ (p − 1)/2 then some of these codes are (essentially) linear and, hence, easy to encode.

In the query model of multi-variate function computation, the values of the variables are queried sequentially, in an order that may depend on previously revealed values, until the function's value can be determined. The function's computation query complexity is the lowest expected number of queries required by any query order. Instead of computation, it is often easier to consider verification, where the value of the function is given and the queries aim to verify it. The lowest expected number of queries necessary is the function's verification query complexity. We show that for all symmetric functions of independent binary random variables, the computation and verification complexities coincide. This provides a simple method for finding the query complexity and the optimal query order for computing many functions. We also show that if the symmetry condition is removed, there are functions whose verification complexity is strictly lower than their computation complexity, and mention that the same holds when the independence or binary conditions are removed.

Based on the elementary symmetric functions, this paper gives a new wide class of Goppa like codes capable of correcting/detecting errors measured under the (symmetric) L\ distance defined over the m-ary words, 2 ≤ m ≤ +∞. All these codes can be efficiently decoded by algebraic means with the Extended Euclidean Algorithm (EEA). In particular it is shown that if K is any field with characteristic char(K) ≠ 2, m Є IN U {+∞} and n, t Є IN then there exist m-ary codes C of length n ≤ (|K|− 1)/2 and cardinality |C| ≥ mn/|K|t which are capable of, say, correcting t errors (i. e., the minimum L 1 distance of C is d L1 (C) ≥ 2t + 1) with t steps of EEA. Also, if K is a finite field and 2t + 1 ≤ char(K) ≠ 2 then some of these codes are (essentially) linear and, hence, easy to encode.

We make a step towards characterizing the boolean functions to which isomorphism can be efficiently tested. Specifically, we prove that isomorphism to any boolean function on $\{0, 1\}^n$ with a polynomial number of distinct permutations can be tested with a number of queries that is independent of~$n$. We also show some partial results in the converse direction, and discuss related problems: testing isomorphism up to linear transformations, and testing isomorphism against a uniform (hyper)graph that is given in advance. Our results regarding the latter topic generalize a theorem of Fischer (SICOMP 2005), and in the process we also provide a simpler proof of his original result which avoids the use of Szemer\'edi's regularity lemma.

A new form of symmetrical measurement equation based on homogeneous symmetric function has been proposed for tracking of multiple targets. The observability condition and noise statistics have been derived for proposed measurement equation. A case study of three particles in motion is considered where positions and velocities of the particles are estimated using extended Kalman filter. It has been found that the track labeling is lost during estimation. The target tracks have been labeled by minimizing sum of square errors over the permutation of states. The performance is compared in terms of root mean square error (RMSE) with sum of product and sum of power form of symmetric measurement equations. From simulation it is observed that RMSE of position and velocity in homogeneous symmetric measurement equation are smaller than that of obtained from sum of power and product form.

A new method for identification of symmetric switching functions is proposed. The proposed method exploits the Shannon's decomposition theory to reduce the space-time complexity in symmetric switching function identification. The method is applicable for literals as well. The set of true min-terms are bi-partitioned into two subsets depending upon the polarity of a particular variable. This reduces the search space for symmetry detection.

The problems of filtering, spectral analysis and spectral estimation have been investigated on the sphere using azimuthally symmetric functions as kernels which treat all the directions uniformly. In this work, we extend the concentration problem on the sphere for an azimuthally non-symmetric spatial region on the sphere. Our approach is different in a sense that we obtain the family of spatially concentrated bandlimited mutually orthogonal functions by maximizing the contribution of spherical harmonics components of all degrees and orders within the spectral bandwidth. We also provide analysis of the eigenfunctions for different bandwidths and non-symmetric regions and illustrate the concentration of eigenfunctions with the help of examples. Also we formulate the definition of filtering using azimuthally non-symmetric functions. The proposed eigenfunctions can be used to revisit the problems of estimation, localized spectral analysis, smoothing and filter design on the sphere.

We study algorithms for the {\sc Sub modular Multiway Partition}problem (\SubMP). An instance of \SubMP consists of a finite ground set $V$, a subset $S = \{s_1,s_2,\ldots,s_k\} \subseteq V$ of $k$elements called terminals, and a non-negative sub modular set function$f:2^V\rightarrow \mathbb{R}_+$ on $V$ provided as a value oracle. The goal is to partition $V$ into $k$ sets $A_1,\ldots,A_k$ to minimize $\sum_{i=1}^kf(A_i)$ such that for $1 \le i \le k$, $s_i \inA_i$. \SubMP generalizes some well-known problems such as the {\scMultiway Cut} problem in graphs and hyper graphs, and the {\scNode-weighed Multiway Cut} problem in graphs. \SubMP for arbitrary sub modular functions (instead of just symmetric functions) was considered by Zhao, Nagamochi and Ibaraki \cite{ZhaoNI05}. Previous algorithms were based on greedy splitting and divide and conquer strategies. In recent work \cite{ChekuriE11} we proposed a convex-programming relaxation for \SubMP based on the Lov\'asz-extension of a sub modular function and showed its applicability for some special cases. In this paper we obtain the following results for arbitrary sub modular functions via this relaxation. \begin{itemize} \item A $2$-approximation for \SubMP. This improves the $(k-1)$-approximation from \cite{ZhaoNI05}. \item A $(1.5-\frac{1}{k})$-approximation for \SubMP when $f$ is {\em symmetric}. This improves the $2(1-\frac{1}{k})$-approximation from \cite{Queyranne99, ZhaoNI05}.\end{itemize}

The problem of finding optimal querying policy, for expected query complexity of symmetric boolean threshold functions was solved in [1] in the context of collocated networks. In this paper, instead of considering the optimal policy to compute the functions, we define the problem of verification of the function value. We use this idea to provide a simpler proof of the optimal querying policy for threshold functions. The method is more generic and is extended to delta and some other symmetric functions. We also provide some partial results for interval functions and finally address a question posed in [1]. Recently we have extended these results to any symmetric function of boolean inputs, which we mention at the end.

In this paper we give a new upper bound on the minimal degree of a nonzero Fouriercoefficient in any non-linear symmetric Boolean function. Specifically, we prove that forevery non-linear and symmetric $f:\B^{k}\to\B$ there exists a set $\emptyset\neqS\subset[k]$ such that $|S|=O(\Gamma(k)+\sqrt{k})$, and $\hat{f}(S)\neq0$, where$\Gamma(m)\leq m^{0.525}$ is the largest gap between consecutive prime numbers in$\{1,\ldots,m\}$. As an application we obtain a new analysis of the PAC learningalgorithm for symmetric juntas, under the uniform distribution, of Mossel et al. [JCSS,2004]. Namely, we show that the running time of their algorithm is at most$n^{O(k^{0.525})}\cdot\poly(n,2^{k},\log(1/\delta))$ where $n$ is the number ofvariables, $k$ is the size of the junta (i.e. number of relevant variables) and $\delta$is the error probability. In particular, for $k\geq\log(n)^{1/(1-0.525)}\approx\log(n)^{2.1}$ our analysis matches the lower bound $2^k$ (up to polynomial factors).\sloppy Our bound on the degree greatly improves the previous result of Kolountzakis etal. [Combinatorica, 2009] who proved that $|S|=O(k/\log k)$.

Auto symmetric functions are a class of Boolean functions whose regular structure can be exploited by synthesis algorithms in order to reduce the minimization time and to derive more compact algebraic forms. In this paper we propose a generalization of this class of functions to the multiple-valued logic framework. We also study the spectral properties of auto symmetric functions and provide a complete spectral characterization for both the Boolean and the multiple-valued setting.

This paper considers the following network computation problem: n nodes are placed on a √n×√n grid, each node is connected to every other node within distance r(n) from itself, and is given an arbitrary input bit. Nodes communicate with each other so that finally a designated sink node can compute a target function f of the input bits. We focus on computing the identity function and the class of symmetric functions under two different communication models. We first consider a noiseless model where links are independent and noise-free, suitable for modeling wired networks. Next, we study a noisy broadcast model in which when a node transmits a bit, each of its neighbors receives a noisy copy of the bit. This is a simple model for wireless communications, originally proposed by El Gamal (1987). We use the protocol model for interference and nodes which do not share neighbors are allowed to transmit simultaneously. For every connection radius r(n), we present lower bounds on the minimum number of transmissions and the minimum number of time slots required to compute f. We then describe efficient protocols which can match both these lower bounds up to a constant factor.

We introduce a class of spectral shape signatures constructed from symmetric functions on the eigenfunctions of the Laplacian exponentially weighted by their eigenvalues. Such a construction is motivated by problems that arise in the use of the eigenfunctions for shape comparison, such as indeterminacies in the choice of signs and the particular ordering in which the eigenfunctions are presented. The spectral invariants are applied to the analysis of Alzheimer's disease (AD) data collected by the Alzheimer's Disease Neuroimaging Initiative, in particular, to the problem of determining whether the signatures can aid in early detection of AD through morphology and imaging.

In this paper a hysteresis model based upon an extended classical scalar Preisach hysteresis model is introduced. It is extended by the consideration of an offset of the hysteresis, because the Preisach function is a symmetric function and the consideration of an offset is one way to include a means to be able to model unsymmetric hysteresis.

In this paper, we present a study of the cryptographic properties of symmetric Boolean functions, especially of the propagation properties. We point that the value of autocorrelation functions of a symmetric function are equal when they have fixed Hamming weight. Furthermore, we extensively study the propagation properties of symmetric functions by giving the algebraic normal forms of the derivatives of a symmetric function with respect to any vectors.

We address the problem of finding optimal strategies for computing Boolean symmetric functions. We consider a collocated network, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and we wish to compute a given Boolean function of these measurements with zero error. We allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total bits to be communicated to perform the desired computation. We restrict attention to the class of symmetric Boolean functions, which only depend on the number of 1s among the n measurements. We define three classes of functions, namely threshold functions, delta functions and interval functions. We provide exactly optimal strategies for the first two classes, and an order-optimal strategy with optimal preconstant for interval functions. Using these results, we can characterize the complexity of computing percentile type functions, which is of great interest. In our analysis, we use lower bounds from communication complexity theory, and provide an achievable scheme using information theoretic tools., Comment: 5 pages, To appear in Proceedings of the IEEE Information Theory Workshop, Cairo, January 2010

A new technique using a positive symmetric function to improve support vector machine(SVM) is presented. Firstly, the support vectors are obtained from traditional SVM. Secondly, a positive scalar function is constructed using the support vectors. Thirdly, a new kernel function is obtained from the Gaussian kernel multiplied by the positive symmetric function merged into data information. The new SVM with the new kernel is to enlarge margin around the separating hyper-plane as a result of the differential approximation theory. Therefore, the separability is increased and the support vectors are decreased. Simulation results for both artificial and real data show remarkable improvement of generalization error and computational cost.

This paper considers the following network computation problem: n nodes are placed on a √n×√n grid, each node in the network is connected to every other node within distance r(n) of itself, and is given an arbitrary input bit. Connected nodes communicate with each other over independent binary symmetric channels of a given transition probability e ≥ 0, and an arbitrarily designated node computes a symmetric target function ƒ of the input bits. We characterize up to order the minimum number of transmissions required to compute ƒ with a probability of error less than any given positive constant δ. As a side result, we answer an open question posed by El Gamal in 1987 [1] regarding the number of transmissions required to compute the parity function over ring and tree networks.

This chapter contains sections titled: Symmetric Functions Iterative Functions Realizations in Tree Form Overview and Summary Sources Problems ]]>

Identification of totally symmetric function (TSF) is one of the important methods to achieve an efficient system design with minimized cost. Finding TSF is sometimes very useful in the application like VLSI testing, logic and physical deign, cryptology etc. apart from its wide use in optimization problems. McCluskey had already established the method of decomposition to compute TSF. Later Biswas came up with an enhanced approach using the method of ordered partition, but the method suffers from excessive and complex computation for functions with large number of variables. We, in this paper, claim that some of Biswas's assertions for finding TSF and its related theorems are incorrect and also logically prove our claim. We also propose a new efficient and simpler solution for finding TSF in much fewer steps than Biswas's method. Result and examples show that the proposed technique works significantly faster than the Biswas's method with the gain of 43% in computational speed.

The functional completeness problems of the partial K-valued logic functions have a wide range of applications including cryptography and the real combinatorial circuits design. It includes the decision and construction for Sheffer functions in P, and the solution of the problems depends on determining all precomplete classes in P, and reduces to determine the minimal cover of the union of all precomplete classes in P. An n-ary function f is a Sheffer function if and only if f does not belong to any other precomplete classes in P. Hence, it is important to determine the minimal cover of the union of all precomplete classes on partial K-valued logic functions in on studying Sheffer Function. In this paper, some full symmetric function sets (m=k)are proved to be the component of the minimal cover of the union of all precomplete classes in P.

Shape representations using polynomials in computer-aided geometric design (CAGD) and computer graphics are ubiquitous. This paper shows that any bivariate polynomial p(t,u) of total degree d les n can be represented in the form of a blossom of another bivariate polynomial b(t, u) of total degree d evaluated off the diagonal at the linear function pairs (Xj(t),Yj(u)), j = 1,... ,n, chosen under some conditions expressed in terms of symmetric functions. The bivariate polynomial b(t,u) is called a bud of the bivariate polynomial p(t,u). An algorithm for finding a bud b(t,u) of a given bivariate polynomial p(t,u) is presented. Successively, a bud of b(t, u) can be computed and so on, to form a sequence of representations. The information represented by the original bivariate polynomial is preserved in its buds. This scheme can be used for encoding/decoding geometric design information. The objects in the encoding/decoding sequence can be rendered graphically and manipulated geometrically like the usual parametric representations. Examples concerning triangular Bezier patches are provided as illustrations.

We present a new variant of the quantum adversary method. All adversary methods give lower bounds on the quantum query complexity of a function by bounding the change of a progress function caused by one query. All previous variants upper-bound the_difference_ of the progress function, whereas our new variant upper-bounds the_ratio_ and that is why we coin it the multiplicative adversary. The new method generalizes to all functions the new quantum lower-bound method by Ambainis [Amb05, ASW06] based on the analysis of eigenspaces of the density matrix. We prove a strong direct product theorem for all functions that have a multiplicative adversary lower bound., Comment: 15 pages, v2: removed an incorrect claim, v3: cleaned up, commented better, added stronger bound for OR

Let $$A_{1}, \ldots, A_{n}$$ be events in a probability space. The approximate inclusion-exclusion problem, due to Linial and Nisan (1990), is to estimate $${\bf P} [A_{1} \cup \ldots \cup A_{n}]$$ given $${\bf P} [\bigcap_{i\in S} A_{i}]$$ for |S| ≤ k. Kahn et al. (1996) solved this problem optimally for each k. We study the following more general question: estimate $${\bf P} [f(A_{1}, \ldots, A_{n})]$$ given $${\bf P} [\bigcap_{i\in S} A_{i}]$$ for |S| ≤ k, where f : {0, 1} n → {0, 1} is a given symmetric function. We solve this general problem for every f and k, giving an algorithm that runs in polynomial time and achieves an approximation error that is essentially optimal. We prove this optimal error to be $$2^{-\tilde\Theta(k^{2}/n)}$$ for k above a certain threshold, and $$\Theta(1)$$ otherwise. As part of our solution, we analyze, for every nonconstant symmetric f : {0, 1} n → {0, 1} and every $$\epsilon \in [2^{-n}, 1/3]$$ , the least degree $${\rm deg}_{\epsilon}(f)$$ of a polynomial that approximates f pointwise within $$\epsilon$$ . We show that $${\rm deg}_{\epsilon}(f) = \tilde\Theta({\rm deg}_{1/3}(f) + \sqrt{n {\rm log}(1/\epsilon))}$$ , where deg1/3(f) is well-known for each f. Previously, the answer for vanishing $$\epsilon$$ was known only for f = OR. We construct the approximating polynomial explicitly for all f and $$\epsilon$$ .

In this paper, a simple and robust method for frequency estimation of multi-sinusoidal signal from a given discrete sequence of noisy data is proposed. The approach used herein is based on the algebraic derivative method in the frequency domain and it does not make any assumption on the way to collect the samples of the considered signal. The frequencies are estimated without iterations, and explicit relationship between the elementary symmetric functions on the frequencies of the signal and its multiple integrals is given. Due to the use of the process output integrals, the resulting parameters estimation is very robust in the face of large measurement noise in the output. Moreover, for an easy time realization of the estimation, a time-varying linear (unstable) filter is proposed. Finally, the effectiveness of the proposed method is demonstrated through practical and simulated experiments.

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'number on the forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the degree-discrepancy lemma in the recent work of Sherstov (2007). Using this we prove that depth three circuits consisting of a MAJORITY gate at the output, gates computing arbitrary symmetric function at the second layer and arbitrary gates of bounded fan-in at the base layer i.e. circuits of type MAJ o SYMM o ANYO(1) cannot simulate the circuit class AC0 in sub-exponential size. Further, even if the fan-in of the bottom ANY gates are increased to o(log log n), such circuits cannot simulate AC0 in quasi-polynomial size. This is in contrast to the classical result of Yao and Beigel-Tarui that shows that such circuits, having only MAJORITY gales, can simulate the class ACC0 in quasi-polynomial size when the bottom fan-in is increased to poly-logarithmic size. In the second part, we simplify the arguments in the breakthrough work of Bourgain (2005) for obtaining exponentially small upper bounds on the correlation between the boolean function MODq and functions represented bv polynomials of small degree over Zm, when m,q ges 2 are co-prime integers. Our calculation also shows similarity with techniques used to estimate discrepancy of functions in the multiparty communication setting. This results in a slight improvement of the estimates of Bourgain et al. (2005). It is known that such estimates imply that circuits of type MAJ o MODm o ANDisin log n cannot compute the MODq function in sub-exponential size. It remains a major open question to determine if such circuits can simulate ACC0 in polynomial size when the bottom fan-in is increased to poly-logarithmic size.