Arrow Research search

Author name cluster

Steven Rudich

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.

14 papers
1 author row

Possible papers

14

FOCS Conference 2002 Conference Paper

Learning a Hidden Matching

  • Noga Alon
  • Richard Beigel
  • Simon Kasif
  • Steven Rudich
  • Benny Sudakov

We consider the problem of learning a matching (i. e. , a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0. 32(n/2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

Details

FOCS Conference 1994 Conference Paper

Products and Help Bits in Decision Trees

  • Noam Nisan
  • Steven Rudich
  • Michael E. Saks

We investigate two problems concerning the complexity of evaluating a function f at k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best decision tree algorithm of depth d is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth d algorithms are all correct is at most p/sup k/, which is the trivial lower bound. We show that if we replace the depth d restriction by "expected depth d", then this result fails. In the help-bit problem, we are permitted to ask k-1 arbitrary binary questions about the k-tuple of inputs. For each possible k-1-tuple of answers to these queries we will have a k-tuple of decision trees which are supposed to correctly compute all functions on k-tuples that are consistent with the particular answers. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg/sup s/(f) which is the minimum degree of a multivariate polynomial whose sign is equal to f. Finally, we give a brief discussion of these problems in the context of other complexity models. >

Details

FOCS Conference 1991 Conference Paper

Communication Complexity Towards Lower Bounds on Circuit Depth

  • Jeff Edmonds
  • Steven Rudich
  • Russell Impagliazzo
  • Jirí Sgall

M. Karchmer et al. (1991) considered the circuit depth complexity of n-bit Boolean function constructed by composing up to d=log n/log log n levels of k=log-n-bit Boolean functions. Any such function is in AC/sup 1/. They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires dk in Omega (log/sup 2/ n/log log n) depth. This would separate AC/sup 1/ from NC/sup 1/. They recommend using the communication game characterization of circuit depth. They suggest an intermediate problem which they call the universal composition relation. An almost optimal lower bound of dk-O(d/sup 2/(k log k)/sup 1/2/) is given for this problem. In addition, a proof, directly in terms of communication complexity, that there is a function on k bits requiring Omega (k) circuit depth is presented. >

Details

FOCS Conference 1985 Conference Paper

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

  • Benny Chor
  • Oded Goldreich 0001
  • Johan Håstad
  • Joel Friedman
  • Steven Rudich
  • Roman Smolensky

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f: {0, 1}n → {0, 1}m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in {0, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f: {0, 1}n → {0, 1}m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.

Details