The boolean-functions tag has no wiki summary.
-2
votes
1answer
98 views
computing with gates on polar coordinates, functionally complete wrt boolean functions?
this question is inspired by a particular somewhat "natural" physical system specifically constructed to mimic another complex highly-studied physical computing system. (some may astutely guess at ...
1
vote
1answer
77 views
Expressing a set of 0-1 strings by Extended Formulation
Extended Formulation of a polytope $P \subseteq \mathbb{R}$ is a system of linear constraints which satisfies the following condition:
$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax ...
2
votes
1answer
118 views
Size of decision tree for f is polynomial in the DNF size of f and CNF size of f
I've been having hard time with proving the following claim:
Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the ...
1
vote
0answers
73 views
Extended Formulaiton and Integer Programming
An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints
$Ex + Fy = g, y\geq 0$
in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real
matrices ...
4
votes
1answer
295 views
Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?
Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function.
The Fourier expansion of $f$ is
$$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$
where $\widehat{f}(S)$ are real numbers ...
3
votes
1answer
104 views
About Closure under Resolution
The question looks very simple, that is why I posted it first on MathSE, unsuccesfully - no answer for 12 days. I tried to find a short and elegant answer to the question, but I haven't succeed yet. ...
0
votes
0answers
68 views
Bound for the spectral norm of a boolean function [duplicate]
As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$.
Is it possible to improve this bound..?
Can somebody provide me an example of a Boolean ...
25
votes
2answers
700 views
What is the complexity of distinguishing a true Fourier spectra from a fake one?
A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.
The Fourier spectra of a function $f$ is defined as ...
16
votes
2answers
276 views
Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?
Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
14
votes
1answer
209 views
An extension of the noise operator
In a problem I am currently working on, an extension of the noise operator arises naturally, and I was curious whether there has been prior work. First let me revise the basic noise operator ...
-5
votes
1answer
162 views
Fourier analysis of Boolean functions [closed]
Suppose f is any boolean function from {-1,1}^n to {-1.1}. Then How will prove that f has atmost one fourier coefficient with magnitude exceeding 1/2.
2
votes
0answers
60 views
Exhibiting an adversary to prove a boolean function is evasive
I'm trying to collect examples of exhibiting an adversary to prove that a Boolean function is evasive. I know of several examples of graph properties for which adversary methods have been used, i.e. ...
16
votes
2answers
443 views
Robustness of splitting a junta
We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables.
Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by ...
4
votes
2answers
282 views
Factoring Cartesian bitwise join of bit vectors
(This question has been substantially revised in an attempt to word it clearly.)
I am wondering if anyone has seen this problem. Let $[n] = \{1,\ldots,n\}$ for an integer $n$. Consider two finite ...
4
votes
0answers
136 views
Sparse Boolean Function and Other Boolean Functions
Let $s$ be a Sparse boolean function $s:\{0,1\}^{n}\rightarrow \{0,1\}$ such that $|s^{-1}(1)| \leq 2^{n\delta}, 0 < \delta <1$
The majority function $MAJ_{n}$ takes value 1 if and only if the ...
