All Questions

Filter by
Sorted by
Tagged with
4
votes
1answer
212 views

Level $k$ bounds in Analysis of Boolean functions

In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears: If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer ...
3
votes
1answer
199 views

Dual to hypercontractive inequality

Recall the hypercontractive inequality: Let $\rho = \sqrt{\frac{p-1}{q-1}}$, then $||T_\rho(f)||_q \leq ||f||_p$ In https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf it is stated that the ...
4
votes
1answer
254 views

How tight is the XOR lemma?

The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
2
votes
0answers
143 views

Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
4
votes
1answer
217 views

Which (almost) balanced Boolean function has smallest "total" influence

The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$ $$ \max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
6
votes
1answer
127 views

Average-case analogue of Small-bias Spaces

Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias $$| \mathbb{E}_{x \in S} [ (-...
3
votes
0answers
217 views

Computing the Fourier expansion of the complete quadratic function

I am working through Ryan O' Donnell's book on the analysis of Boolean functions. One of the exercises (1.1) is to compute the Fourier series of the `complete quadratic function' on $\mathbf{F}_2^n$ $...
2
votes
0answers
53 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)?
14
votes
0answers
317 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\}$, ...
9
votes
1answer
300 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)$ ...
3
votes
0answers
173 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 \...
15
votes
1answer
527 views

Beigel-Tarui transformation of ACC cricuits

I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf One of the key lemmas is a ...
3
votes
0answers
66 views

Estimating the average contiguous sequence length of a balanced boolean function

Given a balanced Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, is there a sampling strategy that needs less than $O(2^n)$ samples to estimate the average length of contiguous sequences of 1's? ...
3
votes
0answers
179 views

Natural Proofs and methods for polylog depth circuit lower bounds

I have a question about the following question and its answer. Status on circuit lower bounds for polylog-bounded depth circuits In the above question, it is asked about methods to prove lower bounds ...
0
votes
0answers
92 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 ...
6
votes
2answers
822 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 ...
16
votes
2answers
787 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
1answer
870 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 ...
0
votes
0answers
298 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 "...
19
votes
2answers
1k 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$ ...
4
votes
0answers
188 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 ...
6
votes
1answer
152 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
689 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
445 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 $d$...
10
votes
0answers
442 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 \...
0
votes
1answer
201 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 :) )
23
votes
4answers
2k views

Social choice, arrow's theorem and open problems ?

Last few months I started to lecture myself on social choice, arrow's theorem and related results. After reading about the seminal results, I asked myself about what happens with partial order ...