检索结果-内蒙古大学图书馆

threshold functions, node isolation, and emergent Lacunae in sensor networks

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第12期52卷 5352-5372页

作者： Kunniyur, Srisankar S. Venkatesh, Santosh S. Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA

A geometrically random network of sensors is obtained by modeling sensors as random points in the unit disc equipped with a local sensing capability and the ability to communicate with other sensors in their vicinity. Node extinctions in the network representing the finite battery lifetimes of the sensors are modeled as a sequence of independent random variables governed by a common probability distribution parametrized by the sensing and communication radii of the sensor nodes. Following its establishment, the devolution of the network with time is characterized by the appearance first of isolated nodes, then the growth of sensory lacunae or dead spots in the sensor field, and, eventually, a breakdown in connectivity between survivors. It is shown that these phenomena occur very sharply in time, these phase transitions occurring at times characteristic of the underlying probability law governing lifetimes. More precisely, it is shown that as the number of sensors grows there exists a critical point in time determined solely by the lifetime distribution at which the number of emergent lacunae of a given size is asymptotically Poisson.

关键词： graph connectivity inclusion-exclusion phase transitions Poisson paradigm random graphs sensor networks threshold functions

来源：评论

学校读者我要写书评

暂无评论

threshold functions for asymmetric Ramsey properties involving cycles

引用

RANDOM STRUCTURES & ALGORITHMS 1997年第3期11卷 245-276页

作者： Kohayakawa, Y Kreuter, B UNIV SAO PAULO INST MATEMAT & ESTATBR-05508900 SAO PAULOBRAZIL

We consider the binomial random graph G(p) and determine a sharp threshold function for the edge-Ramsey property G(p) --> (C-l1,...,C-lr) for all l(1),...,l(r), where C-l denotes the cycle of length l. As deterministic consequences of our results, we prove the existence of sparse graphs having the above Ramsey property as well as the existence of infinitely many critical graphs with respect to the property above. (C) 1997 John Wiley & Sons, Ins.

关键词： Ramsey theory random graphs threshold functions Szemeredi's lemma cycles

来源：评论

学校读者我要写书评

暂无评论

Decomposition of threshold functions into bounded fan-in threshold functions

引用

INFORMATION AND COMPUTATION 2013年 227卷 84-101页

作者： Annampedu, Viswanath Wagh, Meghanad D. LSI Corp Serdes Architecture Allentown PA 18109 USA Lehigh Univ Dept Elect & Comp Engn Bethlehem PA 18015 USA

This paper obtains explicit decomposition of threshold functions into bounded fan-in threshold functions. A small fan-in is important to satisfy technology constraints for large scale integration. By employing the concept of error in the threshold function, we are able to decompose functions in LT1 into a network of size O(n(c)/M-2) and depth O(log(2)n/logM) where n is the number of inputs of the function and M is the fan-in bound. The proposed construction enables one to trade-off the size and depth of the decomposition with the fan-in bound. Combined with the work on small weight threshold functions, this implies polynomial size, log(2) depth bounded fan-in decompositions for arbitrary threshold functions in LTd. These results compare favorably with the classical decomposition which has a size O(2(n-M)) and depth O(n-M). We also show that the decomposition size and depth can be significantly reduced by exploiting the relationships between the input weights. As examples of this strategy, we demonstrate an O(n(2)/M) size decomposition of the majority function and, O(n/M) size decompositions of an error tolerant pattern matching function and the comparison function. In all these examples, except for the first level, all other levels use only majority functions. (C) 2013 Elsevier Inc. All rights reserved.

关键词： threshold functions Decomposition Bounded fan-in Majority logic Comparison function

来源：评论

学校读者我要写书评

暂无评论

Algebraic techniques for constructing minimal weight threshold functions

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2003年第1期16卷 114-126页

作者： Bohossian, V Bruck, J CALTECH Pasadena CA 91125 USA

