Questions about Boolean functions and their analysis

learn more… | top users | synonyms

2
votes
1answer
68 views

Complexity of generating a pseudo-Boolean function

A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to $\mathbb{R}$. Following is a pseudo-Boolean function. $$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - ...
4
votes
1answer
111 views

Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$. As we know that every ...
3
votes
1answer
62 views

Symbolic Execution of the Quine-McCluskey Algorithim

If I understand correctly, the Quine–McCluskey algorithm will find the minimum boolean formula size for given boolean function. Has there been any attempts to (for lack of a better term) symbolically ...
2
votes
0answers
145 views

Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?

It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$. Input: a list $P$ of triplets $(a,s,t)$ where $s$ and $t$ are nonnegative integers. Output: is there an $x\in \mathbb{R}$ such ...
2
votes
0answers
32 views

moments of complexity for random restriction

Suppose C is a large circuit computing a function $f:2^n \rightarrow 2^m$. For a function $g$ let $B(g)$ denote the size of the minimal Boolean circuit computing $g$. What can be said about the ...
1
vote
1answer
115 views

Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?

Let $\underline{x}\triangleq x_1,\dots,x_n$. Given a Boolean function $f:\{0,1\}^n\to\{0,1\}$, we say that $p(\underline{x})\in\Bbb{R}[\underline{x}]$ is an $\epsilon$-approximation to $f$ if for ...
1
vote
2answers
197 views

Does approximation degree of AND depend on error?

Denote $\underline{x}\triangleq x_1,\dots,x_n$. Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $p_\epsilon(\underline{x})\in\Bbb R[\underline{x}]$ be minimum multilinear multivariate ...
2
votes
1answer
54 views

One sided approximation degree

Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $P_{i,\epsilon}$ be minimum multivariate polynomial such that $P_{i,\epsilon}=i\iff f=i$, $P_{i,\epsilon}\in(i-\epsilon,i+\epsilon)\iff ...
12
votes
0answers
95 views

Which monotone Boolean functions are representable as thresholds on sums?

I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want ...
2
votes
0answers
100 views

Complexity: simulated annealing vs. quantum annealing

How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms? In Convergence theorems for quantum annealing by Morita and Nishimori, it has been ...
2
votes
2answers
66 views

Learning k-parities with Membership Queries and Persistent Noise

Random independent misclassification error is an inappropriate noise model for a membership query (MQ) oracle because for any noise rate $\eta<1/2$ one can eliminate noise to an arbitrary extent by ...
2
votes
1answer
134 views

Real representation versus communication complexity

Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for ...
5
votes
0answers
182 views

Less known graphical representations of Boolean functions

A Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ admits a canonical graphical representation in terms of a reduced ordered binary decision diagram (ROBDDs or BDDs for short). There are other ...
10
votes
0answers
229 views

Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2

Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and ...
5
votes
2answers
297 views

Complexity class of sensitivity

Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function. Let $[n]=\{1,2,\dots,n\}$. If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position. If $B\subseteq ...
0
votes
1answer
260 views

Randomized Algorithm with random input

As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm ...
8
votes
2answers
193 views

Sensitivity-Block sensitivity conjecture - Implications

Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$. The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c>0$ such that $\forall ...
2
votes
1answer
214 views

Important papers and open problems in Boolean functions

I am interested in Boolean function polynomial/rational exact/approximate/one sided approximate representation, relation to circuit/communication complexity, tools utilized to study Boolean functions ...
4
votes
1answer
92 views

On Boolean functions with a certain number of zeros

Given boolean $f(\Bbb x)$, with $\Bbb x\in\{0,1\}^n$, what are good upper/lower bounds, in terms of $|f^{-1}(0)|$, for minimum $deg(p(\Bbb x))$ of a real polynomial satisfying $p(\Bbb x)=f(\Bbb x)$?
7
votes
1answer
234 views

Conversion between k-SAT and XOR-SAT

According to XOR Satisfiability Solver Module for DPLL Integration by Tero Laitinen, we need $2^{n-1}$ CNF clauses to convert an $n$ literal XOR-SAT clause if we do not want to increase the number of ...
6
votes
0answers
114 views

Bias of a random boolean low degree polynomial

What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree? More specifically, is it true that if we take a uniformly ...
2
votes
0answers
43 views

Minimizing a general submodular pseudo boolean function

Are there algorithms that minimize a general submodular pseudo boolean function (PBF) without first transforming it to a quadratic pseudo boolean function (QPBF)?
3
votes
1answer
121 views

Gap in degree of representations of candidate boolean functions

Let $x_1,x_2,\dots x_n$ be literals. Let $P(x_1,x_2,\dots,x_n)$ be one of the following Boolean function: $0)$ Equality function - $Eq_k^n(x)=1\iff x_1+\dots+x_n= k$ $1)$ Threshold function - ...
1
vote
1answer
85 views

Rational function for Parity function

Let $x_1,x_2,\dots x_n$ be literals. Let $P(x_1,x_2,\dots,x_n)$ be the parity function. What is the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents ...
5
votes
1answer
163 views

Representing boolean function by a polynomial

Supposing we have a boolean function from $f:\{0,1\}^n\rightarrow\{0,1\}$. It is clear that a real multivariate polynomial $p(x)$ such that $f(x)=p(x)$ on $x\in\{0,1\}^n$ can be multilinear. What are ...
11
votes
0answers
201 views

