Arrow Research search

Author name cluster

Richard Beigel

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.

23 papers
2 author rows

Possible papers

23

MFCS Conference 2006 Conference Paper

The Multiparty Communication Complexity of Exact- T: Improved Bounds and New Problems

  • Richard Beigel
  • William I. Gasarch
  • James Glenn

Abstract Let x i, .. ., x k be n -bit numbers and T ∈ ℕ. Assume that P 1, .. ., P k are players such that P i knows all of the numbers exceptx i. They want to determine if \(\sum^{k}_{j=1}{\it x}_{j}\) = T by broadcasting as few bits as possible. In [7] an upper bound of \(O(\sqrt n )\) bits was obtained for the k =3 case, and a lower bound of ω (1) for k ≥3 when T =Θ(2 n ). We obtain (1) for k ≥3 an upper bound of \(k+O((n+\log k)^{1/(\lfloor{\rm lg(2k-2)}\rfloor)})\), (2) for k =3, T =Θ(2 n ), a lower bound of Ω(loglog n ), (3) a generalization of the protocol to abelian groups, (4) lower bounds on the multiparty communication complexity of some regular languages, and (5) empirical results for k = 3.

Details

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

MFCS Conference 1996 Conference Paper

On the Query Complexity of Sets

  • Richard Beigel
  • William I. Gasarch
  • Martin Kummer
  • Timothy H. McNicholl
  • Frank Stephan 0001

Abstract There has been much research over the last eleven years that considers the number of queries needed to compute a function as a measure of its complexity. We are interested in the complexity of certain sets in this context. We study the sets ODD A n ={(x 1, .. ., x n )∶¦ A ∩ { x 1, .. ., x n }¦ is odd} and WMOD( m ) A n ={( x 1, .. ., x n )∶¦ A ∩ { x 1, .. ., x n }¦≢0 (mod m )}. If A=K or A is semirecursive, we obtain tight bounds on the query complexity of ODD A n and WMOD( m ) A n. We obtain lower bounds for A r. e. The lower bounds for A r. e. are derived from the lower bounds for A semirecursive. We obtain that every tt-degree has a set A such that ODD A requires n n parallel queries to A, and a set B such that ODD B n can be decided with one query to B. Hence for bounded-query complexity, how information is packaged is more important than Turing degree. We investigate when extra queries add power. We show that, for several nonrecursive sets A, the more queries you can ask, the more sets you can decide; however, there are sets for which more queries do not help at all.

Details

FOCS Conference 1995 Conference Paper

3-Coloring in Time O(1. 3446 n ): A No-MIS Algorithm

  • Richard Beigel
  • David Eppstein

We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2, 3)-SSS while the other problems above are special cases of (3, 2)-SSS; there is also a natural duality transformation from (a, b)-SSS to (b, a)-SSS. We give a fast algorithm for (3, 2)-SSS and use it to improve the time bounds for solving the other problems listed above.

Details

FOCS Conference 1995 Conference Paper

Fault Diagnosis in a Flash

  • Richard Beigel
  • William Hurwood
  • Nabil Kahalé

Consider a set of n processors that can communicate with each other. Assume that each processor can be either "good" or "faulty". Also assume that the processors can test each other. We consider how to use parallel testing rounds to identify the faulty processors, given an upper bound t on their number. We prove that 4 rounds are necessary and sufficient when 2/spl radic/(2n)/spl les/0. 03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t/spl ges/0. 49n (for n sufficiently large), and 10 rounds are sufficient when t<0. 5n (for all n). (It is well known that no general solution is possible when t/spl ges/0. 5n).

Details

FOCS Conference 1991 Conference Paper

Languages that Are Easier than their Proofs

  • Richard Beigel
  • Mihir Bellare
  • Joan Feigenbaum
  • Shafi Goldwasser

Languages in NP are presented for which it is harder to prove membership interactively than it is to decide this membership. Similarly, languages where checking is harder than computing membership are presented. Under assumptions about triple-exponential time, incoherent sets in NP are constructed. Without any assumptions, incoherent sets are constructed in DSPACE (n to the log n), yielding the first uncheckable and non-random-self-reducible sets in that space. >

Details

FOCS Conference 1991 Conference Paper

On ACC

  • Richard Beigel
  • Jun Tarui

It has been shown by A. Yao (1990) that every language in ACC is recognized by a sequence of depth-2 probabilistic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog (n) at the leaves. The authors simplify Yao's proof and strengthen his results: every language in ACC is recognized by a sequence of depth-2 deterministic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog(n) at the leaves. They also analyze and improve modulus-amplifying polynomials constructed by S. Toda (1989) and Yao: this yields smaller circuits in Yao's and the present results on ACC. >

Details