A linear threshold element computes a function that is a sign of a weighted sum of the input variables. The best known lower bounds on the size of threshold circuits are for depth-2 circuits with small (polynomial-size) weights. However, in general, the weights are arbitrary integers and can be of exponential size in the number of input variables. Namely, obtaining progress in lower bounds for threshold circuits seems to be related to understanding the role of large weights. In the present literature, a distinction is made between the two extreme cases of linear threshold functions with polynomial-size weights, as opposed to those with exponential-size weights. Our main contributions are in devising two novel methods for constructing threshold functions with minimal weights and filling up the gap between polynomial and exponential weight growth by further refining the separation. Namely, we prove that the class of linear threshold functions with polynomial-size weights can be divided into subclasses according to the degree of the polynomial. In fact, we prove a more general result-that there exists a minimal weight linear threshold function for any arbitrary number of inputs and any weight size.

关键词： threshold functions computational complexity neural networks

来源：评论

学校读者我要写书评

暂无评论

On the fast algebraic immunity of threshold functions

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN functions AND SEQUENCES 2021年第5期13卷 741-762页

作者： Meaux, Pierrick Catholic Univ Louvain ICTEAM ELEN Crypto Grp Louvain La Neuve Belgium

Motivated by the impact of fast algebraic attacks on stream ciphers, and recent constructions using a threshold function as main part of the filtering function, we study the fast algebraic immunity of threshold functions. As a first result, we determine exactly the fast algebraic immunity of all majority functions in more than 8 variables. Then, For all n >= 8 and all threshold value between 1 and n we exhibit the fast algebraic immunity for most of the thresholds, and we determine a small range for the value related to the few remaining cases. Finally, provided m >= 2, we determine exactly the fast algebraic immunity of all threshold functions in 3 . 2(m) or 3 . 2(m) + 1 variables.

关键词： Boolean functions Fast algebraic attacks Symmetric functions threshold functions

来源：评论

学校读者我要写书评

暂无评论

On encoding and enumerating threshold functions

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2004年第2期15卷 261-267页

作者： Zunic, J Univ Exeter Dept Comp Sci Exeter EX4 4QF Devon England Serbian Acad Arts & Sci Math Inst Belgrade Serbia

In this paper, we deal with encoding and enumerating threshold functions defined on n-dimensional binary inputs. The paper specifies situations in which the unique characterization of functions from a given class is preserved by usage of an appropriate set of discrete moments. Moreover, sometimes such a characterization (coding) is optimal with respect to the number of necessary bit rate per coded function. By estimating the number of possible values of the discrete moments used, several upper bounds (for different classes of threshold functions) are derived, some of which are better than those previously known.

关键词： discrete moments encoding enumerating neural networks threshold functions

来源：评论

学校读者我要写书评

暂无评论

POLYNOMIAL threshold functions AC0 functions, AND SPECTRAL NORMS

引用

SIAM JOURNAL ON COMPUTING 1992年第1期21卷 33-42页

作者： BRUCK, J SMOLENSKY, R UNIV TORONTO DEPT COMP SCITORONTO M5S 1A4ONTARIOCANADA

This paper examines the class of polynomial threshold functions using harmonic analysis and applies the results to derive lower bounds related to AC0 functions. A Boolean function is polynomial threshold if it can be represented as the sign of a sparse polynomial (one that consists of a polynomial number of terms). The main result of this paper is that the class of polynomial threshold functions can be characterized using their spectral representation. In particular, it is proved that an n-variable Boolean function whose L1 spectral norm is bounded by a polynomial in n is a polynomial threshold function, while a Boolean function whose L infinity-1 spectral norm is not bounded by a polynomial in n is not a polynomial threshold function [J. Bruck, SIAM J. Discrete Math., 3 (1990), pp. 168-177]. The motivation is that the characterization of polynomial threshold functions can be applied to obtain upper and lower bounds on the complexity of computing with networks of linear threshold elements. In this paper results related to the complexity of computing AC0 functions are presented. More applications of the characterization theorem are presented in [J. Bruck, SIAM J. Discrete Math., 3 (1990), pp. 168-177] and [K. Y. Siu and J. Bruck, SIAM J. Discrete Math., 4 (1991), pp. 423-435].

