64
Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions $f: \{0,1\}^n\to\mathbb{R}$, and consider a linear operator of the form $\sigma_w$ (for $w\in\{0,1\}^n$), that maps a function $f(x)$ as above to the function $f(x+w)$. In many of the questions ...
22
If I may, quite blatantly, advertise myself, we wrote an article about this last year
Abstraction-Based Algorithm for 2QBF. I've got an implementation for qdimacs, which I can provide if you wish but from my experience, one can benefit greatly from specializing the algorithm for a particular problem. There is also an older paper A Comparative Study of 2QBF ...
19
No. Consider the following function on $\{0,1\}^n$:
$$ f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}). $$
Clearly this function is hard for AC0. On the other hand, the function is almost constant, so almost all of its Fourier spectrum is on the first level.
If you want a balanced counterexample, consider
$$...
17
The answer is “yes”. The proof is by contradiction.
For notational convenience, let us denote the first $n/2$ variables by $x$ and the second $n/2$ variables by $y$. Suppose that $f(x,y)$ is $\delta$-close to a function $f_1(x,y)$ which depends only on $k$ coordinates of $x$. Denote its influential coordinates by $T_1$. Similarly, suppose that $f(x,y)$ is $\...
17
Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014.
(http://dx.doi.org/10.1007/978-3-662-44602-7_9)
You may be attacking this problem. If so, I feel sorry, but I started to attack the problem independently before the ...
17
From the paper: what is actually proven is, in Theorem 1.4,
$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad s(f) \geq \sqrt{\deg f} \tag{1}
$$
which cannot be improved (it is tight for some functions). Then it is combined with the previously known result of Nisan and Szegedy [1],
$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad \deg f \geq \sqrt{\frac{1}{2}\...
15
I'll answer the second part of the question.
I. Eigenvalues and Eigenfunctions
Let's first consider the one dimensional case $n=1$. It is easy to check that the operator $R_{p_1,p_2}$ has two eigenfunctions: $1$ and
$$\xi(x) = (p_1+p_2)x - p_1 =
\begin{cases}
-p_1, &\text{ if } x =0,\\
p_2, &\text{ if } x =1.
\end{cases}$$
with eigenvalues $1$ and ...
14
for Question 1, the answer is Yes, and can be shown as follows. (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at once.)
Fix any NP-complete language $L$, and a family of good binary error-correcting codes (with rate 1/4 and correcting from a .1 fraction of errors, say). ...
14
To me, your question seems analogous to saying "I've heard that non-Euclidean geometry requires me to give up Euclid's fifth axiom, which is very useful in many mathematical contexts." You don't have to give up the axiom in the sense of "personally agree, at a basic philosophical level, that it doesn't hold", you just have to think of it in terms like: "As a ...
14
In his CCC'17 paper [1], Avishay Tal improved the bound to $$
\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}
$$
You may want to check p.15:4 for a discussion. It also refers to (see Footnote 30 to a paper of Harsha and Srinivasan, which improves on (1)) and answers Tal's conjecture: $k$-wise independent, for
$$
k = \left(\log m \right)^{O(d)}\cdot\...
13
Here is what Scott Aaronson has to say on the subject:
What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity measures: the decision-tree complexity of $f$, the certificate complexity of $f$, the randomized query complexity of $f$, the quantum query complexity of $f$, the ...
13
You seem to be confusing several things here.
First of all, like Alexis said in her answer, I don't see why you would need to accept/reject the principles of a given logical theory in order to study it and learn about it. The fact that your theory is intuitionistic doesn't mean that your meta-theory has to be! You may freely use proof by contradiction or ...
12
The smallest $c$ that the bound holds for is $c = \frac{1}{\sqrt 2 - 1} \approx 2.41$.
Lemmas 1 and 2 show that the bound holds for this $c$.
Lemma 3 shows that this bound is tight.
(In comparison, Juri's elegant probabilistic argument gives $c=4$.)
Let $c=\frac{1}{\sqrt 2 - 1}$.
Lemma 1 gives the upper bound for $k=0$.
Lemma 1:
If $f$ is $\epsilon_g$-...
12
Isn't the following a counter-example?
Let $f(x)$ be the majority of $x_1, \ldots, x_{1/\epsilon^2}$, which is an indicator of a set of size $2^n/2$, so $d = 1$. However, $\hat{f}(\{i\}) = \Theta(\epsilon)$ for $1 \le i \le 1/\epsilon^2$, so you have $1/\epsilon^2$ linearly independent large Fourier coefficients.
11
LMN theorem shows that if f is a boolean function$(f:\{-1,1\}^n \rightarrow \{-1,1\})$ computable by an $\text{AC}^0$ circuit of size M,
$$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{d-1})}$$
$\Rightarrow \hat f([n])^{2} \leq 2^{-\Omega(n/(\log M)^{d-1})}$
$\Rightarrow |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}$
$|\hat f([n])|$ is ...
11
It is actually possible to make use of random restrictions to prove lower bounds for threshold circuits.
In particular in the paper Size-Depth Tradeoffs for Threshold Circuits, Impagliazzo, Paturi, and Saks use random restrictions to prove a superliner lower bound (on the number of wires) for constant depth threshold circuits computing the parity function.
...
answered Jul 27 '12 at 17:56
Kristoffer Arnsfelt Hansen
3,9052 gold badges22 silver badges34 bronze badges
11
Here's an algorithm that beats the trivial attempts.
The following is a known fact (Exercise 1.12 in O'Donnell's book) : If $f:\{-1,1\}^n\to\{-1,1\}$ is a Boolean function which has degree $\le d$ as a polynomial, then every Fourier coefficient of $f$, $\hat{f}(S)$ is an integer multiple of $2^{-d}$.
Using Cauchy-Schwarz and Parseval one gets that there are ...
11
The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound was established by Lupanov, and his method is known as the Lupanov representation of boolean functions. It also gives an upper bound of $(1+o(1))2^n/\log n$ ...
11
Type theory is a mathematical theory in which we can do very many different things (set theory is like that as well). We can use type theory for computability, or homotopy theory, or use it to express features of a programming language, etc. One of the things that we can use type theory for is as a kind of logic (this is known as Curry-Howard correspondence)....
11
In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system model (Section 3.1). Then, they further illustrate how to map their spin system model to the problem of uniformly sampling from the order ideals of a poset which, ...
11
Note that formulas using $\land$ and $\lor$ gates (and possibly the constants $0$ and $1$) are known as monotone.
The complexity of monotone formula equivalence depends on how complex formulas are allowed. Let me start with the related problem of implication (entailment) between two formulas $\phi\vdash\psi$, which is easier to classify. Note that $\phi$ ...
10
Sorry I'm late -- it's a wonderful question! As others have already pointed out, that's exactly why I asked the question in my BQP vs. PH paper, and why I spent 4 or 5 months working on it without success back in 2008. One way to answer the question would have been to prove a much more general statement that I called the "Generalized Linial-Nisan ...
10
Sure. If $C_1\ni x_i$ and $C_2\ni\neg x_i$ are in $F\restriction I$ (in particular, $x_i$ is unset by $I$), pick clauses $D_1,D_2$ in $F$ which restrict to $C_1$ and $C_2$, respectively. Then $x_i\in D_1$ and $\neg x_i\in D_2$, hence their resolvent $(D_1\let\bez\smallsetminus\bez\{x_i\})\cup(D_2\bez\{\neg x_i\})$ is subsumed by some $D\in F$. If $D$ ...
10
Isn't the probability of $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$ at least 1/2 ? It seems that $1/(10k)$ is a weak lower bound.
In fact the answer is no. (It would be that $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$ holds with probability at least $1/2-\varepsilon$, if we were working with an $\varepsilon$-biased hash family, and indeed using $\...
10
It is important to remark that a specific boolean circuit only treats inputs of a given size, unlike a Turing Machine that can take inputs of any size.
So a language with inputs of arbitrary size is usually treated by a family of circuits, one for each size of input.
The problem with this definition is that it allows circuit to solve uncomputable problems, ...
10
Any function which has non-zero correlation with parity has degree $n$. That is, if $$\sum_{x \in \{0,1\}^n} (-1)^{\sum_i x_i}f(x) \neq 0$$
then the unique multilinear expansion of $f$ contains the monomial $x_1\cdots x_n$. Indeed, since $(-1)^{x_i} = \frac{1-x_i}{2}$, the Fourier expansion of $f$ (expressed in terms of products of $\frac{1-x_i}{2}$) will ...
9
Perhaps you want what's sometimes called "Chang's Lemma" or "Talagrand's Lemma"... called the "Level-1 Inequality" here:
http://analysisofbooleanfunctions.org/?p=885
It implies that if $1_S$ has mean $2^{-d}$ then the number of linearly independent Fourier coefficients whose square is at least $\gamma 2^{-d}$ is at most $O(d/\gamma^2)$. (This is because an ...
9
There is no such $C$. Define $g\colon\mathbb{Z}_2^n\to\mathbb{R}$ by
$$g(x_1,\dots,x_n)=\begin{cases}
2^{2n/3}&\text{ if $x_1=\dots=x_n=0$}\\
1&\text{ otherwise.}\end{cases}$$
Then $g*g$ satisfies
$$(g*g)(x_1,\dots,x_n)=\begin{cases}
2^{4n/3}+2^n-1&\text{ if $x_1=\dots=x_n=0$}\\
2^{2n/3}\cdot 2+2^n-2&\text{ otherwise.}\end{cases}$$
Let $f=g/...
9
Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits.
If you can sort the bits then it is easy to compare the result to $k$ and
compute restricted threshold.
On the other hand, assume that we have an circuits to compute restricted threshold.
We can do a parallel search to find the number of ones in the input and
...
9
Kaveh's answer provides an answer do the question as you have stated it (and this is the usual proof for showing that $\mathsf{TC}^0$ is contained in $\mathsf{NC}^1$). But I was thinking that you might actually have intended to ask a slightly a different question. Namely for an explicit polynomial size monotone formula for majority.
Since majority is ...
answered Mar 6 '14 at 11:53
Kristoffer Arnsfelt Hansen
3,9052 gold badges22 silver badges34 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible
