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

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

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