关键词： BOOLEAN functions threshold functions AC0 functions HARMONIC ANALYSIS COMPLEXITY

来源：评论

学校读者我要写书评

暂无评论

Secure Computation for threshold functions with Physical Cards: Power of Private Permutations

引用

NEW GENERATION COMPUTING 2022年第1期40卷 95-113页

作者： Nakai, Takeshi Shirouchi, Satoshi Tokushige, Yuuki Iwamoto, Mitsugu Ohta, Kazuo Univ Electrocommun Grad Sch Informat & Engn 1-5-1 Chofugaoka Chofu Tokyo 1828585 Japan Natl Inst Adv Ind Sci & Technol Cyber Phys Secur Res Ctr Koto Ku 2-3-26 Aomi Tokyo 1350064 Japan

Card-based cryptography is a variant of multi-party computation using physical cards like playing cards. There are two models on card-based cryptography, called public and private models. The public model assumes that all operations are executed publicly, while the private model allows the players private operations called private permutations (PP, for short). Much of the existing card-based protocols were developed under the public model. Under the public model, 2n cards are necessary for every protocol with n-bit input since at least two cards are required to express a bit. In this paper, we propose n-bit input protocols with fewer than 2n cards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (n-bit input) threshold function can be realized with only n + 1 cards by reducing the threshold function to the majority voting. Toward this end, we first offer that two-bit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for three-input majority voting with only four cards by observing the relationship between AND/OR operations. This protocol can be easily extended to more participants, and to the protocol for threshold functions.

关键词： Secure computation Card-based cryptography threshold functions

来源：评论

学校读者我要写书评

暂无评论

Construction of Wavelet Filtration Algorithms with Two-Parameter threshold functions

引用

OPTOELECTRONICS INSTRUMENTATION AND DATA PROCESSING 2012年第1期48卷 9-17页

作者： Voskoboinikov, Yu. E. Gochakov, A. V. Novosibirsk State Univ Architecture & Civil Engn Ul Leningradskaya 113 Novosibirsk 630008 Russia Siberian Reg Hydrometeorol Inst Novosibirsk 630099 Russia

A class of wavelet filtration algorithms with two-parameter threshold functions is considered. An algorithm is proposed for solving the problem of choosing two threshold values, which allows estimating their optimal v... 详细信息

关键词： wavelet filtration threshold functions optimal threshold value

来源：评论

学校读者我要写书评

暂无评论

Improved Approximation of Linear threshold functions

引用

COMPUTATIONAL COMPLEXITY 2013年第3期22卷 623-677页

作者： Diakonikolas, Ilias Servedio, Rocco A. Univ Calif Berkeley Berkeley CA 94720 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

We prove two main results on how arbitrary linear threshold functions over the n-dimensional Boolean hypercube can be approximated by simple threshold functions. Our first result shows that every n-variable threshold function f is -close to a threshold function depending only on many variables, where denotes the total influence or average sensitivity of f. This is an exponential sharpening of Friedgut's well-known theorem (Friedgut in Combinatorica 18(1):474-483, 1998), which states that every Boolean function f is -close to a function depending only on many variables, for the case of threshold functions. We complement this upper bound by showing that many variables are required for -approximating threshold functions. Our second result is a proof that every n-variable threshold function is -close to a threshold function with integer weights at most This is an improvement, in the dependence on the error parameter , on an earlier result of Servedio (Comput Complex 16(2):180-209, 2007) which gave a bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original result of Servedio (Comput Complex 16(2):180-209, 2007) and extends to give low-weight approximators for threshold functions under a range of probability distributions other than the uniform distribution.

关键词： threshold functions total influence average sensitivity integer-weight approximation juntas

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：