In this paper we consider the problem of computing threshold functions using directed monotone contact networks. We give constructions of monotone contact networks of size (k - 1)(n - k + 2)[log(n - k + 2)] computing ...
详细信息
In this paper we consider the problem of computing threshold functions using directed monotone contact networks. We give constructions of monotone contact networks of size (k - 1)(n - k + 2)[log(n - k + 2)] computing T(k)n, for 2 less-than-or-equal-to k less-than-or-equal-to n - 1. Our upper bound is close to the OMEGA(kn log(n/(k - 1))) lower bound for small thresholds and the k(n - k + 1) lower bound for large thresholds. Our networks are described explicitly;we do not use probabilistic existence arguments.
Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Among the many areas of application are hardware verification. model checking, and symbolic graph algo...
详细信息
Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Among the many areas of application are hardware verification. model checking, and symbolic graph algorithms. threshold functions are the basic functions for discrete neural networks and are used as building blocks in the design of some symbolic graph algorithms. In this paper the first exponential lower bound on the size of a more general model than OBDDs and the first nontrivial asymptotically optimal bound on the OBDD size for a threshold function are presented. (C) 2009 Elsevier B.V. All rights reserved.
The number of two-dimensional threshold functions was considered recently in [SIAM J. Discrete Math., 24 (2010), pp. 1617-1631]. By this note we point out that some of the results presented are easy consequences of al...
详细信息
The number of two-dimensional threshold functions was considered recently in [SIAM J. Discrete Math., 24 (2010), pp. 1617-1631]. By this note we point out that some of the results presented are easy consequences of already known results.
We consider two general frameworks for multiple domination, which are called (r, s)-domination and parametric domination. They generalise and unify {k}-domination, k-domination, total k-domination and k-tuple dominati...
详细信息
We consider two general frameworks for multiple domination, which are called (r, s)-domination and parametric domination. They generalise and unify {k}-domination, k-domination, total k-domination and k-tuple domination. In this paper, known upper bounds for the classical domination are generalised for the < r, s >-domination and parametric domination numbers. These generalisations are based on the probabilistic method and they imply new upper bounds for the {k}-domination and total k-domination numbers. Also, we study threshold functions, which impose additional restrictions on the minimum vertex degree, and present new upper bounds for the aforementioned numbers. Those bounds extend similar known results for k-tuple domination and total k-domination. (C) 2015 Elsevier By. All rights reserved.
A simple algorithm for testing the 2-summability of Boolean functions is presented in this note. The concept of asummobility has been extended and the idea of "mutual 2-asummability" has been introduced. The...
详细信息
A simple algorithm for testing the 2-summability of Boolean functions is presented in this note. The concept of asummobility has been extended and the idea of "mutual 2-asummability" has been introduced. The authors show how mutual 2-asummobility can be utilized for the testing of isobaricity of threshold functions containing no more than seven variables.
The analysis of linear threshold Boolean functions has recently attracted the attention of those interested in circuit complexity as well as of those interested in neural networks. Here a generalization of linear thre...
详细信息
The analysis of linear threshold Boolean functions has recently attracted the attention of those interested in circuit complexity as well as of those interested in neural networks. Here a generalization of linear threshold functions is defined, namely, polynomial threshold functions, and its relation to the class of linear threshold functions is investigated.
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed length log n/epsilon(O(d)) fooling degree d PTFs with error at...
详细信息
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed length log n/epsilon(O(d)) fooling degree d PTFs with error at most epsilon. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error epsilon. For the class of degree 1 threshold functions or halfspaces, previously only PRGs with seed length O(log n log(2)(1/epsilon)/epsilon(2)) were known. We improve this dependence on the error parameter and construct PRGs with seed length O(log n + log(2)(1/epsilon)) that epsilon-fool halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the n-dimensional unit sphere. The main theme of our constructions and analysis is the use of invariance principles to construct PRGs. We also introduce the notion of monotone read-once branching programs, which is key to improving the dependence on the error rate epsilon for halfspaces. These techniques may be of independent interest.
A simple way to generate a Boolean function is to take the sign of a real polynomial in variables. Such Boolean functions are called polynomial threshold functions. How many low-degree polynomial threshold functions a...
详细信息
A simple way to generate a Boolean function is to take the sign of a real polynomial in variables. Such Boolean functions are called polynomial threshold functions. How many low-degree polynomial threshold functions are there? The partial case of this problem for degree d = 1 was solved by Zuev in 1989, who showed that the number T(n, 1) of linear threshold functions satisfies log(2) T(n, 1) approximate to n(2), up to smaller order terms. However, the number of polynomial threshold functions for any higher degrees, including d = 2, has remained open. We settle this problem for all fixed degrees d >= 1, showing that log(2) T(n, d) approximate to n (<= d\bigr). The solution relies on connections between the theory of Boolean threshold functions, hyperplane arrangements, and random tensors. Perhaps surprisingly, it uses also a recent result of Abbe, Shpilka, and Wigderson on Reed-Muller codes.
This paper presents digital image segmentation techniques and algorithms using variable threshold functions. The technique is successful to detect regions with different or poor light radiances and can be applied to i...
详细信息
ISBN:
(纸本)0819453609
This paper presents digital image segmentation techniques and algorithms using variable threshold functions. The technique is successful to detect regions with different or poor light radiances and can be applied to images with occluded or noisy objects. The Variable threshold functions are derived from discrete time functions often used in digital control system design. The developed algorithms can be integrated on a single monolithic integrated circuit or implemented as an embedded system for real-time applications.
We prove new upper and lower bounds on the sample complexity of (epsilon, delta) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function c(x) over a totally ord...
详细信息
ISBN:
(纸本)9781467381918
We prove new upper and lower bounds on the sample complexity of (epsilon, delta) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function c(x) over a totally ordered domain X evaluates to c(x) (y) = 1 if y <= x, and evaluates to 0 otherwise. We give the first nontrivial lower bound for releasing thresholds with (epsilon, delta) differential privacy, showing that the task is impossible over an infinite domain X, and moreover requires sample complexity n >= Omega(log*vertical bar X vertical bar), which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with n <= 2((1+0(1))) log* vertical bar x vertical bar samples. This improves the previous best upper bound of 8(1 +0(1)) log* PC (Beimel et al., RANDOM '13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with (epsilon, delta) differential privacy and learning without privacy. For properly learning thresholds in l dimensions, this lower bound extends to n >= Omega(l . log* vertical bar X vertical bar). To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database D of elements from X, the interior point problem asks for an element between the smallest and largest elements in D. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.
暂无评论