Sign patterns for Fourier coefficients of Boolean functions

Given a sequence of real numbers $(a_i)$, the sign-pattern sequence $(s_i)$ is defined by $s_i = +$ if $a_i \geq 0$ and $s_i = -$ otherwise. For a boolean function $f: \{0,1\}^n \to \{0,1\}$, ...
5
votes
1answer
198 views

May Boolean circuits be exponentially more concise than Boolean formulae?

Consider a family $(f_n)_{1 \leq n}$ of Boolean functions, where $f_n$ is a function on $n$ variables. Consider for every $n$ the smallest Boolean formula $F_n$ describing $f_n$, and the smallest ...
3
votes
0answers
81 views

What is the current state of research on the representation of boolean functions using wavelets

The harmonic representation of boolean functions such as XOR or AND has been studied in different course note lectures that can be found on Google. http://cs.mcgill.ca/~hatami/comp760-2011/ ...
13
votes
0answers
318 views

How can one find the “hard” probability distribution on the input for recursive boolean functions?

Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
4
votes
1answer
271 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the ...
3
votes
1answer
97 views

Satisfiability for various branching programs

Clearly, SAT for CNF, formula, or many classes of boolean circuits have strong significance on the entire theory community. Branching program, or BDD is one of the most basic and popular ...
9
votes
1answer
192 views

Random restrictions and the connection to total influence of Boolean functions

Say we have a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$ and we apply $\delta$-random restriction on $f$. In addition, say that the decision tree $T$ that computes $f$ shrinks to size $O(1)$ ...
11
votes
1answer
204 views

Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a problem with a similar flavor to learning juntas: Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$. ...
3
votes
0answers
78 views

Social choice theory, preference aggregation data sets

I do computational research on preference aggregation. I am quite interested in Kemeny Optimal Aggregation. However I do not find much useful data for preference aggregation in context of social ...
5
votes
2answers
88 views

L1 - embeddability of metrics supported on the Hypercube

I am quite new to the area of metric embeddings so this question might turn out to be extremely easy. Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge ...
4
votes
0answers
111 views

A possible application of TCS to EE: disruption-resistant circuits

Consider the following problem. We're given a circuit $C$ with $n$ binary inputs and $n$ binary outputs, computing some boolean function $f_C : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$. We assume ...
14
votes
2answers
215 views

On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside ...
5
votes
0answers
134 views

Fourier Analysis on checking whether there exists a vector in hypercube orthogonal to a set of vectors?

I know virtually noting about Fourier Analysis and I'd like to know whether it's worth to learn this topic for my problem. My problem is: Given vectors $h_1,\cdots,h_k\in\{+1,-1\}^n$ where $k < ...
10
votes
3answers
689 views

Circuit complexity of Majority function

Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I ...
3
votes
0answers
112 views

Deciding whether a binary multiplicity automaton has empty language

Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ...
0
votes
1answer
104 views

How to go about finding the most “complex” function?

Intro Hi, I'm a hobbyist, with no formal education, tinkering with SAT solving and boolean algebra minimization. So expect bad terminology. I hope you will forgive me I'm asking a wrong question in a ...
3
votes
0answers
118 views

An identity about the Majority function?

Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and $\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x ...
0
votes
0answers
106 views

Determining if a function is constant or not using period finding

Consider an arbitrary boolean function $$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$ which we write as: $$f(x_1, x_2 ... x_n) $$ where each $x_i$ is a boolean variable We note ...
2
votes
0answers
43 views

Is there a relation between $l_p$-norms of functions with same Fourier spectra but w.r.t different measures on the Hamming cube?

Informally, I want to ask if two functions $f$ and $g$ on the Hamming cube have the same Fourier spectra but w.r.t different measure and basis, then is $||f||_p$ related to $||g||_p$? (Where each ...
10
votes
1answer
238 views

Boolean Functions Where Sensitivity Equals Block Sensitivity

Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ ...
5
votes
1answer
183 views

any connection between binary/integer multiplication and matrix multiplication?

is there a connection between the inherent complexity of binary/integer multiplication algorithms and matrix multiplication algorithms? if so what is a ref that outlines/discusses it? some ...
5
votes
1answer
193 views

Lower bounds for formulae sizes for addition

I am interested in the conversion of $\sum_{i=1}^n x_i = y$ to 3-CNF. Here $x_i$ is a binary 0/1 variable and $y$ is some positive integer. There are a number of practical methods for doing this, ...
2
votes
2answers
327 views

Are Boolean circuits 'universal'

I have a question, but I don't seem to know enough computer science terminology in order to look up an answer. So I wonder if you guys could help a poor physicist like me. I would like to know if ...
6
votes
0answers
136 views

An alternative proof of hypercontractivity of the Becker-Bonami operator

The Becker-Bonami operator $T_p$ on a function $f(x) : \{0,1\}^d \to \mathbb{R}$ is defined as follows. Let $\nu(x)$ be a perturbation of $x$ so that every bit remains the same with probability $p$ or ...
6
votes
0answers
89 views

Problems that reduce to or are abstracted by the learning juntas problem

What problems are either abstracted by or reduce to the learning juntas problem? (An example of a real-world problem abstracted by the learning juntas problem is the Identification of genetic loci ...