All reports by Author Avishay Tal:

__
TR13-168
| 29th November 2013
__

Raghav Kulkarni, Avishay Tal#### On Fractional Block Sensitivity

Revisions: 1
,
Comments: 1

__
TR13-145
| 20th October 2013
__

Gil Cohen, Avishay Tal#### Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

__
TR13-058
| 5th April 2013
__

Ilan Komargodski, Ran Raz, Avishay Tal#### Improved Average-Case Lower Bounds for DeMorgan Formula Size

Revisions: 2

__
TR13-049
| 1st April 2013
__

Amir Shpilka, Ben Lee Volk, Avishay Tal#### On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

__
TR12-163
| 24th November 2012
__

Avishay Tal#### Properties and Applications of Boolean Function Composition

__
TR11-002
| 9th January 2011
__

Gil Cohen, Amir Shpilka, Avishay Tal#### On the Degree of Univariate Polynomials Over the Integers

__
TR10-178
| 17th November 2010
__

Amir Shpilka, Avishay Tal#### On the Minimal Fourier Degree of Symmetric Boolean Functions

Raghav Kulkarni, Avishay Tal

In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and

Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by $fbs(f)$, and showed

that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by $RC(f)$, which ...
more >>>

Gil Cohen, Avishay Tal

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. ... more >>>

Ilan Komargodski, Ran Raz, Avishay Tal

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the ``expected ... more >>>

Amir Shpilka, Ben Lee Volk, Avishay Tal

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.

1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.

2. ... more >>>

Avishay Tal

For Boolean functions $f:\{0,1\}^n \to \{0,1\}$ and $g:\{0,1\}^m \to \{0,1\}$, the function composition of $f$ and $g$ denoted by $f\circ g : \{0,1\}^{nm} \to \{0,1\}$ is the value of $f$ on $n$ inputs, each of them is the calculation of $g$ on a distinct set of $m$ Boolean variables. Motivated ... more >>>

Gil Cohen, Amir Shpilka, Avishay Tal

We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,m\}$?

Clearly, when $m=n$ the function $f(x)=x$ has degree $1$. We prove that when $m=n-1$ (i.e. the point $\{n\}$ is not in the range), it must be the case ... more >>>

Amir Shpilka, Avishay Tal

In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function.

Specifically, we prove that for every non-linear and symmetric $f:\{0,1\}^{k} \to \{0,1\}$ there exists a set $\emptyset\neq S\subset[k]$ such that $|S|=O(\Gamma(k)+\sqrt{k})$, and $\hat{f}(S) \neq 0$, where ...
more >>>