The boolean-functions tag has no wiki summary.
2
votes
1answer
67 views
Lower Bound for the Parity Learning Problem
What are known lower bounds for the time and query complexity of the problem of learning parities with an adaptive membership query oracle? To be clear the concept space $C$ is $\{x\in \{0,1\}^n \, \, ...
2
votes
1answer
93 views
Inferring simplest method to convert bit array 1 to bit array 2
Consider the set of all bit arrays of length n. Now consider the set of all 1-to-1 functions that map from this set to this set.
Now select a single function out of the latter set. Is there any ...
2
votes
1answer
88 views
Locally monotone Boolean function
I am unable to understand the definition of locally monotone Boolean function which is defined in Gotsman and Linial, "Spectral Properties of Threshold Functions", 1994, p. 40:
A function $f$ is ...
-2
votes
1answer
107 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
0answers
75 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 ...
1
vote
1answer
78 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 ...
3
votes
1answer
106 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
69 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 ...
4
votes
1answer
300 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 ...
2
votes
2answers
148 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 ...
14
votes
1answer
215 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 ...
2
votes
0answers
61 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
447 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
285 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
137 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 ...
16
votes
2answers
277 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 ?
3
votes
1answer
224 views
Length of a minimal DNF Boolean expression
Consider an disjunctive normal form boolean expression on $n$ variables. What is the upper bound on the number of terms in a minimal equivalent DNF expression? That is, given an arbitrary DNF ...
38
votes
2answers
2k views
Why does Fourier analysis of Boolean functions “work”?
Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including ...
7
votes
0answers
189 views
Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?
Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability.
...
0
votes
0answers
178 views
Boolean circuits and digraphs
It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the ...
10
votes
1answer
219 views
The entropy of a noisy distribution
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$ such that
$$\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},$$
and $f$ is a ...
12
votes
1answer
374 views
The entropy of a convolution over the hypercube
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
11
votes
1answer
204 views
Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?
There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma.
Can we develop a Switching Lemma result to prove a size lower-bound ...
17
votes
2answers
496 views
Linearly independent Fourier coefficients
A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ ...
2
votes
1answer
118 views
Agnostic Learning of K-Juntas over “small” distribution
I have two questions related to agnostic learning, one specific and one more general, specifically when the distribution relative to which the learner must operate is given explicitly as part of the ...
3
votes
2answers
310 views
Boolean Circuit in a Black Box?
Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here.
Let's equip a normal Turing machine with a "black box ...
4
votes
1answer
131 views
Computing every boolean function with a polynomial over $\mathbb{F}_3$?
The following paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over ...
7
votes
1answer
433 views
Checking formulas with two quantifiers ($\forall \exists$) - 2QBF
SAT solvers give a powerful way to check the validity of a boolean formula with one quantifier.
For instance, to check the validity of $\exists x . \varphi(x)$, we can use a SAT solver to determine ...
-7
votes
1answer
90 views
Reduce the given Logic Expression [closed]
Reduce the given logic expression into its simplest form:-
$A^{\prime}B^{\prime}C^{\prime}D + A^{\prime}BCD + AB^{\prime}C^{\prime}D +AB^{\prime}CD + ABC^{\prime}D^{\prime} + ABCD^{\prime} $
Here ...
4
votes
0answers
170 views
How to prove deg(f) = n iff the parity imbalance of f is non-zero?
Not sure if the notation I'm using here is standard or not. I'm going over class notes and I'm stumped over an exercise given: Show that $deg(f) = n \iff PI(f) \neq 0$.
Here $f$ is a boolean function ...
7
votes
1answer
225 views
Proper PAC learning of 2-DNF under uniform distribution
What is the state of art result about query complexity of proper PAC learning 2-DNF formulas with sample queries and under uniform distribution? Or any non-trivial bound on it?
Because I am not ...
18
votes
2answers
352 views
Uses of XORification
XORification is the technique to make a Boolean function or formula harder by replacing every variable $x$ by the XOR of $k\geq 2$ distinct variables $x_1 \oplus \ldots \oplus x_k$.
I am aware of ...
19
votes
5answers
597 views
Monotone arithmetic circuits
The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have ...
1
vote
0answers
277 views
Succinct representation of boolean functions
Let $f$ be a boolean function over $n$ variables $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}$. We are looking now for a representation of $f$ s.t. when given that representation and values $x_1, \ldots, ...
6
votes
1answer
116 views
Combining (block)-sensitivity and Lipschitz conditions?
If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a ...
4
votes
2answers
456 views
“long code test” and “dictatorship test”
Why is "long code test" also called "dictatorship test"?
I got really confused when I read about it in Arora's survey.
10
votes
0answers
222 views
Relation beween approximate degree of a function and its Fourier coefficient.
Consider a Boolean function $f:\{0,1\}^n\to\{0,1\}$.
The degree of the function $d$ has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than ...
12
votes
1answer
239 views
Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?
Is the following problem in PTIME, or coNP-hard:
Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ ...
3
votes
1answer
213 views
Bounds on the size of smallest decision tree for a boolean function?
Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?
It seems to me that assuming ...
10
votes
0answers
317 views
Expectation of Gowers norm
This was an assignment problem in a course on analytics combinatorics that I had taken this semester. Here is the problem:
Let $\mathbf{F}$ be the set of boolean functions, $f: \{0,1\}^n \rightarrow ...
27
votes
2answers
897 views
Cohomological approach to boolean complexity
A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this ...
9
votes
0answers
172 views
Lower bound method for ordered binary decision diagrams
This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?:
If you want to prove some exponential ...
5
votes
2answers
211 views
Boolean functions with exponential size OBDD representation in all orders except one order?
Are there boolean functions with exponential size OBDD representation in all orders except one order?
...exponential size in all orders except very few orders?
The exceptional orders should be ...
8
votes
1answer
432 views
Lower bounds on the Threshold function
In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
6
votes
1answer
405 views
Complexity of converting a boolean circuit to a boolean formula
Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime ...
0
votes
0answers
144 views
Determining dont care values in a Karnaugh Map [closed]
Ok I'm not sure if this question belongs here, but I am learning this in a CS class and the people at math.stack wouldn't know about this stuff, so here it goes. I'm having a hard time understanding ...
0
votes
1answer
191 views
Bent and hyper-bent functions
Is the AND logic function considered to be a bent function? If it is, how could one make a hyper-bent funtion using logic gates? Thank you (two questions in one: very efficient :) )
7
votes
2answers
205 views
Boolean function with specific ОBDD representation
I am looking for a class of boolean functions on $n$ variables with the following property:
When represented by read twice palindromic ordered bdd (i.e. the order is 1..n n..1) the size of the OBDD ...
0
votes
0answers
155 views
Problems or issues with a proposed circuit class?
I'm looking to use something close to the following as a definition for a circuit class. This is obviously semi-informal. I am curious if any one sees any potential problems with it, or where ...
6
votes
0answers
150 views
Distributions over circuits and N-to-N vs N-to-1 circuits
This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small ...
