Arrow Research search

Author name cluster

Alex Samorodnitsky

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
1 author row

Possible papers

13

STOC Conference 2021 Conference Paper

On codes decoding a constant fraction of errors on the BSC

  • Jan Hazla
  • Alex Samorodnitsky
  • Ori Sberlo

We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is successful on the BEC can also decode over a range of binary memoryless symmetric (BMS) channels. In particular, applying the result of Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke from STOC 2016, we prove that a Reed–Muller code of positive rate R decodes errors on the p with high probability if p < 1/2 − √2 − R (1−2 − R ).

Details

FOCS Conference 2014 Conference Paper

Bounds on the Permanent and Some Applications

  • Leonid Gurvits
  • Alex Samorodnitsky

We give new lower and upper bounds on the permanent of a doubly stochastic matrix. Combined with previous work, this improves on the deterministic approximation factor. We also give a combinatorial application of the lower bound, proving S. Friedland's "Asymptotic Lower Matching Conjecture"for the monomer-dimer problem.

Details

FOCS Conference 2009 Conference Paper

Learning and Smoothed Analysis

  • Adam Tauman Kalai
  • Alex Samorodnitsky
  • Shang-Hua Teng

We give a new model of learning motivated by smoothed analysis (Spielman and Teng, 2001). In this model, we analyze two new algorithms, for PAC-learning DNFs and agnostically learning decision trees, from random examples drawn from a constant-bounded product distributions. These two problems had previously been solved using membership queries (Jackson, 1995; Gopalan et al, 2005). Our analysis demonstrates that the "heavy" Fourier coefficients of a DNF suffice to recover the DNF. We also show that a structural property of the Fourier spectrum of any boolean function over "typical" product distributions. In a second model, we consider a simple new distribution over the boolean hypercube, one which is symmetric but is not the uniform distribution, from which we can learn O(log n)-depth decision trees in polynomial time.

Details

STOC Conference 2008 Conference Paper

Inverse conjecture for the gowers norm is false

  • 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 N p to F p is non-negligible, that is larger than a constant independent of N, then f has a non-trivial correlation with a degree d-1 polynomial. The conjecture is known to hold for d=2,3 and for any prime p. In this paper we show the conjecture to be false for p=2 and for d=4, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation with any polynomial of degree 3 is exponentially small. Essentially the same result, with different bounds for correlation, was independently obtained by Green and Tao. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime p, for d = p 2 .

Details

STOC Conference 2007 Conference Paper

Low-degree tests at large distances

  • 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. A central step in our analysis of quadraticity tests is the proof of aninverse theorem for the third Gowers uniformity norm of boolean functions. The last result implies that it ispossible to estimate efficiently the distance from the second-order Reed-Muller code on inputs lying far beyond its list-decoding radius. Our main technical tools are Fourier analysis on Z 2 n and methods from additive number theory. We observe that these methods can be used to give a tight analysis of the Abelian Homomorphism testing problemfor some families of groups, including powers of Z p .

Details

STOC Conference 2006 Conference Paper

Gowers uniformity, influence of variables, and PCPs

  • Alex Samorodnitsky
  • Luca Trevisan 0001

We return to the study of the relation of query complexity and soundness in probabilistically checkable proofs.We present a PCP verifier for languages that are Unique-Games-Hard and such that the verifier makes q queries, has almost perfect completeness, and has soundness error at most 2q/2 q+ε , for arbitrarily small ε>0. For values of q of the form 2 t-1 , the soundness error is (q+1)/2 q+ε .Charikar et al. show that there is a constant c such that for every language that has a verifier of query complexity q, and a ratio of soundness error to completeness smaller than cq/2 q is decidable in polynomial time. Up to the value of the multiplicative constant and to the validity of the Unique Games Conjecture, our result is therefore tight.As a corollary, we show that approximating the Maximum Independent Set problem in graphs of degree Δ within a factor better than Δ/(log Δ) c is Unique-Games-Hard for a certain constant c>0.Our main technical results are (i) a connection between the Gowers uniformity of a Boolean function and the influence of its variables and (ii) the proof that "Gowers uniform" functions pass the "hypergraph linearity test" approximately with the same probability of a random function. The connection between Gowers uniformity and influence might have other applications.

Details

FOCS Conference 2005 Conference Paper

On Delsarte's Linear Programming Bounds for Binary Codes

  • Michael Navon
  • Alex Samorodnitsky

We prove two results about the value of Delsarte 's linear program for binary codes. Our main result is a new lower bound on the value of the program, which, in particular, is nearly tight for low rate codes. We also give an easy proof of a (known) upper bound, which coincides with the best known bound for a wide range of parameters.

Details

STOC Conference 2002 Conference Paper

Monotonicity testing over general poset domains

  • Eldar Fischer
  • Eric Lehman
  • Ilan Newman
  • Sofya Raskhodnikova
  • Ronitt Rubinfeld
  • Alex Samorodnitsky

The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are 'far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n -dimensional hypercube {1,…, m } n . These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2 -CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest.

Details

FOCS Conference 2002 Conference Paper

Testing Juntas

  • Eldar Fischer
  • Guy Kindler
  • Dana Ron
  • Muli Safra
  • Alex Samorodnitsky

We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter /spl epsi/. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in /spl epsi//sup -1/. The first test is stronger in that it has a 1-sided error, while the second test has a more compact analysis. We also present an adaptive version and a 2-sided error version of the first test, that have a somewhat better query complexity than the other algorithms. We then provide a lower bound of /spl Omega//spl tilde/(/spl radic/ k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of /spl Omega/(log(k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group Z/sub 2//sup q/ that may be interesting in its own right. We show that for some t(q) = O/spl tilde/(q/sup 2/), the distributions of the random walk at times t and t + 2 are close to each other, independently of the step distribution of the walk. We also discuss related questions. In particular, when given in advance a known k junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in k and /spl epsi/.

Details
v2026.09.13