A theorem is proved that improves a previously upper bound for the relative distance between a Boolean function of n variables and the set of
k
-dimensional functions, k < n. The proof is based on ...the Bonami-Beckner inequality.
On the Sum of L1 Influences Backurs, Arturs; Bavarian, Mohammad
2014 IEEE 29th Conference on Computational Complexity (CCC),
2014-June
Conference Proceeding
For a function f over the discrete cube, the total L1 influence of f is defined as the sum of the L1 norm of the discrete derivatives of f in all n directions. In this work, we show that in the case ...of bounded functions this quantity can be upper bounded by a polynomial in the degree of f (independently of dimension n), resolving affirmatively an open problem of Aaronson and Ambainis (ITCS 2011). We also give an application of our theorem to graph theory, and discuss the connection between the study of bounded functions over the cube and the quantum query complexity of partial functions where Aaronson and Ambainis encountered this question.
We consider the problem of finding an unknown graph by using queries with an additive property. This problem was partially motivated by DNA shotgun sequencing and linkage discovery problems of ...artificial intelligence.
Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask the sum of weights for weighted graphs.
For a graph
G with
n vertices and at most
m edges, we prove that there exists an algorithm to find the edges of
G using
O
(
m
log
n
2
m
log
(
m
+
1
)
)
queries of both types for all
m. The bound is best possible up to a constant factor. For a weighted graph with a mild condition on weights, it is shown that
O
(
m
log
n
log
m
)
queries are enough provided
m
⩾
(
log
n
)
α
for a sufficiently large constant
α, which is best possible up to a constant factor if
m
⩽
n
2
−
ε
for any constant
ε
>
0
.
This settles, in particular, a conjecture of Grebinski V. Grebinski, On the power of additive combinatorial search model, in: Proceedings of the 4th Annual International Conference on Computing and Combinatorics (COCOON 1998), Taipei, Taiwan, 1998, pp. 194–203 for finding an unweighted graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions as well as a similar coin weighing problem.
Rotation symmetric Boolean functions have been extensively studied in the last dozen years or so because of their importance in cryptography and coding theory. Until recently, very little was known ...about the basic question of when two such functions are affine equivalent. The simplest case of quadratic rotation symmetric functions which are generated by cyclic permutations of the variables in a single monomial was only settled in a 2009 paper of Kim, Park and Hahn. The much more complicated analogous problem for cubic functions was solved for permutations using a new concept of patterns in a 2010 paper of Cusick, and it is conjectured that, as in the quadratic case, this solution actually applies for all affine transformations. The patterns method enables a detailed analysis of the affine equivalence classes for various special classes of cubic rotation symmetric functions in n variables. Here the case of functions generated by a single monomial and having pk variables, where p>3 is prime, is examined in detail, and in particular, a formula for the number of classes is proved.
Given a Boolean function
f
:
F
2
n
→
{
0
,
1
}
, we say a triple (
x
,
y
,
x
+
y
) is a
triangle
in
f
if
f
(
x
)
=
f
(
y
)
=
f
(
x
+
y
)
=
1
. A
triangle-free
function contains no triangle. If
f
...differs from every triangle-free function on at least
ϵ
·
2
n
points, then
f
is said to be
ϵ
-far from triangle-free.
In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those
ϵ
-far from triangle-free. Let the
canonical tester
for triangle-freeness denotes the algorithm that repeatedly picks
x
and
y
uniformly and independently at random from
F
2
n
, queries
f
(
x
),
f
(
y
) and
f
(
x
+
y
), and checks whether
f
(
x
) =
f
(
y
) =
f
(
x
+
y
) = 1. Green showed that the canonical tester rejects functions
ϵ
-far from triangle-free with constant probability if its query complexity is a tower of 2’s whose height is polynomial in
1
/
ϵ
. Fox later improved the height of the tower in Green’s upper bound to
O
(
log
1
/
ϵ
)
. A trivial lower bound of
Ω
(
1
/
ϵ
)
on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough
ϵ
, there exists an integer
n
0
(
ϵ
)
such that for all
n
≥
n
0
there exists a function
f
:
F
2
n
→
{
0
,
1
}
depending on all
n
variables which is
ϵ
-far from being triangle-free and requires
Ω
(
1
ϵ
)
4.847
⋯
queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least
Ω
(
1
ϵ
)
2.423
⋯
queries.
We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of ...monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.
In this paper the problem of comparison of Boolean bases is considered. In our case the bases are compared on the complexity of Boolean functions representation by terms (formulas). The partial order ...is introduced on the set of all Boolean functions bases with respect to which a system of equivalence classes is obtained.It is known that the criterion for the equivalence for two bases is a reciprocal repetition-free expressiveness of functions of the one basis by the functions of the other, and the augmentation of a basis with a function weakly repetition-containing in it allows us not only to expand it, but makes this expansion minimal, making it possible to investigate the bases using the complexity of Boolean function representations with terms.Thus, the problem of describing the equivalence classes of bases can be reduced to finding weakly repetition-containing functions in specific bases. The basis $\{\vee, \cdot, -, 0,1 \}$ is the largest element in this partial order and its equivalence class forms the null level of the structure. The description of bases of the first level and, partially, of the second level has been obtained by several authors. This article describes the weakly repetition-containing Boolean functions in the same basis, in terms of uniformity, which completes the characterization of bases of the second level.
In this comment, an inequality of algebraic immunity of the sum of two Boolean functions is pointed out to be generally incorrect. Then we present some results on how to impose conditions such that ...the inequality is true. Finally, complete proofs of two existing results are given.
Hypertension, also called the “Silent Killer”, is a dangerous and widespread disease that seriously threatens the health of individuals and communities worldwide, often leading to fatal outcomes such ...as heart attack, stroke, and renal failure. It affects approximately one billion people worldwide with increasing incidence. In Turkey, over 15 million people have hypertension. In this study, a new Medical Expert System (MES) procedure with reduced rule base was developed to determine hypertension. The aim was to determine the disease by taking all symptoms of hypertension into account in the Medical Expert System (7 symptoms, 2
7
= 128 different conditions). In this new MES procedure, instead of checking all the symptoms, the reduced rule bases were used. In order to get the reduced rule bases, the method of two-level simplification of Boolean functions was used. Through the use of this method, instead of assessing 2
7
= 128 individual conditions by taking 7 symptoms of hypertension into account, reduced cases were evaluated. The average rate of success was 97.6 % with the new MES procedure.
PDF
