Let RE denote randomized query complexity for error probability epsilon, and R := R-1/3. In this work we investigate whether a perfect composition theorem R(f o g(n)) = Omega(R(f) center dot R(g)) holds for a relation...
详细信息
ISBN:
(纸本)9783959773119
Let RE denote randomized query complexity for error probability epsilon, and R := R-1/3. In this work we investigate whether a perfect composition theorem R(f o g(n)) = Omega(R(f) center dot R(g)) holds for a relation f subset of {0,1}(n) x S and a total inner function g: {0,1}(m) -> {0, 1}. Composition theorems of the form R(f o g(n)) = Omega(R(f) center dot M(g)) are known for various measures M. Such measures include the sabotage complexity RS defined by Ben-David and Kothari (ICALP 2015), the max-conflict complexity defined by Gavinsky, Lee, Santha and Sanyal (ICALP 2019), and the linearized complexity measure defined by Ben-David, Blais, Goos and Maystre (FOCS 2022). The above measures are asymptotically non-decreasing in the above order. However, for total booleanfunctions no asymptotic separation is known between any two of them. Let D-prod denote the maximum distributional query complexity with respect to any product (over variables) distribution. In this work we show that for any total booleanfunction g, the sabotage complexity RS(g) = (Omega) over tilde (D-prod (g)). This gives the composition theorem R(f o g(n)) = (R(f) center dot D-prod (g)) In light of the minimax theorem which states that R(g) is the maximum distributional complexity of g over any distribution, our result makes progress towards answering the composition question. We prove our result by means of a complexity measure R-epsilon(prod) that we define for total booleanfunctions. Informally, R-epsilon(prod) (g) is the minimum complexity of any randomized decision tree with unlabelled leaves with the property that, for every product distribution it over the inputs, the average bias of its leaves is at least ((1 - epsilon) - epsilon)/2 = 1/2 - epsilon. It follows by standard arguments R-1/3(prod)(g) = Omega(D-prod (g)). We show that R-1/3(prod) is equivalent to the sabotage complexity up to a logarithmic factor. Ben-David and Kothari asked whether RS(g) = Theta(R(g)) for total functions g. W
We study the problem of certification: given queries to a function f : {0, 1}(n) ->{0, 1} with certificate complexity <= k and an input x(star), output a size-k certificate for f's value on x(star). For mono...
详细信息
ISBN:
(纸本)9781450392648
We study the problem of certification: given queries to a function f : {0, 1}(n) ->{0, 1} with certificate complexity <= k and an input x(star), output a size-k certificate for f's value on x(star). For monotone functions, a classic local search algorithm of Angluin accomplishes this task with.. queries, which we show is optimal for local search algorithms. Our main result is a new algorithm for certifying monotone functions with O (k(8) log n) queries, which comes close to matching the information-theoretic lower bound of Omega(k log n). The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions. We further prove exponential-in-k lower bounds when.. is nonmonotone, and when.. is monotone but the algorithm is only given random examples of f. These lower bounds show that assumptions on the structure of f and query access to it are both necessary for the polynomial dependence on k that we achieve.
An n-variable boolean logic function f((x) over right arrow) is sensitive to x(i) if there is at least one assignment of values to (x) over right arrow - {x(i)} such that f changes when x(i) changes. We investigate th...
详细信息
ISBN:
(纸本)9781665423953
An n-variable boolean logic function f((x) over right arrow) is sensitive to x(i) if there is at least one assignment of values to (x) over right arrow - {x(i)} such that f changes when x(i) changes. We investigate the sensitivity of boolean logic functions experimentally. For example, we show the use of a reconfigurable computer in computing the sensitivity of n-variable booleanfunctions with up through n = 5 variables. For n = 5, this computation is 192 times faster than a single Xeon microprocessor and 1.8 times faster than a cluster computer with 256 processors. We also examine sensitivity in multiple-valued logic functions.
Polynomial degree is an important measure for studying the computational complexity of booleanfunction. A polynomial P is an element of Z(m)[x] is a generalized representation off over Z(m) if for all x, y is an elem...
详细信息
Polynomial degree is an important measure for studying the computational complexity of booleanfunction. A polynomial P is an element of Z(m)[x] is a generalized representation off over Z(m) if for all x, y is an element of{0, 1}(n);f(x)not equal f(y)double right arrow P(x)not equal P(y)(mod m). Denote the minimum degree as deg(m)(ge)(f), and deg(m)(sym,ge) (f) if the minimum is taken from symmetric polynomials. In this paper we prove new lower bounds for the symmetric booleanfunctions that depend on n variables. First, let m(1) and m(2) be relatively prime numbers and have s and t distinct prime factors respectively. Then we have m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(f))(t)> n. A polynomial Q is an element of Z(m)[x] is a one-sided representation off over Z(m) if for all xe {0, 1}(n);f(x)=0 double left right arrow Q(x) 0(mod m). Denote the minimum degree among these Q as deg(m)(os) (f). Note that Q(x) can be non-symmetric. Then with the same conditions as above, at least one of m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(f))(t)> n and m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(-f))(t)> n is true.
Preprocessing the data is an important step while creating neural network (NN) applications because this step usually has a significant effect on the prediction performance of the model. This paper compares different ...
详细信息
Preprocessing the data is an important step while creating neural network (NN) applications because this step usually has a significant effect on the prediction performance of the model. This paper compares different data processing strategies for NNs for prediction of boolean function complexity (BFC). We compare NNs' predictive capabilities with (1) no preprocessing (2) scaling the values in different curves based on every curve's own peak and then normalizing to [0,1] range (3) applying z-score to values in all curves and then normalizing to [0,1] range, and (4) logarithmically scaling all curves and then normalizing to [0,1] range. The efficiency of these methods was measured by comparing RMS errors in NN-made BFC predictions for numerous ISCAS benchmark circuits. Logarithmic preprocessing method resulted in the best prediction statistics as compared to other techniques. (C) 2007 Elsevier Ltd. All rights reserved.
For boolean polynomials in Z(p) of sufficiently low degree we derive a relation expressing their values on one level set in terms of their values on another level set. We use this relation to derive linear upper and l...
详细信息
For boolean polynomials in Z(p) of sufficiently low degree we derive a relation expressing their values on one level set in terms of their values on another level set. We use this relation to derive linear upper and lower bounds, tight to within constant factor, on the degrees of various approximate majority functions, namely, functions that take the value 0 on one level set, the value 1 on a different level set, and arbitrary 0-1 values on other boolean inputs. We show sublinear upper bounds in the case of moduli that are not prime powers.
We consider small depth boolean circuits with basis {AND, OR, NOT}. We obtain lower bounds for the parity function using a relatively simple method. We prove that for any depth 3 circuit with top fan-in t, computing t...
详细信息
We consider small depth boolean circuits with basis {AND, OR, NOT}. We obtain lower bounds for the parity function using a relatively simple method. We prove that for any depth 3 circuit with top fan-in t, computing the n-variable parity function must have at least t2 n-1/t wires. Similarly, we obtain a lower bound for computing the depth 4 circuits.
We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in boolean variables over Z(m). In particular, we say that a polynomial P weakly represen...
详细信息
We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in boolean variables over Z(m). In particular, we say that a polynomial P weakly represents a booleanfunction f (both have n variables) if for any inputs x and y in {0, 1}(n), we have P(x) not equal P(y) whenever f(x) not equal f(y). Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n(1/r)) (where r is the number of distinct primes dividing m) and a lower bound of omega(1). Here, we show a lower bound of Omega(log n) when m is a product of two primes and Omega((log n)(1/(r-1))) in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal land, we argue, more natural) definition. While the degree is known to be Omega(log n) for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power.
Define the MOD(m)-degree of a booleanfunction F to be the smallest degree of any polynomial P, over the ring of integers module m, such that for all 0-1 assignments ((x) over right arrow, F((x) over right arrow) = 0 ...
详细信息
Define the MOD(m)-degree of a booleanfunction F to be the smallest degree of any polynomial P, over the ring of integers module m, such that for all 0-1 assignments ((x) over right arrow, F((x) over right arrow) = 0 iff P((x) over right arrow) = 0. By exploring the periodic property of the binomial coefficients module m, two new lower bounds on the MOD(m)-degree of the MOD(l) and -MOD(m) functions are proved, where m is any composite integer and l has a prime factor not dividing m. Both bounds improve from sublinear to Omega(n). With the periodic property, a simple proof of a lower bound on the MOD(m)-degree with symmetric multilinear polynomial of the OR function is given. It is also proved that the majority function has a lower bound n/2 and the MidBit function has a lower bound root n.
In this paper we introduce and examine some properties of a new complexity measure for booleanfunctions. Unlike classical approaches, which are largely concerned with resource requirements (see, e.g., [3]), the measu...
详细信息
In this paper we introduce and examine some properties of a new complexity measure for booleanfunctions. Unlike classical approaches, which are largely concerned with resource requirements (see, e.g., [3]), the measure examined here aims at quantifying the potential for lazy evaluation in a function, This measure is motivated by issues arising in the implementation of demand-driven logic simulators, [1], [7], [8], [12]. The range of values that can be taken by the measure is precisely identified and a lower bound on the complexity of 'almost all' booleanfunctions derived, In addition asymptotically exact values are derived for the class of all boolean symmetric functions.
暂无评论