66

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 ...


28

Here are a few other examples. Diaconis and Shahshahani (1981) studied how many random transpositions are required in order to generate a near uniform permutation. They proved a sharp threshold of 1/2 n log(n) +/- O(n). Generating a Random Permutation with Random Transpositions. Kassabov (2005) proved that one can build a bounded degree expander on the ...


19

The question seems somewhat under-specified in the sense that it did not specify the desired error probability of the procedure. Assuming one means constant error probability, then the above is indeed the best I know. For a detailed discussion see Sec 2.5.2.4 in my book "The Foundations of Cryptography - Volume 1" available at http://www.wisdom.weizmann.ac....


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 $\...


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

Here is one example that I know: ``On the 'Log-Rank' Conjecture in Communication Complexity'', R.Raz, B.Spieker, Proceeding of the 34th FOCS, 1993, pp. 168-177 Combinatorica 15(4) (1995) pp. 567-588 I believe that there much more.


14

A very good question. I don't know the full answer and would like to know it myself. However, you may find the following interesting. If, instead of the group $S_n$, we consider its 0-Hecke monoid $H_0(S_n)$, it has a representation on a certain class of integer matrices which acts by tropical $(\min,+)$-multiplication. This has a lot of interesting ...


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\...


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

Here's an example from quantum computing: Roland, Jeremie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), "Symmetry-Assisted Adversaries for Quantum State Generation", Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC '11, IEEE Computer Society, pp. 167–177, doi:10.1109/CCC.2011.24 They show that the quantum ...


11

Knuth 3rd volume of The Art of Computer Programming is devoted to searching and sorting and devote much to combinatorics and permutations and to the Robinson-Schensted-Knuth correspondence, which is central in representation theory of the symmetric group. There are several papers by Ellis-Friedgut-Pilpel, and Ellis-Friedgut-Filmus which solve extremal ...


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 ...


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 ...


9

This paper came up on the arXiv today and it improves on the upper bound on $bs(f)$ in terms of $s(f)$. They prove the following bound: $$ bs(f) \leq 2^{s(f)-1}s(f). $$ This along with the connection that Marcos mentioned in his comment should give better bounds than previously known.


8

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$. In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case. Unfortunately, as you will see,...


7

The Symmetric Group Defies Strong Fourier Sampling by Moore, Russell, Schulman "we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling... These results apply to the special case relevant to the Graph Isomorphism problem." with a connection to solving the Graph Isomorphism problem via QM ...


7

There are several ways to understand the question according to the precise meaning of "small size" and "concentrate." 1) If you consider Boolean functions so that $1-o(1)$ of their l-2 norm is concentrated on small sized $S$ then the answer is no - the majority function is an example such that $1-o(1)$ of the l-2 norm is on bounded sets and is not in ${\rm ...


7

I don't think parities are the only orthonormal Boolean basis, for example Paley basis provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean functions, have any interesting applications.


6

Yes. Let $f : \{-1,1\}^n \to \mathbb{R}$, and let $F : [-1,1]^n \to \mathbb{R}$ be its multilinear extension. If $f$ is monotone, then so is $F$. proof: Fix a variable index $i$; we'll show that $\frac{\partial F}{\partial x_i} \ge 0$ at all $x \in [-1,1]^n$. If this holds for all $i$, we're done. Since $F$ is multilinear, we can write this partial ...


6

More statistics than computer science, but still interesting: In chapter 8 in Diaconis' monograph on Group Gepresentations in Probability and Statistics, spectral analysis techniques for data associated with a group $G$ are developed. This extends more classical spectral analysis of say time series data where the natural $G$ is the reals or the integers ...


6

Here might be another take on this question. Assuming the pseudo Boolean function is k-bounded, the Walsh polynomial representation of the function can be decomposed into k subfunctions. All of the linear terms are collected into one subfunction, the all of the pairwise interactions into one subfunction, then the 3-way interactions, etc. Each one of ...


6

The representation theory of the symmetric group plays a key role in the Geometric Complexity Theory approach to lower bounds on the determinant or on matrix multiplication. Bürgisser and Ikenmeyer prove a lower bound on the border-rank of matrix multiplication using the representation theory of $S_n$. For how the representation theory of $S_n$ relates to ...


5

Huangs Phd thesis, PROBABILISTIC REASONING AND LEARNING ON PERMUTATIONS : exploiting structural decompositions of the symmetric group. the application is "a real camera-based multi-person tracking scenario." Fourier Theoretic Probabilistic Inference over Permutations by Huang, Guestrin, Guibas; Journal of Machine Learning Research 10 (2009) 997-1070. see eg ...


5

A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same. The number of basis states before the Fourier transform is 120, the number of group elements. The number of basis states after the Fourier transform is 120, in this case broken up according to the identity $$ 120=1^2+1^2+4^2+4^2+5^2+...


5

Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups. On the positive side. Theorem: For cyclic groups with order $p^kq$, where $p$ and $q$ are primes and $k\in \mathbb{N}$, the incidence matrix of elements and subgroups is totally ...


5

This is Corollary 3.22 of Analysis of Boolean Functions, by Ryan O'Donnell (2014). You may want to consult the proof in the book, or look directly at the online version (which has a different numbering: this corresponds to Corollary 22 there). Note that you can obtain a version of the book following this link.


5

From D.W.'s comment, we see that your problem is equivalent to the same problem with $s=0$ (and with $d$ only increased by 1). The resulting problem is precisely the Linear Code Equivalence Problem over $\mathbb{F}_2$, just phrased slightly differently. (Usually CodeEq is phrased as "you have two $d \times n$ generator matrices of linear codes, is there a ...


5

Here's one way of attacking the problem. Any boolean function $f: [2]^n \rightarrow [2]$ can be written as \begin{equation} f(\alpha) = \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha) \end{equation} where $\chi_{\beta} \in [2]$ and $\delta_{\beta}$ is defined as \begin{equation} \delta_{\beta} (\alpha) = \begin{cases} 1 & \text{if } \alpha = \...


4

Discarding in this context can be carried out by performing a Partial Trace. The system you're interested in is that of the first register. If you want to know only its state, as opposed to the combined state of the two registers, then you take the density matrix of the whole system and trace out the second register. The resultant state will, in this case, ...


Only top voted, non community-wiki answers of a minimum length are eligible