All reports by Author Alex Samorodnitsky:

__
TR07-123
| 21st November 2007
__

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky#### Inverse Conjecture for the Gowers norm is false

Revisions: 2

__
TR07-033
| 14th February 2007
__

Michael Navon, Alex Samorodnitsky#### Linear programming bounds for codes via a covering argument

__
TR06-054
| 16th April 2006
__

Alex Samorodnitsky#### Low-degree tests at large distances

__
TR05-163
| 19th December 2005
__

Dvir Falik, Alex Samorodnitsky#### Edge-isoperimetric inequalities and influences

__
TR05-116
| 12th October 2005
__

Alex Samorodnitsky, Luca Trevisan#### Gowers Uniformity, Influence of Variables, and PCPs

__
TR05-084
| 31st July 2005
__

Mickey Brautbar, Alex Samorodnitsky#### Approximating the entropy of large alphabets

__
TR05-065
| 26th June 2005
__

Alexander Barvinok, Alex Samorodnitsky#### Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

__
TR01-063
| 5th August 2001
__

Michal Parnas, Dana Ron, Alex Samorodnitsky#### Proclaiming Dictators and Juntas or Testing Boolean Formulae

Revisions: 1

__
TR99-017
| 4th June 1999
__

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky#### Improved Testing Algorithms for Monotonicity.

Revisions: 1

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

Let $p$ be a fixed prime number, and $N$ be a large integer.

The 'Inverse Conjecture for the Gowers norm' states that if the "$d$-th Gowers norm" of a function $f:\F_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially ...
more >>>

Michael Navon, Alex Samorodnitsky

We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, ... more >>>

Alex Samorodnitsky

We define tests of boolean functions which

distinguish between linear (or quadratic) polynomials, and functions

which are very far, in an appropriate sense, from these

polynomials. The tests have optimal or nearly optimal trade-offs

between soundness and the number of queries.

In particular, we show that functions with small ... more >>>

Dvir Falik, Alex Samorodnitsky

We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least Omega(log(n)/n).The methods of the proof are then used to recover additional isoperimetric results for the cube, with ... more >>>

Alex Samorodnitsky, Luca Trevisan

Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f)

of a function f: G -> \C, where G is a finite abelian group and \C are the

complex numbers. Roughly speaking, if a function has small Gowers uniformity

of dimension d, then it ``looks random'' on ...
more >>>

Mickey Brautbar, Alex Samorodnitsky

We consider the problem of approximating the entropy of a discrete distribution P on a domain of size q, given access to n independent samples from the distribution. It is known that n > q is necessary, in general, for a good additive estimate of the entropy. A problem of ... more >>>

Alexander Barvinok, Alex Samorodnitsky

For a family X of k-subsets of the set 1...n, let |X| be the cardinality of X and let Gamma(X, mu) be the expected maximum weight of a subset from X when the weights of 1...n are chosen independently at random from a symmetric probability distribution mu on R. We ... more >>>

Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

We present improved algorithms for testing monotonicity of functions.

Namely, given the ability to query an unknown function $f$, where

$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a

monotone $f$, and rejects $f$ with high probability if it is $\e$-far

from being monotone (i.e., every ...
more >>>